CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

When consensus meets self-stabilization

S. Dolev ; R. I. Kat ; Elad Michael Schiller (Institutionen för data- och informationsteknik, Nätverk och system (Chalmers) )
Journal of Computer and System Sciences (0022-0000). Vol. 76 (2010), 8, p. 884-900.
[Artikel, refereegranskad vetenskaplig]

This paper presents a shared-memory self-stabilizing failure detector, asynchronous consensus and replicated state-machine algorithm suite, the components of which can be started in an arbitrary state and converge to act as a virtual state-machine. Self-stabilizing algorithms can cope with transient faults. Transient faults can alter the system state to an arbitrary state and hence, cause a temporary violation of the safety property of the consensus. Started in an arbitrary state, the long lived, memory bounded and self-stabilizing failure detector, asynchronous consensus, and replicated state-machine suite, presented in the paper, recovers to satisfy eventual safety and eventual liveness requirements. Several new techniques and paradigms are introduced. The bounded memory failure detector abstracts away synchronization assumptions using bounded heartbeat counters combined with a balance-unbalance mechanism. The practically infinite paradigm is introduced in the scope of self-stabilization, where an execution of, say, 2(64) sequential steps is regarded as (practically) infinite. Finally, we present the first self-stabilizing wait-free reset mechanism that ensures eventual safety and can be used to implement efficient self-stabilizing timestamps that are of independent interest. (C) 2010 Elsevier Inc. All rights reserved.

Nyckelord: Failure detector, Consensus, State-machine, Wait-free, Distributed, reset, Self-stabilization, failure detectors, systems, impossibility, time

Denna post skapades 2010-09-20. Senast ändrad 2014-11-10.
CPL Pubid: 126591


Läs direkt!

Länk till annan sajt (kan kräva inloggning)

Institutioner (Chalmers)

Institutionen för data- och informationsteknik, Nätverk och system (Chalmers)


Information Technology

Chalmers infrastruktur