Linear Broadcasting and N loglog N Election in Unoriented Hypercubes.

Abstract

In this paper, we provide efficient broadcasting and election algorithms in unoriented hypercubes. First, O(N) broadcasting and traversing algorithms are introduced, where N is the number of hypercube vertices. This answers affirmatively the open question stated in [Tel95a] whether linear-message broadcasting and traversing can be achieved on hypercubes without sense of direction. Moreover, by exploiting new techniques we designed an O(N log log N) leader election algorithm. This is the first known solution being able to exploit graphtheoretic properties of unoriented hypercubes such that it outperforms algorithms designed for general graphs [GHS83].