Locality in Distributed Computing

Other Titles


The topic of this thesis is the issue of locality in distributed computing. A first set of results in this thesis concerns the Δ-vertex coloring problem. They are all based on the following result. Let G be a graph such that Δ≥3,G is not a complete graph, and such that all of G except one vertex v is Δ-colored. Then, it is possible to extend this Δ-coloring to all of G by recoloring a path originating from v of length at most O(logΔn). This property allows us to develop several efficient algorithms for Δ-coloring. In particular, but not exclusively, in the distributed and PRAM models of computation. It also implies a well-known result of Brooks as a corollary. Another set of results concerns network decomposition - a basic notion in distributed graph algorithms. We improve the bounds for computing a network decomposition distributively and deterministically. Our algorithm computes an (nϵ(n),nϵ(n))-decomposition in O(nϵ(n)) time, where ϵ(n)=O(1/logn). We also show that the class of graphs G whose maximum degree is O(nδ(n), where δ(n)=O(1/loglogn), is complete for the task of computing a (logn,logn)-decomposition, in polylogarithmic in n time. Completeness is to be intended in the following sense: if we have an algorithm A that computes a (logn,logn)-decomposition in polylogarithmic in n time for graphs in G, then we can compute a (logn,logn)-decomposition in polylogarithmic in n time for all graphs. A last set of results concerns the edge coloring problem. We give a randomized distributed algorithm to compute an edge coloring of a given network G, that uses at most 1.6Δ+log2+δn colors, for any δgreaterthan0. The running time is O(logn) and the failure probability is at most ϵ, for any fixed ϵgreaterthan0. The algorithm is quite simple but requires an interesting probabilistic analysis. At the core of the analysis is an extension of the Chernoff-Hoeffding bounds, which are fundamental tools used in estimating the tail probabilities of the sum of Bernoulli-like trials.

Journal / Series

Volume & Issue



Date Issued



Cornell University


computer science; technical report


Effective Date

Expiration Date




Union Local


Number of Workers

Committee Chair

Committee Co-Chair

Committee Member

Degree Discipline

Degree Name

Degree Level

Related Version

Related DOI

Related To

Related Part

Based on Related Item

Has Other Format(s)

Part of Related Item

Related To

Related Publication(s)

Link(s) to Related Publication(s)


Link(s) to Reference(s)

Previously Published As

Government Document




Other Identifiers


Rights URI


technical report

Accessibility Feature

Accessibility Hazard

Accessibility Summary

Link(s) to Catalog Record