A linear algorithm for election in ring configuration networks

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.