Invited Tutorial

  1. Michel Raynal

    IRISA - ISTIC Université de Rennes, France

Biography

Michel Raynal is an Emeritus Professor of Informatics, IRISA, University of Rennes, France. His research interests are the basic principles of distributed computing systems. Recognized as a world leading researcher in distributed computing, he is the author of numerous papers on this topic (more than 170 articles in int'l scientific journals, and more than 330 papers in int'l conferences). He is also well-known for his books on distributed computing. Michel Raynal is a senior member of the prestigious "Institut Universitaire de France", and a member of Academia Europaea. He was the recipient of the 2015 "Int'l Award "Innovation in Distributed Computing" (also known as SIROCCO Prize), and recipient of the 2018 "Outstanding Technical Achievement in Distributed Computing" IEEE Award. Michel Raynal is also "Distinguished Chair Professor on Distributed Algorithms" at the Polytechnic University (PolyU) of Hong Kong.

Michel Raynal chaired the program committee of the major conferences on distributed computing (e.g., ICDCS, DISC, SIROCCO, OPODIS, ICDCN, etc.), and has been member (or head) of their steering committees. He served on the program committees of more than 200 int'l conferences including all the most prestigious ones. He is the recipient of several "Best Paper" awards of major conferences (including ICDCS 1999, 2000 and 2001, SSS 2009 and 2011, Europar 2010, DISC 2010, PODC 2014). He supervised more than 45 PhD students, and gave lectures on distributed computing in many universities all over the world. Michel Raynal has written 12 books on fault-tolerant concurrent and distributed systems, among which the follwing trology "Concurrent Programming: Algorithms, Principles and Foundations", Springer, 515 pages, 2013 (ISBN 978-3-642-32026-2) "Distributed Algorithms for Message-passing Systems", Springer, 510 pages, 2013 (ISBN: 978-3-642-32026-2), and "Fault-Tolerant Message-Passing Distributed Systems: An Algorithmic Approach" Springer, 459 pages, 2018 (ISBN: 978-3-319-94140-0).

Title

A Tutorial on the Notion of Universality in Crash-Prone Asynchronous Message-Passing Systems.

Abstract

The notion of a "universal construction" is central in computing science and technology: general solutions make life easier and the wheel has not to be reinvented each time a new problem appears.

In the context of message-passing asynchronous distributed systems made up of n processes, where some of them may commit crash failures, a universal construction is an algorithm that is able to build any object defined by a sequential specification despite the adversary,effect resulting from the combination of asynchrony and process crashes. The aim of this tutorial is to introduce the reader to the notion of a "distributed universal construction" (and "universal objects" these constructions rely on), and more precisely, explain what can be done, what cannot be done, and which assumptions on the environment are necessary in order objects with provably reliability properties can be built. Its aim is be a guided tour providing the reader with the basic knowledge needed to understand and master asynchronous message-passing fault-tolerant computing. Its spirit is not to be a catalog of constructions proposed so far, but an as simple as possible presentation of concepts and mechanisms that constitute the basis these universal constructions rely on.

Keywords

Agreement, Asynchronous system, Atomic operations, Concurrent object, Consensus, Computability, Crash failure, Distributed Computing, Distributed state machine, Environment, Fault-tolerance, Message-passing, Read/write registers, Sequential specification, Universal construction.