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 $n\ge 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.
