DocumentCode :
279073
Title :
A linear algorithm for election in ring configuration networks
Author :
El-Ruby, M. ; Kenevan, J. ; Carlson, R. ; Khalil, K.
Author_Institution :
IBM Santa Teresa Lab., San Jose, CA, USA
Volume :
i
fYear :
1991
fDate :
8-11 Jan 1991
Firstpage :
117
Abstract :
After a failure occurs in a distributed computing system, it is often necessary to reorganize the active nodes so that they can continue to perform a useful task. The first step in such a reorganization or reconfiguration is to elect a coordinator to manage the operation. The paper introduces a new and simple election algorithm that works in both synchronous and asynchronous rings. The best previous deterministic algorithms for a synchronous ring used O(n) messages and O(n2i) time in the worst case, where i is the ID of the elected coordinator. For asynchronous rings, the best result achieved was O(n log n) messages. The algorithm has been analyzed using both analytical techniques and simulation modeling. The performance evaluation shows that it requires O(n) messages and O(n ) time in the worst case, a potentially significant improvement for large rings
Keywords :
computational complexity; distributed processing; asynchronous rings; distributed computing system; election algorithm; performance evaluation; ring configuration networks; synchronous ring; Algorithm design and analysis; Analytical models; Computational modeling; Concrete; Distributed computing; Intelligent networks; Laboratories; Nominations and elections; Partitioning algorithms; Resumes;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
System Sciences, 1991. Proceedings of the Twenty-Fourth Annual Hawaii International Conference on
Conference_Location :
Kauai, HI
Type :
conf
DOI :
10.1109/HICSS.1991.183877
Filename :
183877
Link To Document :
بازگشت