*Sponsored by SIGACT, SIGOPS, AT&T Labs, HP, IBM, Intel, and Sun Microsystems.*
The Edsger W. Dijkstra Prize in Distributed Computing was created to acknowledge 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 following paper received this award at PODC 2004.
R. G. Gallager, P. A. Humblet, and P. M. Spira, “A Distributed Algorithm for Minimum-Weight Spanning Trees,” ACM Transactions on Programming Languages and Systems (TOPLAS), vol. 5, no. 1, January 1983, pp. 66-77.
Members of the selection committee were Shay Kutten (chair), David Peleg, George Varghese, and Jennifer Welch. We thank the colleagues who contributed to the following description of the paper and its impact:
The Gallager-Humblet-Spira paper describes an elegant and efficient distributed algorithm for finding a minimum spanning tree in an asynchronous network. The problem is important to solve, both theoretically and practically, as a minimum spanning tree can be used for efficient broadcast in the network and to elect a leader node in the network, which can facilitate crash recovery.
This paper has had a very significant impact on research in distributed computing in several respects. First, the paper was a major algorithmic breakthrough on many fronts. It solved the fundamental problem of symmetry breaking (or leader election) in the setting of a general graph, overcoming great difficulties that restricted previous results to be applicable only in the context of rings and complete graphs. Furthermore, the algorithm has a surprisingly low message complexity for this important problem. This motivated many later authors to concentrate on improving the complexity of distributed algorithms.
To achieve its goals, the paper presents techniques for multicasting, and for query and reply. These techniques have found extensive use in theoretical algorithms, as well as in practical protocols, ever since. Additional techniques presented in the paper, dealing with cluster coordination and routing, have also been in widespread use, most notably in protocols for handshake, synchronization, and distributed phases.
Another contribution of the paper is in the beauty and elegance of the algorithm and its presentation. It addresses an intricate problem and does so by employing an exceptional degree of asynchrony among the nodes. Nevertheless, its structure is very intuitive and is easy to comprehend. As a result, the algorithm has become a common showcase for professors to lure students into the field.
Many distributed algorithms cope with concurrency by using mechanisms that force the dynamics of the execution to consist of well-formed sequential phases of computation. The algorithm by Gallager, Humblet, and Spira is unique in that it facilitates much more asynchronous activity than is found in many other algorithms, while still being very strongly structured.
Moreover, the algorithm is sufficiently complicated and interesting that it has become a challenge problem for formal verification methods. On one hand, its correctness is obvious; on the other hand, the task of finding a formal proof poses a challenge that stretches previously existing formal methods. Many papers have been written giving proofs for this algorithm and variations on it, both manual and computer-assisted. Finding a proof that copes with the intricacies of this algorithm in a natural way is still very much an open problem in protocol verification and formal methods.
In summary, this paper is a genuine milestone in the area of asynchronous network algorithms; it has changed this field completely, in terms of both algorithmics and analysis techniques.
Sadly, one of the authors, P.M. Spira, passed away in 1998. Richard Karp wrote the following tribute:
Philip Spira (1941-1998) began his career as a theoretical computer scientist. He received a Ph.D. from Stanford in 1968 with a seminal thesis on the circuit complexity of group operations. From 1968 to 1973 he was a faculty member in EECS at Berkeley, where he did work of lasting significance on the number of linear tests needed to verify a system of linear inequalities, and on shortest-path algorithms. He then had a successful career in Silicon Valley, making contributions to high-tech companies including Apple Computer and Hewlett-Packard. He was a free spirit and a very responsible and devoted father and husband. He would be overjoyed to know that his daughter Tamara will be starting a Ph.D. program at UC Santa Cruz and his son Joshua will be beginning his graduate studies at UC Berkeley. Memories of Phil still bring smiles to his family and host of friends.
This page maintained by Gil Neiger.
Last modified: May 20, 2005