Ajoy K. Datta,
St'ephane Devismes,
Lawrence L. Larmore,
S'ebastien Tixeuil
Fast Leader (Full) Recovery despite Dynamic Faults (2012)
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.
