Title: Specifying and implementing an eventual leader service for dynamic systems

Authors: Mikel Larrea; Michel Raynal; Iratxe Soraluze; Roberto Cortiñas

Addresses: Computer Science Faculty, University of the Basque Country UPV/EHU, Lardizabal, 1, San Sebastian 20018, Spain. ' Institut Universitaire de France, IRISA, Campus de Beaulieu, 35042 Rennes, France. ' Computer Science Faculty, University of the Basque Country UPV/EHU, Lardizabal, 1, San Sebastian 20018, Spain. ' Computer Science Faculty, University of the Basque Country UPV/EHU, Lardizabal, 1, San Sebastian 20018, Spain

Abstract: The election of an eventual leader in an asynchronous system prone to process crashes is an important problem of fault-tolerant distributed computing. This problem is known as the implementation of the failure detector Ω. Nearly all papers that propose algorithms implementing such an eventual leader service consider a static system. In contrast this paper considers a dynamic system, i.e. a system in which processes can join and leave. The paper has three main contributions. It first proposes a specification of Ω suited to dynamic systems. Then, it presents and proves correct two algorithms implementing this specification. Finally, the paper discusses the notion of an eventual leader suited to dynamic systems. It introduces an additional property related to system stability. The design of an algorithm satisfying this last property remains an open challenging problem.

Keywords: asynchronous systems; distributed computing; dynamic systems; eventual leader; failure detection; fault tolerance; omega; partial synchrony; process crashes; system modelling; timely links; system stability.

DOI: 10.1504/IJWGS.2012.049167

International Journal of Web and Grid Services, 2012 Vol.8 No.3, pp.204 - 224

Published online: 31 Dec 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article