SPLASH 2020
Sun 15 - Sat 21 November 2020 Online Conference
Wed 18 Nov 2020 13:40 - 14:00 at SPLASH-I - W-4 Chair(s): Justin Hsu, Eric Koskinen
Thu 19 Nov 2020 01:40 - 02:00 at SPLASH-I - W-4 Chair(s): Sophia Drossopoulou, Jan Vitek

Modern highly-concurrent search data structures, such as search trees, obtain multi-core scalability and performance by having operations traverse the data structure without any synchronization. As a result, however, these algorithms are notoriously difficult to prove linearizable, which requires identifying a point in time in which the traversal's result is correct. The problem is that traversing the data structure as it undergoes modifications leads to complex behaviors, necessitating intricate reasoning about all interleavings of reads by traversals and writes mutating the data structure.

In this paper, we present a general proof technique for proving unsynchronized traversals correct in a significantly simpler manner, compared to typical concurrent reasoning and prior proof techniques. Our framework relies only on sequential properties of traversals and on a conceptually simple and widely-applicable condition about the ways an algorithm's writes mutate the data structure. Establishing that a target data structure satisfies our condition requires only simple concurrent reasoning, without considering interactions of writes and reads. This reasoning can be further simplified by using our framework.

To demonstrate our technique, we apply it to prove several interesting and challenging concurrent binary search trees: the logical-ordering AVL tree, the Citrus tree, and the full contention-friendly tree. Both the logical-ordering tree and the full contention-friendly tree are beyond the reach of previous approaches targeted at simplifying linearizability proofs.

Conference Day
Wed 18 Nov

Displayed time zone: Central Time (US & Canada) change

13:00 - 14:20
W-4OOPSLA at SPLASH-I +12h
Chair(s): Justin HsuUniversity of Wisconsin-Madison, USA, Eric KoskinenStevens Institute of Technology
13:00
20m
Talk
Adversarial Examples for Models of Code
OOPSLA
Noam YefetTechnion, Uri AlonTechnion, Eran YahavTechnion
Link to publication DOI Pre-print Media Attached
13:20
20m
Talk
Finding Bugs in Database Systems via Query Partitioning
OOPSLA
Manuel RiggerETH Zurich, Zhendong SuETH Zurich
Link to publication DOI Pre-print Media Attached
13:40
20m
Talk
Proving Highly-Concurrent Traversals Correct
OOPSLA
Yotam M. Y. FeldmanTel Aviv University, Artem KhyzhaTel Aviv University, Constantin EneaUniversity of Paris / IRIF / CNRS, Adam MorrisonTel Aviv University, Aleksandar NanevskiIMDEA Software Institute, Noam RinetzkyTel Aviv University, Sharon ShohamTel Aviv University
Link to publication DOI Media Attached
14:00
20m
Talk
How Do Programmers Use Unsafe Rust?
OOPSLA
Vytautas AstrauskasETH Zurich, Christoph MathejaETH Zurich, Federico PoliETH Zurich, Peter MüllerETH Zurich, Alexander J. SummersUniversity of British Columbia
Link to publication DOI Media Attached

Conference Day
Thu 19 Nov

Displayed time zone: Central Time (US & Canada) change

01:00 - 02:20
W-4OOPSLA at SPLASH-I
Chair(s): Sophia DrossopoulouImperial College London, Jan VitekNortheastern University / Czech Technical University
01:00
20m
Talk
Adversarial Examples for Models of Code
OOPSLA
Noam YefetTechnion, Uri AlonTechnion, Eran YahavTechnion
Link to publication DOI Pre-print Media Attached
01:20
20m
Talk
Finding Bugs in Database Systems via Query Partitioning
OOPSLA
Manuel RiggerETH Zurich, Zhendong SuETH Zurich
Link to publication DOI Pre-print Media Attached
01:40
20m
Talk
Proving Highly-Concurrent Traversals Correct
OOPSLA
Yotam M. Y. FeldmanTel Aviv University, Artem KhyzhaTel Aviv University, Constantin EneaUniversity of Paris / IRIF / CNRS, Adam MorrisonTel Aviv University, Aleksandar NanevskiIMDEA Software Institute, Noam RinetzkyTel Aviv University, Sharon ShohamTel Aviv University
Link to publication DOI Media Attached
02:00
20m
Talk
How Do Programmers Use Unsafe Rust?
OOPSLA
Vytautas AstrauskasETH Zurich, Christoph MathejaETH Zurich, Federico PoliETH Zurich, Peter MüllerETH Zurich, Alexander J. SummersUniversity of British Columbia
Link to publication DOI Media Attached