| TR#: | CS0897 |
| Class: | CS |
| Title: | Simple and Efficient Network Decomposition and Synchronization |
| Authors: | Shlomo Moran and Sagi Snir |
| CS0897.pdf | |
| 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. |
| Copyright | The 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 (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1997/CS/CS0897), 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