2014 | OriginalPaper | Buchkapitel
Edge Coloring Despite Transient and Permanent Faults
verfasst von : Alexandre Maurer, Toshimitsu Masuzawa
Erschienen in: Stabilization, Safety, and Security of Distributed Systems
Verlag: Springer International Publishing
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We consider the problem of edge coloring in the presence of transient and permanent faults: we must achieve a stable edge coloring despite any initial state, and despite an unbounded number of Byzantine nodes. In this paper, we consider that no local variable is allowed: we only use the colors of the edges. We give a general algorithm to achieve edge coloring at distance 2 of Byzantine failures. Then, we give a Byzantine insensitive algorithm for edge coloring on a ring (we achieve a stable coloring on the correct subgraph).