Nati Linial. Locality in Distributed Graph Algorithms. SIAM Journal on Computing, 21(1), pages 193-201, 1992.
This paper has had a major impact on distributed message-passing algorithms. It focused a spotlight on the notion of locality in distributed computation and raised interesting questions concerning the locality level of various distributed problems, in terms of their time complexity on different classes of networks. Towards that goal, in this paper, Linial developed a model particularly suitable for studying locality, which ignores message sizes, asynchrony and failures. This clean model allowed researchers to isolate the effects of locality and study the roles of distances and neighborhoods, as graph theoretic notions, and their interrelations with algorithmic and complexity-theoretic problems in distributed computing.
In addition to this major conceptual contribution, Linial’s paper presents an O(Δ2)-coloring algorithm for graphs with maximum degree at most Δ that runs in O(log* n) time. It is based on a new connection between extremal set theory and distributed computing. This result serves as a cornerstone for many other distributed coloring algorithms, including the current best algorithm. Whether one can get an O(Δ2-ε)-coloring within the same time bound remains a major open problem.
His paper also proves that, for any function f, any f(Δ)-coloring algorithm requires
Ω(log* n) time. Moreover, the same bound is shown for 3-coloring an oriented path or cycle. To obtain these lower bounds, Linial introduced the concept of the neighborhood graph of a distributed network and analyzed it. An enhanced form of his technique was recently used for establishing the best known lower bounds for Maximal Independent Set and Maximal Matching.
In summary, Linial’s paper opened new approaches to distributed symmetry breaking and remains one of the most important papers in this area.
The 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 Prize is sponsored jointly by the ACM Symposium on Principles of Distributed Computing (PODC) and the EATCS Symposium on Distributed Computing (DISC). This prize is presented annually, with the presentation taking place alternately at ACM PODC and EATCS DISC. This year it will be presented at DISC 2013.
Prize Committee 2013:
- Yehuda Afek, Tel-Aviv Univ.
- Faith Ellen, Univ. of Toronto
- Boaz Patt-Shamir, Tel-Aviv Univ.
- Sergio Rajsbaum, UNAM
- Alexander Shvartsman, Univ. of Connecticut
- Gadi Taubenfeld, IDC, chair