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. At least one paper (co)authored by the
nominee(s), either the original paper, or a paper directly related to
the innovative contribution, must have appeared in SIROCCO proceedings.
The Award Committee has selected _David PELEG_ as the recipient of this
year's Prize for Innovation In Distributed Computing.
The prize is given in recognition of David Peleg for his many and
important innovative contributions to distributed computing, as
illustrated by several papers, including some that appeared in the
proceedings of past SIROCCO meetings. These papers tackled a wide
variety of problems including local computing, robot computing, and the
design and analysis of dynamic monopolies, sparse spanners, and compact
routing and labeling schemes, as illustrated, in particular, by the
following papers:
- B. Awerbuch, O. Goldreich, D. Peleg, R. Vainish. A Trade-Off between
Information and Communication in Broadcast Protocols. J. ACM 37(2):
238-256 (1990)
- R. Cohen, D. Peleg. Robot Convergence via Center-of-Gravity
Algorithms. SIROCCO 2004: 79-88
- U. Feige, D. Peleg, P. Raghavan, E. Upfal: Randomized Broadcast in
Networks. Random Struct. Algorithms 1(4): 447-460 (1990)
- D. Peleg. Size Bounds for Dynamic Monopolies. SIROCCO 1997: 151-161
- D. Peleg. Informative labeling schemes for graphs. MFCS 2000: 579-588
- D. Peleg, E. Upfal. A trade-off between space and efficiency for
routing tables. J. ACM 36(3): 510-530 (1989)
The paper "A Trade-Off between Information and Communication in
Broadcast Protocols" is a prominent illustration of all studies dealing
with compromises between the ability of solving tasks efficiently in a
distributed manner, and the amount of global information provided to the
individual computing entities about their environment. It is also one of
the many seminal papers of David Peleg about information dissemination
problems. In this latter framework, the paper "Randomized Broadcast in
Networks" is one of the most referenced papers in connection to the
analysis of gossip protocols.
The paper "A trade-off between space and efficiency for routing tables"
is definitively one of the most influential papers in the theory of
compact routing. The richness of the concepts introduced in this paper
were the sources of many related topics, including the whole framework
of compact informative labeling schemes, yet another fundamental
research domain initiated by David Peleg (cf. the paper "Informative
labeling schemes for graphs").
David Peleg pioneered so many research domains in the framework of
distributed computing that it would be impossible to provide an
exhaustive list. In addition to the aforementioned topics, he was
interested in robot computing (see, e.g., "Robot Convergence via
Center-of-Gravity Algorithms"), in the evolution of dynamic discrete
systems (see, e.g., "Size Bounds for Dynamic Monopolies"), and, of
course, in graph problems with applications to distributed computing.
By his results and ideas, David Peleg has enriched distributed computing
considerably. In particular, he is one of the most significant
contributors to the theory of local computing, including the study of
trade-offs between "local knowledge" and "global performances", which is
precisely what SIROCCO is about. His book "Distributed computing: a
locality-sensitive approach" (SIAM) is a prominent reference describing
the methodology for addressing locality in distributed computing.
The prize will be officially delivered at the the Business meeting of
the 18th International Colloquium on Structural Information and
Communication Complexity (SIROCCO), June 26-29, 2011, Gdansk, Poland.
Award Committee 2011:
Pierre Fraigniaud (CNRS and University Paris Diderot)
Shay Kutten (Technion)
Boaz Patt-Shamir (Tel Aviv University)
Alexander A. Shvartsman (University of Connecticut)
Paul Spirakis (CTI and University of Patras)
**********************************************************
*
* 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
