Carleton University
Technical Report TR-231
December 1993
Optimal Elections in Labeled Hypercubes
Abstract
We study the message complexity of the Election problem in Hypercube networks, when the processors have a “Sense of Direction”, i.e. the capability to distinguish between adjacent communication links according to some globally consistent scheme.
We present an original 0(N) messages algorithm which uses the natural dimensional labeling of the communication links; to date, the best existing bound was O(N log N) messages. This result answers a long-standing open problem posed by the 0(N) messages bound for chordal rings [1].
We also consider the Election problem for Hypercube with another common labeling which is distance-based. We prove that, in this case the problem becomes drastically simplified and we present a 0(N) messages solution. Finally, we study the communication cost to change one orientation labeling to the other and prove that O(N) messages suffice.