Optimal elections in labeled hypercubes

Paola Flocchini*, Bernard Mans

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

24 Citations (Scopus)

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 two models of Sense of Direction, which differ regarding the way the labeling of the links in the network is done: either by matching based on dimensions or by distance along a Hamiltonian cycle. In the dimension model, we give an optimal linear algorithm which uses the natural dimensional labeling of the communication links. We prove that, in the distance-based case, the graph symmetry of the hypercube is broken and, thus, the leader Election does not require a global maximum-finding algorithm: O(1) messages suffice to select the leader, whereas the Θ(N) messages are required only for the final broadcasting. Finally, we study the communication cost of changing one orientation labeling to the other and prove that O(N) messages suffice.

Original languageEnglish
Pages (from-to)76-83
Number of pages8
JournalJournal of Parallel and Distributed Computing
Volume33
Issue number1
DOIs
Publication statusPublished - 25 Feb 1996
Externally publishedYes

Fingerprint Dive into the research topics of 'Optimal elections in labeled hypercubes'. Together they form a unique fingerprint.

Cite this