Self-Stabilizing Byzantine Asynchronous Unison

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

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2009-12
Main Authors: Swan Dubois, Potop-Butucaru, Maria Gradinariu, Nesterenko, Mikhail, Tixeuil, Sébastien
Format: Article
Language:English
Subjects:
Algorithms
Containment
Rings (mathematics)
Topology
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422