Space-time tradeoffs for distributed verification

DOI10.1007/978-3-319-72050-0_4zbMath1496.68042arXiv1605.06814OpenAlexW2963176286MaRDI QIDQ1742756

Rafail Ostrovsky, Will Rosenbaum, Mor Perry, Mor Baruch

Publication date: 12 April 2018

Published in: Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1605.06814

zbMATH Keywords

distributed algorithmsproof labeling schemesspace-time tradeoffs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Network design and communication in computer systems (68M10) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Graph theory (including graph drawing) in computer science (68R10) Specification and verification (program logics, model checking, etc.) (68Q60) Distributed systems (68M14) Distributed algorithms (68W15) Communication complexity, information complexity (68Q11)

Related Items (9)

Proof-labeling schemes: broadcast, unicast and in between ⋮ Lower bound for constant-size local certification ⋮ A hierarchy of local decision ⋮ Randomized proof-labeling schemes ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Redundancy in distributed proofs ⋮ Approximate proof-labeling schemes ⋮ Introduction to local certification

This page was built for publication: Space-time tradeoffs for distributed verification