Optimal Distributed Algorithms in Unlabeled Tori and Chordal Rings

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.