Randomized Proof-Labeling Schemes

Abstract : A proof-labeling scheme, introduced by Korman, Kutten and Peleg [PODC 2005], is a mechanism enabling to certify the legality of a network configuration with respect to a boolean predicate. Such a mechanism finds applications in many frameworks, including the design of fault-tolerant distributed algorithms. In a proof-labeling scheme, the verification phase consists of exchanging labels between neighbors. The size of these labels depends on the network predicate to be checked. There are predicates requiring large labels, of poly-logarithmic size (e.g., MST), or even polynomial size (e.g., Symmetry). In this paper, we introduce the notion of randomized proof-labeling schemes. By reduction from deterministic schemes, we show that randomization enables the amount of communication to be exponentially reduced. As a consequence, we show that checking any network predicate can be done with probability of correctness as close to one as desired by exchanging just a logarithmic number of bits between neighbors. Moreover, we design a novel space lower bound technique that applies to both deterministic and randomized proof-labeling schemes. Using this technique, we establish several tight bounds on the verification complexity of classical distributed computing problems, such as MST construction, and of classical predicates such as acyclicity, connectivity, and cycle length.
Type de document :
Communication dans un congrès
ACM Symposium on Principles of Distributed Computing (PODC), Jul 2015, Donostia-San Sebastián, Spain. ACM, pp.315-324, 2015, 〈10.1145/2767386.2767421〉
Liste complète des métadonnées

Littérature citée [43 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01247352
Contributeur : Pierre Fraigniaud <>
Soumis le : lundi 21 décembre 2015 - 17:34:05
Dernière modification le : mardi 17 avril 2018 - 11:26:37
Document(s) archivé(s) le : mardi 22 mars 2016 - 13:30:28

Fichier

podc9.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Mor Baruch, Pierre Fraigniaud, Boaz Patt-Shamir. Randomized Proof-Labeling Schemes. ACM Symposium on Principles of Distributed Computing (PODC), Jul 2015, Donostia-San Sebastián, Spain. ACM, pp.315-324, 2015, 〈10.1145/2767386.2767421〉. 〈hal-01247352〉

Partager

Métriques

Consultations de la notice

285

Téléchargements de fichiers

134