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 *Jean-Claude BERMOND* as the *
* recipient of this year's Prize for Innovation In Distributed *
* Computing. *
**********************************************************************
The prize is given in recognition of Bermond for his contribution to
the study of the impact of structure of networks on the efficiency of
parallel or distributed algorithms, 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
routing, broadcasting, gossip protocols, traffic grooming, fault
tolerant network design, monopolies, and other topics, illustrated,
in particular, by the following papers:
- J.-C. Bermond, L. Chacon, D. Coudert, and F. Tillerot.
Cycle Covering.
In Proc. SIROCCO 2001: 21-34.
- J.-C. Bermond, B. Jackson, F. Jaeger.
Shortest coverings of graphs with cycles.
J. Comb. Theory, Ser. B 35(3): 297-308 (1983)
- J.-C. Bermond, C. Peyrat.
De Bruijn and Kautz networks: a competitor for the hypercube?
In Proc. 1st European Workshop on Hypercubes and Distributed
Computers: 279-293 (1989).
- J.-C. Bermond, Stephane Perennes.
Efficient Broadcasting Protocols on the de Bruijn and Similar Networks.
In Proc. SIROCCO 1995: 199-209
- J.-C. Bermond, L. Gargano, A. Rescigno, U. Vaccaro.
Fast Gossiping by Short Messages.
SIAM J. Comput. 27(4): 917-941 (1998)
- J.-C. Bermond, P. Fraigniaud.
Broadcasting and Gossiping in de Bruijn Networks.
SIAM J. Comput. 23(1): 212-225 (1994)
The paper "De Bruijn and Kautz networks: a competitor for the
hypercube?" is a pioneering paper investigating the design of networks
for parallel and distributed computers. This paper promoted the
de Bruijn graph as a suitable network for efficient communication and
management. Under the reign of the hypercubes and meshes
tightly-coupled multi-processors, this paper was definitively
unorthodox. It was visionary too, as the de Bruijn graph was later
found particularly rich in applications, especially in the framework
of overlay network design for P2P systems.
The paper "Cycle Covering" appeared in SIROCCO 1995 deals with
protection by cycles in wavelength division multiplexing networks, a
subject originated in the operation of telecommunication networks. The
most important contribution is the use of design theory to tackle the
questions at hand, using tools developed in the paper "Shortest
coverings of graphs with cycles" (J. Comb. Theory, Ser. B). This
clever perspective can be used to show that other combinatorial
problems in communication networks are special cases of traffic
grooming, like, for instance, the problem of the minimization of the
number of ADMs for all-to-all traffic in unidirectional rings. This
allowed the tools and techniques developed in this article to be
extended to answer all-to-all traffic grooming in unidirectional rings
with larger grooming factors. Most of the techniques used in the
literature to prove lower bounds in related problems were established
in this article.
Last but not least, Bermond was among the first to identify the
importance of designing efficient protocols for structured
communication problems, including one-to-all broadcasting,
multicasting, and all-to-all broadcasting (a.k.a. gossiping). His many
contributions in this field enabled deep understanding of the
capabilities and limitations of networks in terms of efficiently
propagating informations and data.
By his results and ideas, Jean-Claude Bermond has enriched Distributed
Computing considerably, in demonstrating the importance of network
structural properties on the performances of distributed algorithms,
with applications ranging from fundamental aspects of distributed
computing to network design.
The prize will be officially delivered at the the Business meeting of
the 17th edition of the Colloquium on Structural Information and
Communication Complexity (SIROCCO), Sirince, Turkey, June 7-11, 2010.
Award Committee 2010:
Pierre Fraigniaud CNRS and University Paris Diderot, France
Shay Kutten Technion, Israel
Nicola Santoro Carleton University, Canada
Alexander A. Shvartsman University of Connecticut, USA
Shmuel Zaks Technion, Israel
**********************************************************
*
* 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
