2014 | OriginalPaper | Buchkapitel
On Proof-Labeling Schemes versus Silent Self-stabilizing Algorithms
verfasst von : Lélia Blin, Pierre Fraigniaud, Boaz Patt-Shamir
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
It follows from the definition of
silent
self-stabilization, and from the definition of
proof-labeling
scheme, that if there exists a silent self-stabilizing algorithm using ℓ-bit registers for solving a task
${\mathcal{T}} $
, then there exists a proof-labeling scheme for
${\mathcal{T}} $
using registers of at most ℓ bits. The first result in this paper is the converse to this statement. We show that if there exists a proof-labeling scheme for a task
${\mathcal{T}} $
, using ℓ-bit registers, then there exists a silent self-stabilizing algorithm using registers of at most
O
(ℓ + log
n
) bits for solving
${\mathcal{T}} $
, where
n
is the number of processes in the system. Therefore, as far as memory space is concerned, the design of silent self-stabilizing algorithms essentially boils down to the design of compact proof-labeling schemes. The second result in this paper addresses time complexity. We show that, for every task
${\mathcal{T}} $
with
k
-bits output size in
n
-node networks, there exists a silent self-stabilizing algorithm solving
${\mathcal{T}} $
in
O
(
n
) rounds, using registers of
O
(
n
2
+
kn
) bits. Therefore, as far as running time is concerned,
every
task has a silent self-stabilizing algorithm converging in a linear number of rounds.