Linear election for oriented hypercubes
Gérard Tel · 1993
In this article we propose an election algorithm for the oriented hypercube, where each edge is assumed to be labeled with its dimension in the hypercube. The algorithm exchanges O(N) messages and uses O(log²N) time (where N is the size of the cube). A randomized version of the algorithm achieves the same (expected) message and time bounds, but uses messages of only O(log log N) bits and can be used in anonymous hypercubes.