A synod based deterministic and indulgent leader election protocol for asynchronous large groups. Issue 2 (4th March 2022)

• Record Type: Journal Article
• Authors: Srinivasan, Sathyanarayanan; kandukoori, Ramesh
• Is Part Of: International journal of parallel, emergent and distributed systems. Volume 37:Issue 2(2022)
• Page Start: 220
• Page End: 247
• Publication Date: 2022-03-04
• Subjects: Leader election -- deterministic algorithms -- indulgent algorithms -- synod -- Paxos -- wireless sensor networks and internet of things; Parallel computers -- Periodicals; Electronic data processing -- Distributed processing -- Periodicals; Computer algorithms -- Periodicals; 004.35
• DOI: 10.1080/17445760.2021.1879067
• Languages: English
• ISSNs: 1744-5760

Abstract

ABSTRACT: This paper presents a deterministic and indulgent algorithm for leader election. Our algorithm is adapted to large-scale systems with the primary objective of faster execution time to elect a leader. We modify the single-decree Paxos consensus (Synod) algorithm such that proposers proposing the same value do not conflict with each other. Although any process in the system can initiate election, we restrict the decision making on electing the leader to a select set of processes A, called acceptors. For a given k ( = A ) acceptors in the system, our algorithm can tolerate up to f = ⌈ k 2 − 1 ⌉ failures in A, and any number of process failures outside A . The restriction on decision making allows our algorithm to scale without compromising on performance. Experimental results show that our algorithm is faster to elect a leader than existing algorithms which are optimised for large-scale systems. We also adapt our algorithm for leader election in Wireless Sensor Networks (WSNs) and Internet of Things (IoTs) and show that it performs better than the existing graph-based techniques employed in these systems. GRAPHICAL ABSTRACT: UF0001