 |
NominationThe Edsger W. Dijkstra Prize in Distributed Computing is awarded for an outstanding paper on the principles of distributed computing, whose significance and impact on the theory and/or practice of distributed computing has been evident for at least a decade. The Dijkstra Award Committee has selected Baruch Awerbuch and David Peleg as the recipients of this year Edsger W. Dijkstra Prize in Distributed Computing. The prize is given to them for their outstanding paper: ``Sparse Partitions" published in the proceedings of the 31st Annual Symposium on Foundations of Computer Science, pages 503-513, 1990. The Sparse Partitions paper by Awerbuch and Peleg signified the coming-to-age of the area of distributed network algorithms. In this work, a line of research that started with Awerbuch's synchronizer and Peleg's spanner has culminated in this ground breaking paper that has had a profound impact on algorithmic research in distributed computing and in graph algorithms in general. The paper presents concrete definitions of the intuitive concepts of locality and load, and gives surprisingly effective constructions to trade them off. The fundamental technical contribution in the paper is the algorithm of coarsening, which takes, as input, a decomposition of the graph to possibly overlapping components, and generates a new decomposition whose locality is slightly worse, but whose load is far better. The desired balance between locality and load is controlled by a parameter provided by the user. While many other underlying ideas were present in prior work of Awerbuch and Peleg (separately), in the Sparse Partitions paper these ideas have come together, with a unified view, resulting in a new powerful toolkit that is indispensable for all workers in the field. The magnitude of the progress achieved by the new techniques was immediately recognized, and its implications spawn much research to this day. In the Sparse Partitions paper itself, the authors improve on the best known results for two central problems of network algorithms, and many other applications of the results followed, quite a few of them in applications that were visionary at their time. To mention just a few, these include computation of compact routing tables and location services of mobile users (in the original paper), dramatically more efficient synchronizers, effective peer-to-peer network design, and scheduling in grid-like computing models. Besides these applications of the results, the paper can be viewed as one of the important triggers to much of the fundamental research that was dedicated to exploring other variants of the basic concepts, including the notions of bounded-growth graphs, tree metrics, general and geometric spanners. It is interesting to view the Sparse Partitions paper in the historical context. The area of Network Algorithms has its roots in classical graph algorithms. Distributed algorithms have proved to be an algorithmically rich field with the Minimum Spanning Tree paper of Gallager, Humblet and Spira. Motivated by the asynchronous nature of distributed systems, Awerbuch invented the concept of a synchronizer. Peleg, coming from the graph theoretic direction, generalized the notion of spanning tree and invented the concept of spanners. In the Sparse Partitions paper, the additional ingredient of load was added to the combination, yielding a powerful conceptual and algorithmic tool. The results superseded the best known results for classical graph algorithms, thus showing the maturity of the field, which closed a circle by becoming a leading source for graph algorithms of any kind. Award Committee 2008
|
|
|
