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 http://sirocco2015.cs.upb.de/venue.html
(submission deadline April 30th)
-------------------------------------------------------------
The Innovation award in distributed computing formal announcement:
Laudatio
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
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.)
*
<https://mail.google.com/mail/u/0/#14bf9d79b827e501_14bf9afe44284147_14bf9adfa67dc5ea_14bf8de73c6fed6e_14bf8b7d77f5afdd_14bf5b2e93f29dac__ftnref1>
We wish to thank the nominators for the nomination and for contributing
heavily to this text
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
