Technical Report CS0856

Authors: H. Attiya, H. Shachnai and T. Tamir
PDFNot Available
Abstract: This paper studies the power of non-restricted preprocessing on a communication graph $G$, in a synchronous, reliable system. In our scenario, arbitrary preprocessing can be performed on $G$, after which a sequence of labeling problems have to be solved on different subgraphs of $G$. We suggest a preprocessing that produces an orientation of $G$. The goal is to exploit this preprocessing for minimizing the radius of the neighborhood around each vertex from which data has to be collected in order to determine a label. We define a set of labeling problems for which this can be done. The time complexity of labeling a subgraph depends on the topology of the graph $G$ and is always less than $\min\{_x(G),O((\log n)^2)\}$. On the other hand, we show the existence of a graph for which even unbounded preprocessing does not allow fast solution of a simple labeling problem. Specifically, it is shown that a processor needs to know its $\Omega(\log n/\log \log n)$-neighborhood in order to pick a label. Finally, we derive some results for the resource allocation problem. In particular, we show that $\Omega(\log n/\log \log n)$ communication rounds are needed if resources are to be fully utilized. In this context, we define the {\em compact coloring} problem, for which the orientation preprocessing provides a fast distributed labeling algorithm. This algorithm suggests an efficient solutin for the resource allocation problem.
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 1995
To the main CS technical reports page

Computer science department, Technion