Optimal Distributed Algorithms in Unlabeled Tori and Chordal Rings

✍ Scribed by Bernard Mans

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 325 KB
• Volume: 46
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1006/jpdc.1997.1389

✦ Synopsis

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 of handrail which 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 of N processors can be solved using 2(N) messages instead of O(N log N ). Using the same handrail paradigm, we solve the election problem using 2(N) messages in unlabeled chordal rings with one chord (of length approximately √ N). This solves the long-standing open problem of the minimal number of unlabeled chords required to decrease the O(N log N ). message complexity. For each topology, we give an algorithm to compute the sense of direction in 2(N) messages (improving the O(N log N ) 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.