2004-07: Finding Central Sets of Tree Structures in Synchronous Distributed Systems

DIMACS TR: 2004-07

Finding Central Sets of Tree Structures in Synchronous Distributed Systems

Authors: Jonathan W. Berry, Daniel Hrozencik, Shrisha Rao and Zhizhang Shen

ABSTRACT
Finding the central sets, such as center and median sets, of a network topology is a fundamental step in the design and analysis of complex distributed systems. This paper presents distributed synchronous algorithms for finding central sets in general tree structures.

Our algorithms are distinguished from previous work in that they take only qualitative information, thus reducing the constants hidden in the asymptotic notation, and all vertices of the topology know the central sets upon their termination.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2004/2004-07.ps.gz

DIMACS Home Page