TY - GEN
T1 - Brief Announcement
T2 - 42nd ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2023
AU - Hajiaghayi, Mohammadtaghi
AU - Kowalski, Dariusz Rafal
AU - Olkowski, Jan
N1 - Publisher Copyright:
© 2023 ACM.
PY - 2023/6/19
Y1 - 2023/6/19
N2 - Fault-tolerant consensus is about reaching agreement on some of the input values in a limited time by non-faulty autonomous processes, despite of failures of processes or communication medium. This problem is particularly challenging and costly against an adaptive adversary with full information. Bar-Joseph and Ben-Or [7] (PODC'98) were the first who proved an absolute lower bound [EQUATION] on expected time complexity of consensus in any classic (i.e., randomized or deterministic) message-passing network with n processes succeeding with probability 1 against such a strong adaptive adversary crashing processes.Seminal work of Ben-Or and Hassidim [8] (STOC'05) broke the [EQUATION] barrier for consensus in classic (deterministic and randomized) networks by employing quantum computing. They showed an (expected) constant-time quantum algorithm for a linear number of crashes t < n/3.In this paper, we improve upon that seminal work by reducing the number of quantum and communication bits to an arbitrarily small polynomial, and even more, to a polylogarithmic number - though, the latter in the cost of a slightly larger polylogarithmic time (still exponentially smaller than the time lower bound [EQUATION] for classic computation).∗
AB - Fault-tolerant consensus is about reaching agreement on some of the input values in a limited time by non-faulty autonomous processes, despite of failures of processes or communication medium. This problem is particularly challenging and costly against an adaptive adversary with full information. Bar-Joseph and Ben-Or [7] (PODC'98) were the first who proved an absolute lower bound [EQUATION] on expected time complexity of consensus in any classic (i.e., randomized or deterministic) message-passing network with n processes succeeding with probability 1 against such a strong adaptive adversary crashing processes.Seminal work of Ben-Or and Hassidim [8] (STOC'05) broke the [EQUATION] barrier for consensus in classic (deterministic and randomized) networks by employing quantum computing. They showed an (expected) constant-time quantum algorithm for a linear number of crashes t < n/3.In this paper, we improve upon that seminal work by reducing the number of quantum and communication bits to an arbitrarily small polynomial, and even more, to a polylogarithmic number - though, the latter in the cost of a slightly larger polylogarithmic time (still exponentially smaller than the time lower bound [EQUATION] for classic computation).∗
KW - adaptive adversary
KW - approximate counting
KW - consensus
KW - crash failures
KW - distributed algorithms
KW - quantum algorithms
KW - quantum common coin
UR - http://www.scopus.com/inward/record.url?scp=85163928107&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85163928107&partnerID=8YFLogxK
U2 - 10.1145/3583668.3594600
DO - 10.1145/3583668.3594600
M3 - Conference contribution
AN - SCOPUS:85163928107
T3 - Proceedings of the Annual ACM Symposium on Principles of Distributed Computing
SP - 286
EP - 289
BT - PODC 2023 - Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing
PB - Association for Computing Machinery
Y2 - 19 June 2023 through 23 June 2023
ER -