Name
Abstract | ||
|---|---|---|
In a PODC 2008 paper, Helm proposed a protocol for solving distributed consensus using quantum techniques, and without exchanging messages in the classical sense. In this protocol, entangled qubits are distributed to the participants at initialization. Each participant then measures its qubit, and outputs a binary value determined by the outcome of the binary measurement. Since Helm's protocol does not provide the essential properties of consensus (agreement and validity) deterministically, we pose the following question: does this quantum protocol offer any advantage at all over classical protocols that provide similar non-deterministic guarantees? We answer this question in the negative by proving an inherent trade-off between the probability of achieving agreement and the probability of achieving validity in the absence of communication. Our result applies to both classical and quantum protocols.
|
Year | DOI | Venue |
|---|---|---|
2020 | 10.1145/3350755.3400215 | SPAA '20: 32nd ACM Symposium on Parallelism in Algorithms and Architectures
Virtual Event
USA
July, 2020 |
DocType | ISBN | Citations |
Conference | 978-1-4503-6935-0 | 0 |
PageRank | References | Authors |
0.34 | 0 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Wojciech Golab | 1 | 0 | 0.34 |
| Hao Tan | 2 | 0 | 0.68 |