# Deterministic Resource Discovery in Distributed Networks

Title | Deterministic Resource Discovery in Distributed Networks |

Publication Type | Journal Articles |

Year of Publication | 2003 |

Authors | Kutten S, Peleg D, Vishkin U |

Journal | Theory of Computing Systems |

Volume | 36 |

Issue | 5 |

Pagination | 479 - 495 |

Date Published | 2003/// |

ISBN Number | 1432-4350 |

Keywords | Computer, Science |

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| łog 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(łog^2n)$ to\pagebreak[4] $O(łog n )$, the message complexity from $O(n łog^2 n)$ to $O(n łog n )$, and the communication complexity from $O(n^2 łog^3 n)$ to $O(|E_0|łog ^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. |

URL | http://dx.doi.org/10.1007/s00224-003-1084-8 |