Skip navigation

A robust tri-state election algorithm for scalable applications

A robust tri-state election algorithm for scalable applications

Anthony, R.J. (2003) A robust tri-state election algorithm for scalable applications. In: Applied Informatics (AI 2003). Proceeding (378). ACTA Press, Calgary, Alberta, Canada. ISBN 0889863415 ISSN 1027-2666

Full text not available from this repository.


Existing election algorithms suffer limited scalability. This limit stems from the communication design which in turn stems from their fundamentally two-state behaviour. This paper presents a new election algorithm specifically designed to be highly scalable in broadcast networks whilst allowing any processing node to become coordinator with initially equal probability. To achieve this, careful attention has been paid to the communication design, and an additional state has been introduced. The design of the tri-state election algorithm has been motivated by the requirements analysis of a major research project to deliver robust scalable distributed applications, including load sharing, in hostile computing environments in which it is common for processing nodes to be rebooted frequently without notice. The new election algorithm is based in-part on a simple 'emergent' design. The science of emergence is of great relevance to developers of distributed applications because it describes how higher-level self-regulatory behaviour can arise from many participants following a small set of simple rules. The tri-state election algorithm is shown to have very low communication complexity in which the number of messages generated remains loosely-bounded regardless of scale for large systems; is highly scalable because nodes in the idle state do not transmit any messages; and because of its self-organising characteristics, is very stable.

Item Type: Conference Proceedings
Title of Proceedings: Applied Informatics (AI 2003)
Additional Information: [1] This paper was first presented at the 21st IASTED International Conference on Applied Informatics (AI 2003) held from 10-13 February 2003 in Innsbruck, Austria. It was given within the Fault Tolerance track. [2] ISBN: 0-88986-341-5 (CD). [3] Proceeding-Track No: 378-255.
Uncontrolled Keywords: election algorithm, scalability, fault tolerance, emergence
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Pre-2014 Departments: School of Computing & Mathematical Sciences
School of Computing & Mathematical Sciences > Computer & Computational Science Research Group
School of Computing & Mathematical Sciences > Department of Computer Systems Technology
Related URLs:
Last Modified: 14 Oct 2016 09:01

Actions (login required)

View Item View Item