HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

Randomized proof-labeling schemes

Abstract : Proof-labeling schemes, introduced by Korman et al. (Distrib Comput 22(4):215–233, 2010. https://doi.org/10.1007/s00446-010-0095-3), are a mechanism to certify that a network configuration satisfies a given boolean predicate. Such mechanisms find applications in many contexts, e.g., the design of fault-tolerant distributed algorithms. In a proof-labeling scheme, predicate verification consists of neighbors exchanging labels, whose contents depends on the predicate. In this paper, we introduce the notion of randomized proof-labeling schemes where messages are randomized and correctness is probabilistic. We show that randomization reduces verification complexity exponentially while guaranteeing probability of correctness arbitrarily close to one. We also present a novel message-size lower bound technique that applies to deterministic as well as randomized proof-labeling schemes. Using this technique, we establish several tight bounds on the verification complexity of MST, acyclicity, connectivity, and longest cycle size.
Complete list of metadata

https://hal.inria.fr/hal-02433478
Contributor : Pierre Fraigniaud Connect in order to contact the contributor
Submitted on : Thursday, January 9, 2020 - 10:33:29 AM
Last modification on : Thursday, February 3, 2022 - 11:18:23 AM

Identifiers

Citation

Pierre Fraigniaud, Boaz Patt-Shamir, Mor Perry. Randomized proof-labeling schemes. Distributed Computing, Springer Verlag, 2019, 32 (3), pp.217-234. ⟨10.1007/s00446-018-0340-8⟩. ⟨hal-02433478⟩

Share

Metrics

Record views

19