Michel Raynal, membre du Conseil d’administration et du Conseil scientifique de la SIF est lauréat du prix SIROCCO 2015. La SIF se félicite de cette reconnaissance des travaux de Michel Raynal par le prix de l’innovation SIROCCO.
Texte original
Dear colleagues,
We are happy to announce the winner of the SIROCCO Innovation award in distributed computing for 2015: Michel Raynal. Michel has made numerous major contributions to the field of distributed computing and the detailed announcement can be found bellow. Michel will give a talk at the prize ceremony during the coming SIROCCO in Montserrat, Spain, July 15-17.
————————————————————————————————————————————————-
The Innovation award in distributed computing formal announcement:
Laudatio:
It is a pleasure to award the 2015 SIROCCO Prize for « Innovation in distributed Computing » to Michel Raynal. Michel has made numerous major contributions to the field of distributed computing. The prize is awarded for this lifetime achievement of his, but especially for his contribution to the research on problems related to consensus (such as set agreement); even more specifically, we note here his work on the conditions-based approach to consensus.
This approach was a fresh and innovative way to look at a fundamental problem, thus a very good match for the spirit of the SIROCCO award.
The consensus problem and its celebrated FLP impossibility result are among the oldest, most seminal problems studied in the field of distributed computing. More generally, an important concern in distributed systems has been to identify common behaviors of systems, and to design solutions that behave well in those scenarios. Researchers have typically looked at partially synchronous executions, in one way or another. Michel introduced a surprising and natural new dimension
to the area. Consider a distributed system where consensus is trying to be reached, among the values produced by a set of sensors, or by the votes selecting a president by a community. It is often the case that some combinations of values, which he called conditions, of the sensors or of the electors, are much more likely to occur than others. Michel came up with the idea of designing distributed algorithms that try to adapt to such conditions.
In SIROCCO 2001, Michel considered the condition-based approach to solving agreement problems. This work considers solutions to agreement problems, when some input combinations are known not to appear in system executions. The idea spawned a whole new and fruitful line research line, with many follow-up contributions, including contributions by Michel himself. It has been possible to identify conditions that allow to solve various distributed tasks, in various models of computation, and in those cases where a solution exist, to study the time needed to solve a task assuming a given condition on its inputs holds.
An impressive aspect of this work is that Michel has linked two seemingly unrelated area: error correcting codes and agreement protocols (IEEE Transactions on Computers 2007). In a nutshell, this captures the following insight: an input vector for the consensus problem actually encodes a value that the processes have to decode in order to decide it. An exciting side-effect of this work is a new proof of the impossibility of designing perfect codes when digit erasures are possible. Very cleverly, Michel showed that the design of such codes is equivalent to solving consensus despite asynchrony and process crashes. This is a very ingenious and perceptive work.
Michel has also used the condition-based approach to establish a strong link between impossibility results in asynchronous fault-prone systems and efficiency in synchronous systems. This is also a remarkable achievement that provides a better understanding of fundamental computability limitations in distributed computing.
It is intuitively clear that although consensus is not solvable in asynchronous distributed systems where crash failures can occur, it is actually solvable in most executions of such a system, and in some sense randomized algorithms formalize this claim. Michel’s ideas provide an orthogonal perspective, where one can quantify and characterize the structure of the inputs that allow solving consensus and other coordination tasks, establishing an essential link to the topology approach-based to fault tolerance.
Following its introduction by Michel, the innovative condition-based approach was investigated by many researchers leading to many follow-up papers, some of which appeared in forums as prestigious as Journal of the ACM, and several of which were published in SIROCCO.
Michel is one of the most prolific researchers in distributed computing. He belongs to a very small group of researchers who are leaders in establishing distributed computing as a flourishing research area. In particular, he published 13 papers in SIROCCO. In particular, in the list below, the first paper is the above mentioned SIROCCO paper on the condition-based approach [1].
The 2015 award committee:
Thomas Moscibroda (Microsoft), Guy Even (Tel Aviv University), Shay Kutten (Technion)- chair, Andrzej Pelc (Universite du Quebec en Outaouais), Masafumi Yamashita (Kyushu University)*
Selected publications related to Michel Raynal’s contribution:
1. Achour Mostéfaoui, Sergio Rajsbaum, Michel Raynal, Matthieu Roy: Efficient Condition-Based Consensus. SIROCCO 2001:275-292
2. Achour Mostéfaoui, Sergio Rajsbaum, Michel Raynal, Matthieu Roy: A Hierarchy of Conditions for Asynchronous Interactive Consistency. PACT 2003:130-140
3. Achour Mostéfaoui, Sergio Rajsbaum, Michel Raynal, Matthieu Roy: Condition-Based Protocols for Set Agreement Problems. DISC 2002:48-62
4. Achour Mostéfaoui, Eric Mourgaya, Philippe Raipin Parvédy, Michel Raynal: Evaluating the Condition-Based Approach to Solve Consensus. DSN 2003:541-550
5. Achour Mostéfaoui, Sergio Rajsbaum, Michel Raynal: Conditions on input vectors for consensus solvability in asynchronous distributed systems. J. ACM 50(6):922-954 (2003). (Previously in STOC 2001.)
6. Achour Mostéfaoui, Sergio Rajsbaum, Michel Raynal, Matthieu Roy: Condition-based consensus solvability: a hierarchy of conditions and efficient protocols. Distributed Computing 17(1):1-20 (2004). (Previously in PODC 2001.)
7. Achour Mostéfaoui, Sergio Rajsbaum, Michel Raynal: Synchronous condition-based consensus. Distributed Computing 18(5):325-343 (2006). (Previously in DISC 2003 and DISC 2004.)
8. Roy Friedman, Achour Mostéfaoui, Sergio Rajsbaum, Michel Raynal: Asynchronous Agreement and Its Relation with Error-Correcting Codes. IEEE Trans. Computers 56(7):865-875 (2007)
9. Achour Mostéfaoui, Sergio Rajsbaum, Michel Raynal, Corentin Travers: The Combined Power of Conditions and Information on Failures to Solve Asynchronous Set Agreement. SIAM J. Comput. 38(4):1574-1601 (2008) (Previously in PODC 2005.)
10. Yoram Moses, Michel Raynal: No Double Discount: Condition-Based Simultaneity Yields Limited Gain. Inf. Comput. 214: 47-58 (2012) (Previously in DISC 2008)
11. François Bonnet, Michel Raynal: Conditions for Set Agreement with an Application to Synchronous Systems. J. Comput. Sci. Technol. 24(3):418-433 (2009). (Previously in ICDCS 2008.)
* We wish to thank the nominators for the nomination and for contributing heavily to this text