Technical Report CS0897

Title: Simple and Efficient Network Decomposition and Synchronization
Authors: Shlomo Moran and Sagi Snir
Abstract: We present a simple and efficient method for the decomposition of a network into clusters. This method is used to perform the preprocessing phases needed for variants of the synchronizers in [Awe85, SS94] in $O(|V|)$ time and $O(|E|)+|V|\log |V|)$ communication complexities, while maintaining constant message size and constant memory per edge. The synchronizers resulted from our constructions are more efficient than the original ones. For isntance, they enable to perform Breadth First Search in an asynchronous network, in which no preprocessing has been done, in communication and time complexities of $O(K|V|D+|E|+|V| \log |V|)$ and $O(D \log_K |V|+|V|)$ respectively, where $K \geq 2$ is a parameter, and $D$ is the diameter of the network. We also present an efficient cover-coarsening algorithm, which improves the coarsening algorithm in [SS94] in several aspects.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1997
To the main CS technical reports page

Computer science department, Technion