Tutorial 4: Implementing concurrent objects in multiprocessor machines
Prof. Michel Raynal (University of Rennes, France)
http://www.irisa.fr/prive/raynal/
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".