Optimal Distributed Algorithms in Unlabeled Tori and Chordal Rings

Bernard Mans*

*Corresponding author for this work

Research output: Contribution to journalArticle

32 Citations (Scopus)

Abstract

We study the message complexity of distributed algorithms in tori and chordal Rings when the communication links are unlabeled, which implies that the processors do not have "sense of direction." We introduce the paradigm ofhandrailwhich allows messages to travel with a consistent direction. We give a distributed algorithm which confirms the conjecture that the leader election problem for unlabeled tori ofNprocessors can be solved using Θ(N) messages instead ofO(NlogN). Using the samehandrailparadigm, we solve the election problem using Θ(N) messages in unlabeled chordal rings with one chord (of length approximatelyN). This solves the long-standing open problem of the minimal number of unlabeled chords required to decrease theO(NlogN). message complexity. For each topology, we give an algorithm to compute the sense of direction in Θ(N) messages (improving theO(NlogN) previous results). This proves the more fundamental result that any global distributed algorithm for these labeled topologies can be used with a similar asymptotic complexity in the respective unlabeled class.

Original languageEnglish
Pages (from-to)80-90
Number of pages11
JournalJournal of Parallel and Distributed Computing
Volume46
Issue number1
DOIs
Publication statusPublished - 10 Oct 1997

Fingerprint Dive into the research topics of 'Optimal Distributed Algorithms in Unlabeled Tori and Chordal Rings'. Together they form a unique fingerprint.

Cite this