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.
Complete list of metadatas

Cited literature [43 references]  Display  Hide  Download

https://hal.inria.fr/hal-01247352
Contributor : Pierre Fraigniaud <>
Submitted on : Monday, December 21, 2015 - 5:34:05 PM
Last modification on : Friday, January 4, 2019 - 5:33:21 PM
Long-term archiving on : Tuesday, March 22, 2016 - 1:30:28 PM

File

podc9.pdf
Files produced by the author(s)

Identifiers

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

Share

Metrics

Record views

776

Files downloads

370