Verimag

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 $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.

Contact | Site Map | Site powered by SPIP 3.0.25 + AHUNTSIC [CC License]

info visites 776231