Sunday, March 15, 2015

Fwd: SIROCCO 2015 - Innovation Award in Distributed Computing and Invited Speakers

Dear colleagues,

1. We are happy to announce the winner of the SIROCCO Innovation award
in distributed computing for 2015: ** Michel Raynal **. The detailed
announcement can be found bellow. Michel will give a talk at the prize
ceremony during the coming SIROCCCO in
Montserrat, Spain, July 15-17.
2. The Winner of the Innovation award will join the impressive list of
additional invited speakers (partial list).
- Amos Korman
- Bernhard Häupler
- Nati Linial
- Saket Navlakha

See you in Montserrat
(submission deadline April 30th)


The Innovation award in distributed computing formal announcement:

It is a pleasure to award the 2014 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
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

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
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

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