This page is dedicated to the workshop 40 Years of Distributed Computing, in celebration of Hagit Attiya’s 60th birthday
Dates: June 21-22, 2022
Location: Technion
All events will take place in the Taub Computer Science Building.
Talks (& coffee breaks) will be held in Room 337 (3rd floor).
Lunch will be served in the main lobby (Ground floor).
The dinner event will be held at the outdoor terrace (2nd floor).
Car entry permits are not required — please say at the gate that you are attending the workshop.
Registration (free):
Please register at this link by May 31, 2022
(please register also if you only plan to attend the dinner event)
Program (abstracts below):
Tuesday, June 21
10:00-10:30 Gathering and coffee
10:30-11:30 Rachid Guerraoui (École Polytechnique Fédérale de Lausanne)
Title: Deconstructing Bitcoin through Hagit’s Lenses
11:30-12:00 Armando Castaneda (National Autonomous University of Mexico)
Title: A Journey in DC with Hagit: From Simple Impossibility Proofs to Open Problems
12:00-12:30 Alessia Milani (Aix-Marseille University)
Title: Long-lived counters with polylogarithmic step complexity
12:30-14:00 Lunch
14:00-14:30 Adam Morrison (Tel Aviv University)
Title: Toward memory-level parallelism as an algorithmic design goal
14:30-15:00 Danny Hendler (Ben Gurion University)
Title: Recoverable Algorithms for Non-Volatile Memory
15:00-15:30 Coffee break
15:30-16:00 Nir Shavit (MIT)
Title: Collects and Snapshots in an Asynchronous World
16:00-16:30 Panagiota Fatourou (University of Crete)
Title: Fault-Tolerant Data Structures in Settings with Non-Volatile Main Memory
16:30-17:00 Jennifer Welch (Texas A&M University)
Title: Thirty-Plus Years of Collaboration on Consistency Conditions and More
18:30 Dinner event
—
Wednesday, June 22
10:00-10:30 Gathering and coffee
10:30-11:00 Petr Kuznetsov (Telecom Paris)
Title: Adaptive and Asynchronous: Thirty Years of Lattice Agreement
11:00-11:30 Faith Ellen (University of Toronto)
Title: Approximate Agreement on Graphs
11:30-12:00 Constantin Enea (Ecole Polytechnique)
Title: Preserving Hyperproperties in Programs that Use Concurrent Objects
12:00-12:30 Yehuda Afek (Tel Aviv University)
Title: 40 years of adaptive dancing with Hagit
12:30-14:00 Lunch
14:00-14:30 Oded Goldreich (Weizmann Institute)
Title: Secure Multi-Party Computation
14:30-15:00 Maurice Herlihy (Brown University)
Title: Our Long Conversation about Renaming
15:00 Farewell and coffee
Organizers:
Keren Censor-Hillel (Technion)
David Hay (Hebrew University)
For administrative questions please contact Hila Mizrahi at hilamiz@cs.technion.ac.il
Talks:
Rachid Guerraoui (École Polytechnique Fédérale de Lausanne)
Title: Deconstructing Bitcoin through Hagit’s Lenses
—————–
Armando Castaneda (National Autonomous University of Mexico)
Title: A Journey in DC with Hagit: From Simple Impossibility Proofs to Open Problems
Abstract: This talk will review a couple of simple non-topological impossibility proofs for set agreement and renaming, two paradigmatic problems for the study of agreement and symmetry breaking in distributed systems. It will also discuss related open problems.
—————–
Alessia Milani (Aix-Marseille University)
Title: Long-lived counters with polylogarithmic step complexity
Abstract:
Shared data objects are an essential abstraction in distributed computing, as they provide a consistent interface for multiple processes to interact via shared data. Linearizability is the main consistency criterion that formalizes the correctness of shared object implementations. Linearizable shared objects are intuitive to use, but they can be expensive to implement. In this talk, I will consider a widely-used shared object, the counter.
I.n 2000, Jayanti, Tan and Toueg proved a linear lower bound on the worst-case step complexity of obstruction-free implementations, from read and write operations, of a large class of shared objects, including counters. In 2012, Aspnes, Attiya and Censor-Hillel observed that the lower bound holds only when numerous operations are applied to the object and does not rule out the possibility of obtaining algorithms whose step complexity is sub-linear when the number of operations is bounded. Inspired by Hagit and co-authors work, we recently prove that there exists deterministic counters implementations with sub-linear amortized step complexity regardless of how many operations are performed on the object.
This is a joint work with Mirza Ahad Baig, Danny Hendler and Corentin Travers
—————–
Adam Morrison (Tel Aviv University)
Title: Toward memory-level parallelism as an algorithmic design goal
Abstract:
Computational models do not account for the modern processor’s ability to exploit memory-level parallelism (MLP) by parallelizing execution of independent memory reads which appear sequentially in program order. This talk will argue for making MLP a first-class algorithmic design goal instead of abstracting it away as an implementation detail.
We will showcase the benefits of an MLP-driven design by describing the Cuckoo Trie, a memory-efficient trie that leverages MLP to break a fundamental speed barrier faced by existing search trees, whose bottleneck is a series of dependent pointer-chasing memory accesses—e.g., traversing a search tree path—which the processor cannot parallelize.
Joint work with Adar Zeitak.
—————–
Danny Hendler (Ben Gurion University)
Title: Recoverable Algorithms for Non-Volatile Memory
Abstract:
The emergence of systems with non-volatile main memory (NVM) increases the need for persistent
concurrent objects. Of specific interest are recoverable implementations that, in addition to being
robust to crash-failures, are also detectable. Detectability ensures that upon recovery, it is possible
to infer whether the failed operation took effect or not and, in the former case, obtain its response.
In the first part of my talk, I will provide a high-level description of our work on detectable algorithms.
This will be followed by a recollection of the dramatic events that have transpired in an unforgettable dinner
that Hagit and I had with other colleagues more than a decade ago.
—————–
Nir Shavit (MIT)
Title: Collects and Snapshots in an Asynchronous World
Abstract:
Hagit’s deep interest in asychronous computability was channeled through a collection of important “key problems,” many of which she introduced, defined, and then studied extensively. Concurrent Collects and Atomic Snapshots are two such problems, and I will try to give the listeners a brief understanding of what they are and why they are intellectually satisfying to work on.
—————–
Panagiota Fatourou (University of Crete)
Title: Fault-Tolerant Data Structures in Settings with Non-Volatile Main Memory
Abstract:
This talk will present generic approaches for deriving recoverable synchronization algorithms, as well as recoverable implementations of many widely-used concurrent data structures on top of them. Such implementations are appealing for emerging systems featuring byte-addressable non-volatile main memory (NVMM), whose persistence allows to efficiently resurrect failed processes after crashes. Recovery ensures that after a crash, every executed operation is able to recover and return a correct response, and that the state of the data structure is not corrupted. Our experimental analysis introduces a new way of analyzing the cost of persistence instructions, not by simply counting them but by separating them into categories based on the impact they have on the performance. The analysis reveals that understanding the actual persistence cost of an algorithm in machines with real NVMM, is more complicated than previously thought, and requires a thorough evaluation, since the impact of different persistence instructions on performance may greatly vary.
—————–
Jennifer Welch (Texas A&M University)
Title: Thirty-Plus Years of Collaboration on Consistency Conditions and More
Abstract:
I will provide an overview of research I have done with Hagit or that has been inspired by research done with Hagit. The primary focus is on shared memory consistency conditions.
—————–
Petr Kuznetsov (Telecom Paris)
Title: Adaptive and Asynchronous: Thirty Years of Lattice Agreement
Abstract:
Building generic replicated state machine is equivalent to solving consensus. Intuitively, consensus is used here to ensure that concurrent operations on the replicated service are totally ordered. As no fault-tolerant asynchronous solution to consensus exists, one may ask if there is an asynchronous universal abstraction, analogous to consensus in partially synchronous systems. Lattice agreement introduced by Hagit Attiya, Maurice Herlihy and Ophir Rachman in 1992 can be seen as such an abstraction. We observe that many important applications only require specific lattice partial orders on their operations and, therefore, can be implemented asynchronously using lattice agreement. As an example, we consider the asset transfer problem that lies at the core of modern cryptocurrencies.
—————–
Faith Ellen (University of Toronto)
Title: Approximate Agreement on Graphs
Abstract:
Approximate agreement is one of the few variants of consensus that can be solved in a wait-free manner in asynchronous systems where processes communicate by reading and writing to shared memory. A natural generalization is to consider the input of each process to be a vertex of a connected graph and require the outputs to form a clique in this graph.
Moreover, each output must lie on a shortest path between two inputs.
For paths and, more generally, trees, wait-free solutions exist. We give a simple 1-resilient algorithm for any graph. However, using a generalization of Sperner’s Lemma, we show that wait-free approximate agreement on cycles of length at least 4 and, more generally, on any triangulated $d$-dimensional sphere that is not a clique, is impossible.
This is joint work with Dan Alistarh and Joel Rybicki and work of my student, Shi Hao Liu.
—————–
Constantin Enea (Ecole Polytechnique)
Title: Preserving Hyperproperties in Programs that Use Concurrent Objects
Abstract:
Concurrent objects are a widely used abstraction to simplify the design of concurrent programs. Their correctness is typically stated in terms of an atomic specification, where operations take place instantaneously, via a correctness criterion called linearizability. Linearizability ensures that replacing concurrent objects in a program with their atomic specifications is sound for reasoning about program safety properties. However linearizability is not sound for reasoning about hyper-properties, which include probabilistic guarantees of randomized programs. A more restrictive criterion, called strong linearizability, does preserve hyper-properties but it is impossible to achieve in many situations. In particular, we show that there are no strongly linearizable implementations of multi-writer registers or snapshot objects in message-passing systems. On the other hand, we show that a wide class of linearizable implementations, including well-known ones for registers and snapshots, can be modified to approximate the probabilistic guarantees of randomized programs when using atomic objects.
—————–
Yehuda Afek (Tel Aviv University)
Title: 40 years of adaptive dancing with Hagit
—————–
Oded Goldreich (Weizmann Institute)
Title: Secure Multi-Party Computation
Abstract:
My main thesis is that secure multi-party computation is an integral part of distributed computing.
Results established in the (mid to late) 1980s assert that one can construct protocols for securely computing any desirable multi-party functionality (as defined below). Indeed, what is striking about these results is their generality, and we believe that the wonder is not diminished by the (various alternative) conditions under which these results hold.
A general framework for casting (m-party) cryptographic (protocol) problems consists of specifying a random process that maps m inputs to m outputs. The inputs to the process are to be thought of as local inputs of m parties, and the m outputs are their corresponding (desired) local outputs. The random process describes the desired functionality. That is, if the m parties were to trust each other (or trust some external party), then they could each send their local input to the trusted party, who would compute the outcome of the process and send to each party the corresponding output. A secure multi-party computation of such a functionality is a protocol that lets mutually distrustful parties “emulates” the imaginary trusted party. Such protocols can be constructed in several models which vary by the underlying assumptions regarding the communication channels, the numerous parameters relating to the extent of adversarial behavior, and the desired level of emulation of the trusted party (i.e., level of “security”).
—————–
Maurice Herlihy (Brown University)
Title: Our Long Conversation about Renaming
Abstract:
In 1990, Attiya et al. posed the following question: how can a collection of asynchronous processes choose unique names from a small namespace? This innocent-sounding puzzle has turned out to be one of the most productive problems in the theory of distributed computing, inspiring (literally) hundreds of follow-on works. This talk will present a brief, incomplete, but heartfelt appreciation of this paper’s impact.
—————–