Self-stabilizing byzantine asynchronous unison

Swan Dubois (1) , Maria Potop-Butucaru (2) , Mikhail Nesterenko (3) , Sébastien Tixeuil (4, 5, 2)

1 Regal - Large-Scale Distributed Systems and Applications
2 NPA - Networks and Performance Analysis
3 Department of computer science
4 IUF - Institut universitaire de France
5 LINCS - Laboratory of Information, Network and Communication Sciences

We explore asynchronous unison in the presence of systemic transient and permanent Byzantine faults in shared memory. We observe that the problem is not solvable under a less than strongly fair scheduler or for system topologies with maximum node degree greater than two. We present then a self-stabilizing Byzantine-tolerant solution to asynchronous unison for chain and ring topologies under the central strongly fair daemon. Our algorithm has minimum possible containment radius and optimal stabilization time.

Mots clés: Self-stabilization; Byzantine containment; Strict stabilization; Unison; Clock synchronization

Domaines: Algorithme et structure de données [cs.DS]; Calcul parallèle, distribué et partagé [cs.DC]; Réseaux et télécommunications [cs.NI]; Performance et fiabilité [cs.PF]; Informatique ubiquitaire

Swan Dubois, Maria Potop-Butucaru, Mikhail Nesterenko, Sébastien Tixeuil. Self-stabilizing byzantine asynchronous unison. Journal of Parallel and Distributed Computing, 2012, 72 (7), pp.917-923. ⟨10.1016/j.jpdc.2012.04.001⟩. ⟨hal-00934022⟩