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

When Consensus Meets Self-stabilization

Shlomi Dolev ; Ronen I. Kat ; Elad Michael Schiller (Institutionen för data- och informationsteknik, Datavetenskap, Datakommunikation och distribuerade system (Chalmers))
OPODIS / Alexander A. Shvartsman Vol. 4305 (2006), p. 45-63.
[Konferensbidrag, refereegranskat]

This paper presents a 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. New requirements for consensus that fit the on-going nature of self-stabilizing algorithms are presented. The wait-free consensus (and the replicated state-machine) algorithm presented is a classic combination of a failure detector and a (memory bounded) rotating coordinator consensus that satisfy both eventual safety and eventual liveness. 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, 264 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 in other scopes.

Nyckelord: Failure Detector, Consensus, State-Machine, Wait-Free, Distributed Reset, Self-Stabilization

Denna post skapades 2007-01-15. Senast ändrad 2014-11-10.
CPL Pubid: 25164


Institutioner (Chalmers)

Institutionen för data- och informationsteknik, Datavetenskap, Datakommunikation och distribuerade system (Chalmers) (2005-2007)



Chalmers infrastruktur