Optimal Elections in Labeled Hypercubes |
| |
| Affiliation: | 1. CHArt Laboratory, Université Paris 8 Vincennes - Saint Denis, 2 Rue de la Liberté, Saint-Denis 93526, France;2. Department of Child and Adolescent Psychiatry, Groupe Hospitalier Pitié-Salpêtriére, 47 bd. de l’Hôpital, Paris 75013, France;3. Institute of Intelligent Systems and Robotics, Université Pierre et Marie Curie, 4 place Jussieu, Paris 75005, France;4. Equipes traitement de l’information et systémes (ETIS), Université de Cergy-Pontoise, 33, bvd. du Port, Cergy 95014, France;5. Institute of Clinical Physiology, National Research Council, Via Moruzzi 1, Pisa 56124, Italia;6. Fondazione Stella Maris, Viale del Tirreno, 331, Calambrone, Pisa 56018, Italy;1. School of Earth and Environmental Sciences, University of Manchester, Oxford Road, Manchester, M139PL, UK;2. Geological Survey of Japan, AIST, 1-1-1 Higashi, Tsukuba, Ibaraki 305-8567, Japan |
| |
| Abstract: | We study the message complexity of theElectionProblem 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 thatO(N) messages suffice. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
