Deterministic Resource Discovery in Distributed Networks |
| |
Authors: | Shay Kutten David Peleg and Uzi Vishkin |
| |
Affiliation: | (1) Faculty of Industrial Engineering and Management, Technion, Haifa 32000, Israel;(2) Department of Computer Science and Applied Mathematics, The Weizmann Institute, Rehovot 76100, Israel;(3) Electrical and Computer Engineering Department, University of Maryland Institute for Advanced Computer Studies, College Park, MD 20742, USA;(4) Computer Science Department, The Technion, Haifa 32000, Israel |
| |
Abstract: | The resource discovery problem was introduced by Harchol-Balter,
Leighton, and Lewin. They developed a number of algorithms
for the problem in the weakly connected directed graph model. This model is a
directed logical graph that represents the vertices’ knowledge about the topology
of the underlying communication network.
The current paper proposes a deterministic algorithm for the
problem in the same model,
with improved time, message, and communication complexities.
Each previous algorithm had a complexity that was higher at least in one of the
measures. Specifically, previous deterministic solutions required either time linear
in the diameter of the initial network, or communication complexity $O(n^3)$ (with
message complexity $O(n^2)$), or message complexity $O(|E_0| \log n)$ (where $E_0$
is the arc set of the initial graph $G_0$). Compared with the main randomized
algorithm of Harchol-Balter, Leighton, and Lewin, the time complexity is reduced
from $O(\log^2n)$ to\pagebreak4] $O(\log n )$, the message complexity from $O(n \log^2 n)$ to
$O(n \log n )$, and the communication complexity from $O(n^2 \log^3 n)$ to
$O(|E_0|\log ^2 n )$.
\par
Our work significantly extends the connectivity algorithm of Shiloach
and Vishkin which was originally given for a parallel model of computation.
Our result also confirms a conjecture of Harchol-Balter, Leighton, and
Lewin, and addresses an open question due to Lipton. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|