Prize for Innovation in Distributed Computing

                         Awarded by the
  Colloquium on Structural Information and Communication Complexity
                           (SIROCCO)


The Prize for Innovation in Distributed Computing is awarded by the
Colloquium on Structural Information and Communication Complexity
(SIROCCO). It is established to recognize individuals whose research
contributions on the relationships between information and efficiency
in decentralized computing have expanded the collective investigative
horizon by formulating new problems, or identifying new research
areas, that were at the time of their introduction unorthodox and
outside the mainstream. The prize recognizes originality, innovation,
and creativity. The recipient of the Prize is chosen among the
nominated persons for the current year.

The Award Committee has selected Nicola Santoro as the recipient of
this year's Prize for Innovation In Distributed Computing.

The prize is given to Nicola Santoro for his overall contribution on
the analysis of the labeled graph properties which has been shown to
have a significant impact on computability and complexity in systems
of communicating entities. These contributions are including the
notions of "Implicit Routing", "Sense of Direction", and "'topological
awareness'", illustrated, in particular, by the following papers:

 - Nicola Santoro, Ramez Khatib: Labeling and Implicit Routing in
   Networks. Comput. J. 28(1): 5-8 (1985)

 - Paola Flocchini, Bernard Mans, Nicola Santoro: Sense of Direction:
   Formal Definitions and Properties. SIROCCO 1994: 9-34

 - Paola Flocchini, Alessandro Roncato, Nicola Santoro: Backward
   Consistency and Sense of Direction in Advanced Distributed
   Systems. SIAM J. Comput. 32(2): 281-306 (2003)

The paper "Labeling and Implicit Routing in Networks" is a pioneering
paper investigating the design of compact data structures for
distributed routing in networks. In particular, it introduces the
Interval Routing technique as one of the very first techniques used
for compacting information required for routing. This technique has
been implemented by INMOS on its most recent version of the
Transputer, and is at the basis of some XML search engines.

The aforementioned papers on Sense of Direction are part of the very
few papers that make explicit common implicit notions of knowledge. In
particular, the notion of sense of direction formalizes the
relationship between the node/edge labeling in a network, the
topological structure of this network, and the local view that an
entity can get of the entire system. It enables to generalize to any
graph results that were known only under certain assumptions such as
the ability to distinguish right from left, or to identify the four
cardinal directions.

By his results and ideas, Nicola Santoro has enriched Distributed
Computing considerably, providing innovative concepts at the source of
an extremely large number of current investigations, ranging from
compact routing to mobile computing. His pioneering investigations of
distributed computing in labeled networks are among the most
influential ones, and have opened a vast domains of promising
researches, aiming at capturing and understanding the central notion
of "local knowledge".  He is the author of the book "Design and
Analysis of Distributed Algorithms" (Wiley, 2006). Quoting the
introduction: "My own experience as well as that of my students leads
to the inescapable conclusion that both to teach and to learn
distributed algorithms are fun". Those of us who had the opportunity
to work with Nicola Santoro are the witnesses that it is not the least
of his contributions to have make this conclusion a fact.

The prize will be officially delivered at the the Business meeting of
the 16th edition of the Colloquium on Structural Information and
Communication Complexity (SIROCCO), May 25-27, 2009, Piran, Slovenia.

Award Committee 2009:

Pierre Fraigniaud              CNRS and University Paris Diderot
Leszek Gasieniec               University of Liverpool
David Peleg                    Weizmann Institute
Alexander A. Shvartsman        University of Connecticut
Shmuel Zaks                    Technion