eCommons

 

Locality in Distributed Computing

Other Titles

Abstract

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

Description

Sponsorship

Date Issued

1993-06

Publisher

Cornell University

Keywords

computer science; technical report

Location

Effective Date

Expiration Date

Sector

Employer

Union

Union Local

NAICS

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)

References

Link(s) to Reference(s)

Previously Published As

http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR93-1356

Government Document

ISBN

ISMN

ISSN

Other Identifiers

Rights

Rights URI

Types

technical report

Accessibility Feature

Accessibility Hazard

Accessibility Summary

Link(s) to Catalog Record