TY - GEN
T1 - Random leaders and random spanning trees
AU - Bar-Ilan, Judit
AU - Zernik, Dror
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1989.
PY - 1989
Y1 - 1989
N2 - The problem of distributively constructing a minimum spanning tree has been thoroughly studied. The root of this spanning tree is often elected as a leader, and then centralized algorithms are run in the distributed system. If, however, we have fault tolerance in mind, selecting a random spanning tree and a random leader are more desirable. If we manage to select a random tree, the probability that a bad channel will disconnect some nodes from the random tree is relatively small. Otherwise, a small number of predetermined edges will greatly effect the system's behavior. In this paper we present an algorithm for choosing a random leader (RL), and distributed random spanning tree algorithms (RST), where random means, that each spanning tree in the underlying graph has the same probability of being selected. We give optimal algorithms for the complete graph and the ring. We also describe an RST algorithm for the general graph, and discuss the relation between RST and RL algorithms.
AB - The problem of distributively constructing a minimum spanning tree has been thoroughly studied. The root of this spanning tree is often elected as a leader, and then centralized algorithms are run in the distributed system. If, however, we have fault tolerance in mind, selecting a random spanning tree and a random leader are more desirable. If we manage to select a random tree, the probability that a bad channel will disconnect some nodes from the random tree is relatively small. Otherwise, a small number of predetermined edges will greatly effect the system's behavior. In this paper we present an algorithm for choosing a random leader (RL), and distributed random spanning tree algorithms (RST), where random means, that each spanning tree in the underlying graph has the same probability of being selected. We give optimal algorithms for the complete graph and the ring. We also describe an RST algorithm for the general graph, and discuss the relation between RST and RL algorithms.
UR - http://www.scopus.com/inward/record.url?scp=70350666600&partnerID=8YFLogxK
U2 - 10.1007/3-540-51687-5_27
DO - 10.1007/3-540-51687-5_27
M3 - Conference contribution
AN - SCOPUS:70350666600
SN - 9783540516873
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 1
EP - 12
BT - Distributed Algorithms - 3rd International Workshop, Proceedings
A2 - Bermond, Jean-Claude
A2 - Raynal, Michel
PB - Springer Verlag
T2 - 3rd International Workshop on Distributed Algorithms, WDAG 1989
Y2 - 26 September 1989 through 28 September 1989
ER -