The basics of distributed computing: Shared memory Hugues Fauconnier Univ. Paris Diderot, France

Biography:
Hugues Fauconnier holds a PhD in computer sciences from the Université Paris-7 (1982) and HDR (« habilitation à diriger des recherches) » in 2001. His main research concerns distributed computing and is a specialist in fault-tolerance, distributed algorithms, failure detectors and models of distributed computing. He has published many important articles in the main scientific journals in the domain. With C. Delporte he is responsible of the French ANR-Project DISPLEXITY (distributed computing: computability and complexity). He is actually Professor in Université Paris-Diderot and heads the computer science département of that University. Moreover he is in charge of the Licence of Computer Science of Université Paris-Diderot.

Abstract:

We present some principles on shared memory distributed computing. In this part, we first present the fundamental notion of linearizability. Atomic registers, TestAndSet, CompareAndSwap … and more generally distributed data structure may be specified as Shared Atomic Objects defined by a sequential specification. We introduce the Herlihy’s hierarchy that enable to compare the computational power of these objects. Moreover an important result that consensus is universal in the sense that any object shared by n processes may be implemented in a wait-free way with help of consensus for n processes