2014 | OriginalPaper | Chapter
On Proof-Labeling Schemes versus Silent Self-stabilizing Algorithms
Authors : Lélia Blin, Pierre Fraigniaud, Boaz Patt-Shamir
Published in: Stabilization, Safety, and Security of Distributed Systems
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. 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.