Technical Reports

Ajoy K. Datta, St'ephane Devismes, Lawrence L. Larmore, S'ebastien Tixeuil
Fast Leader (Full) Recovery despite Dynamic Faults (2012)

TR-2012-18.pdf


Keywords: self-stabilization, $k$-stabilization, leader election, leader recovery

Abstract: In this paper, we give a leader recovery protocol, lek, that recovers a legitimate configuration where a single leader exists, after at most $k$ memory corruption faults hit the system in an arbitrary manner. That is, if a leader $ell$ is elected before state corruption, the emph{same} leader is elected after recovery. Our protocol works for an anonymous bidirectional, yet oriented, ring of size $n$, and does emph{not} require that processes know $n$, although the knowledge of $k$ is assumed. If $nge 18k+1$, our protocol recovers the leader in $O(k^malytwo)$ rounds using $O(log k)$ bits per process, assuming unfair scheduling. Our protocol handles emph{dynamic} faults in the sense that the $k$ memory corruption faults may occur while the network has started recovering the leader.

Contact | Plan du site | Site réalisé avec SPIP 4.2.8 + AHUNTSIC [CC License]

info visites 3945246