Skip to Main content Skip to Navigation
New interface
Conference papers

Randomized Proof-Labeling Schemes

Mor Baruch 1 Pierre Fraigniaud 2, 3 Boaz Patt-Shamir 1 
3 GANG - Networks, Graphs and Algorithms
LIAFA - Laboratoire d'informatique Algorithmique : Fondements et Applications, Inria Paris-Rocquencourt
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.
Complete list of metadata

Cited literature [43 references]  Display  Hide  Download
Contributor : Pierre Fraigniaud Connect in order to contact the contributor
Submitted on : Monday, December 21, 2015 - 5:34:05 PM
Last modification on : Tuesday, October 25, 2022 - 4:21:56 PM
Long-term archiving on: : Tuesday, March 22, 2016 - 1:30:28 PM


Files produced by the author(s)




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. pp.315-324, ⟨10.1145/2767386.2767421⟩. ⟨hal-01247352⟩



Record views


Files downloads