Optimal Distributed Algorithms in Unlabelled Tori and Chordal Rings.
Bernard Mans · 1996
We study the message complexity of distributed algorithms in Tori and Chordal Rings when the communication links are unlabelled, 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 unlabelled Tori of N processors can be solved using #(N) messages instead of O(N log N ). Using the same handrail paradigm, we solve the Election problem using #(N) messages in unlabelled chordal rings with one chord (of length approximately # N ). This solves a long-standing open problem of the minimal number of unlabelled chords required to decrease to decrease the O(N log N) message complexity. For each topology, we give an algorithm to compute the Sense of Direction in #(N) messages (improving the O(N log N) previous results). This proves the more fundamental result that any global...