Title: Self-stabilising protocols on oriented chains with joins and leaves

Authors: Doina Bein; Hirotsugu Kakugawa; Toshimitsu Masuzawa

Addresses: Applied Research Laboratory, The Pennsylvania State University, USA ' Graduate School of Information Science and Technology, Osaka University, Japan ' Graduate School of Information Science and Technology, Osaka University, Japan

Abstract: A key problem in designing self-stabilising algorithm is to minimise the stabilisation time (also called convergence time), that is, the maximum time necessary to bring a system into a legitimate configuration after an arbitrary initialisation or after a fault; this process is called stabilisation. Except for Masuzawa and Kakugawa (2005); Nakaminami et al. (2006), it was always measured either from the initial configuration or the configuration after the fault. When a fault has only a local effect, this measure overestimates the time to stabilise, since a system may recover much faster after a fault than after an arbitrary initialisation. We measure the stabilisation time only from the initial configuration. We show the efficiency of this measure that includes as parameter the number of faults, for a consensus algorithm on an oriented chain where processes can join or leave at will.

Keywords: distributed systems; self-stabilisation; synchronisation; convergence time; stabilisation time; consensus algorithms; oriented chains; arbitrary initialisation; transient faults; round; locally shared memory models; legitimate configuration.

DOI: 10.1504/IJAACS.2012.046284

International Journal of Autonomous and Adaptive Communications Systems, 2012 Vol.5 No.2, pp.178 - 199

Published online: 05 Dec 2014 *

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