On Proof-Labeling Schemes versus Silent Self-stabilizing Algorithms

Abstract : 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 T , then there exists a proof-labeling scheme for 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 T , using ℓ-bit registers, then there exists a silent self-stabilizing algorithm using registers of at most O(ℓ + logn) bits for solving 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 T with k-bits output size in n-node networks, there exists a silent self-stabilizing algorithm solving 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.
Type de document :
Communication dans un congrès
Pascal Felber; Vijay Garg. SSS 2014 - 16th International Symposium on Stabilization, Safety, and Security of Distributed Systems, Sep 2014, Paderborn, Germany. Springer, 8756, pp.18-32, LNCS - Lecture Notes in Computer Science. 〈10.1007/978-3-319-11764-5_2〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01102123
Contributeur : Pierre Fraigniaud <>
Soumis le : lundi 12 janvier 2015 - 10:31:55
Dernière modification le : mercredi 28 novembre 2018 - 01:26:05

Identifiants

Citation

Lélia Blin, Pierre Fraigniaud, Boaz Patt-Shamir. On Proof-Labeling Schemes versus Silent Self-stabilizing Algorithms. Pascal Felber; Vijay Garg. SSS 2014 - 16th International Symposium on Stabilization, Safety, and Security of Distributed Systems, Sep 2014, Paderborn, Germany. Springer, 8756, pp.18-32, LNCS - Lecture Notes in Computer Science. 〈10.1007/978-3-319-11764-5_2〉. 〈hal-01102123〉

Partager

Métriques

Consultations de la notice

433