Keynote talk II

II- Another Look at the Implementation of Read/write Registers in Crash-prone Asynchronous Message-Passing Systems

Michel Raynal
IRISA, Université de Rennes

Michel Raynal is a Professor of Informatics, IRISA, University of Rennes, France. His main 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 150 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. From a « purely numeric » point of view, his h-index is 54 and his i-10 index is 254. 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). Michel raynal is also « Chair Professor on Distributed Algorithms » at the Polytechnic University (PolyU) of Hong Kong. Michel Raynal chaired the program committee of the major conferences on the topic (e.g., ICDCS, DISC,SIROCCO, OPODIS, ICDCN, etc.) and served on the program committees of more than 180 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. He gave lectures on distributed computing in many universities all over the world. In the recent past, Michel Raynal has written four books: « Communication and Agreement Abstractions for Fault-Tolerant Asynchronous Distributed Systems », Morgan & Claypool 251 pages, 2010 (ISBN 978-1-60845-293-4); « Fault-Tolerant Agreement in Synchronous Distributed Systems », 165 pages, Morgan & Claypool, September 2010), (ISBN 978-1-60845-525-6); « Concurrent Programming: Algorithms, Principles and Foundations », Springer, 515 pages, 2012 (ISBN 978-3-642-32026-2), and « Distributed Algorithms for Message-passing Systems », Springer, 510 pages, 2013 (ISBN: 978-3-642-32026-2).

This is a joint work with Damien Imbs, Achour Mostéfaoui, and Matthieu Perrin

« Yet another work on » the implementation of read/write registers in crash-prone asynchronous message-passing systems! Yes…, but, differently from its predecessors, this talk presents a communication abstraction which captures the essence of such an implementation in the same sense that total order broadcast can be associated with consensus. To this end, the talk introduces a new communication abstraction, named SCD-broadcast (SCD stands for « Set Constrained Delivery »), which, instead of a single message, delivers to processes sets of messages (whose size can be arbitrary), such that the sequences of message sets delivered to any two processes satisfies some constraints. The talk will then show that: (a) SCD-broadcast allows for a very simple implementation of a snapshot object (and consequently also of atomic read/write registers) in crash-prone asynchronous message passing systems; (b) SCD-broadcast can be built from snapshot objects (hence SCD-broadcast and snapshot objects –or read/write
registers– are « computationally equivalent »); (c) SCD-broadcast can be built in message-passing systems where any minority of processes may crash (which is the weakest assumption on the number of possible process crashes needed to implement a read/write register).


Extended deadlines

November 25, 2016

December 02, 2016

Abstract submission deadline

December 02, 2016

December 09, 2016

Paper submission deadline

January 27, 2017

Acceptance notification

March 03, 2017

Camera ready copy due



The proceedings of the conference will be published in Springer’s Lecture Notes in Computer Science

Partners & Sponsors