Accueil du site > Vie de la recherche > Innovation

Recherchez sur ce site

Prize 2010 for Innovation In DC : Jean-Claude BERMOND récompensé

The Award Committee has selected Jean-Claude BERMOND as the recipient of this year’s Prize for Innovation In Distributed Computing.

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