Self-stabilizing Byzantine Asynchronous Unison

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

1 Regal - Large-Scale Distributed Systems and Applications
2 Department of computer science
3 NPA - Networks and Performance Analysis
4 IUF - Institut universitaire de France
5 GRAND-LARGE - Global parallel and distributed computing

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 less than strongly fair scheduler or for system topologies with maximum node degree greater than two. We present a self-stabilizing Byzantine-tolerant solution to asynchronous unison for chain and ring topologies. Our algorithm has minimum possible containment radius and optimal stabilization time.

Domaines: Calcul parallèle, distribué et partagé [cs.DC]

Swan Dubois, Maria Gradinariu Potop-Butucaru, Mikhail Nesterenko, Sébastien Tixeuil. Self-stabilizing Byzantine Asynchronous Unison. OPODIS 2010 - 14th International Conference On Principles Of DIstributed Systems, Dec 2010, Tozeur, Tunisia. pp.83-86, ⟨10.1007/978-3-642-17653-1_7⟩. ⟨inria-00627771⟩