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
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;
Conference_Titel :
System Sciences, 1991. Proceedings of the Twenty-Fourth Annual Hawaii International Conference on
Conference_Location :
Kauai, HI
DOI :
10.1109/HICSS.1991.183877