Redundancy in distributed proofs

Autor: Ami Paz, Mor Perry, Laurent Feuilloley, Juho Hirvonen, Pierre Fraigniaud

Publikováno v: 32nd International Symposium on Distributed Computing
32nd International Symposium on Distributed Computing, 2018, New Orleans, United States. ⟨10.4230/LIPIcs.DISC.2018.24⟩
Distributed Computing

Distributed proofs are mechanisms enabling the nodes of a network to collectivity and efficiently check the correctness of Boolean predicates on the structure of the network, or on data-structures distributed over the nodes (e.g., spanning trees or r

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::0f33d88d5962a68f3484b8d06b770ce6
https://doi.org/10.1007/s00446-020-00386-z

Relaxed and Approximate Graph Realizations

Autor: Mor Perry, Amotz Bar-Noy, Toni Böhnlein, David Peleg, Dror Rawitz

Publikováno v: Lecture Notes in Computer Science ISBN: 9783030799861
IWOCA

A network realization problem involves a given specification \(\pi \) for some network parameters (such as vertex degrees or inter-vertex distances), and requires constructing a network G that satisfies \(\pi \), if possible. In many settings, it may

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::22701c30f0007372dfd0490e9e0c1721
https://doi.org/10.1007/978-3-030-79987-8_1

Proof-Labeling Schemes: Broadcast, Unicast and In Between

Autor: Boaz Patt-Shamir, Mor Perry

We study the effect of limiting the number of different messages a node can transmit simultaneously on the verification complexity of proof-labeling schemes (PLS). In a PLS, each node is given a label, and the goal is to verify, by exchanging message

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::0cd451c0602623c05299370fa3d3ade8
http://arxiv.org/abs/1708.06947

Space-Time Tradeoffs for Distributed Verification

Autor: Mor Perry, Rafail Ostrovsky, Will Rosenbaum

Publikováno v: Structural Information and Communication Complexity ISBN: 9783319720494
SIROCCO

Verifying that a network configuration satisfies a given boolean predicate is a fundamental problem in distributed computing. Many variations of this problem have been studied, for example, in the context of proof labeling schemes (\(\mathrm {PLS}\))

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::e93ff04de01dd65478774dcc5cf2600e
https://doi.org/10.1007/978-3-319-72050-0_4