Randomized fault-detecting leader election in a bi-directional ring

Author

Wagner, Neal R.

Author_Institution

Div. of Math., Comput. Sci. & Stat., Texas Univ., San Antonio, TX, USA

fYear

1990

fDate

9-13 Dec 1990

Firstpage

506

Lastpage

510

Abstract

The article particle presents a randomized algorithm for leader election which uses bi-directionality of an asynchronous ring to force a node to `commit´ to a coin flip by sending it in both directions. The algorithm is fault-detecting in a strong sense: it works if and only if there is a connected segment of [n/2]+1 non-faulty processors (n=ringsize). Faulty processors may do anything to disrupt the algorithm-even communicate outside the ring and cooperate. The algorithm guarantees that each non-faulty processor in the segment either has probability 1/n of being elected leader or will receive a fault message

Keywords

fault tolerant computing; multiprocessor interconnection networks; probability; protocols; asynchronous ring; bi-directional ring; bi-directionality; bidirectional ring; coin flip; fault detection; fault tolerance; leader election; probability; protocols; randomized algorithm; Bidirectional control; Clocks; Computer science; Fault detection; Gold; Mathematics; Nominations and elections; Protocols; Statistics;

fLanguage

English

Publisher

ieee

Conference_Titel

Parallel and Distributed Processing, 1990. Proceedings of the Second IEEE Symposium on

Conference_Location

Dallas, TX

Print_ISBN

0-8186-2087-0

Type

conf

DOI

10.1109/SPDP.1990.143593

Filename

143593