Tutorial 4: Implementing concurrent objects in multiprocessor machines
Prof. Michel Raynal (University of Rennes, France)
Abstract: The advent of multicore architectures makes more and more important
the design of efficient shared data structures also called concurrent objects.
This tutorial is organized in two parts, as follows:
Part 1: A Short Introduction to Wait-free Computing.
Informally, "wait-free" means that the progress of a process depends only on itself. This notion is more and more pervasive in a lot of problems that basically relie (in one way or another) on the definition and the use of concurrent objects in presence of failures. This lecture will visit wait-free computing: its underlying concepts and its basic mechanisms. To that end, the lecture will also visit fundamental notions of synchronization such as the consensus number notion, and problems of asynchronous computing in presence of failures (such as renaming, set agreement, snapshot, etc.).
Part 2: Looking for Efficient Implementations of Concurrent Objects.
A contention-sensitive implementation of a concurrent object is an implementation such that the overhead introduced by locking is eliminated in the common cases, i.e., when there is no contention or when the operations accessing concurrently the object are non-interfering. This talk, that can be considered as an introduction to the topic, will present a methodological construction of a contention-sensitive implementation of a concurrent object. The talk, that will present algorithms in an incremental way, will also visit also a family of liveness conditions and important concurrency-related concepts such as the notion of an abortable object.
Short bio: Michel Raynal is a professor of Computer Science at the University of
Rennes, France. His main research interests are the basic principles of distributed
computing systems. He is a world leading researcher in the domain of distributed computing.
He is the author of numerous papers on distributed computing (more
than 120 in journals and 270 papers in international conferences) and is well-known for his (9)
distributed algorithms books on distributed computing.
He has chaired the program committee of the major conferences on the topic, served on the program committees of many international conferences, and is the recipient of several "Best Paper" awards (ICDCS 1999, 2000 and 2001, SSS 2009, Europar 2010, DISC 2010, SSS 2011).
He has been invited by many universities all over the world to give lectures on distributed computing.
He has recently written two books published by Morgan & Clayppool: "Communication and Agreement Abstractions for Fault-Tolerant Asynchronous Distributed Systems" (June 2010) and "Fault-Tolerant Agreement in Synchronous Distributed Systems" (September 2010). His last book Concurrent Programming: Algorithms, Principles and Foundations (Springer, 500 pages, ISBN: 978-3-642-32026-2) is currently in print.
Since 2010, Michel Raynal is a senior member to the prestigious "Institut Universitaire de France".