Brief Announcement: Improved Consensus in Quantum Networks

DOI10.1145/3583668.3594600arXiv2305.10618OpenAlexW4380880753WikidataQ130910804 ScholiaQ130910804MaRDI QIDQ6202264FDOQ6202264

Authors: Mohammad T. Hajiaghayi 

Publication date: 26 March 2024

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

Abstract: 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 (PODC'98) were the first who proved an absolute lower bound $Omega(sqrtn/logn)$ 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 (STOC'05) broke the $Omega(sqrtn/logn)$ 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 $Omega(sqrtn/logn)$ for classic computation).

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

zbMATH Keywords

consensusdistributed algorithmsapproximate countingquantum algorithmscrash failuresadaptive adversaryquantum common coin

Mathematics Subject Classification ID

Distributed algorithms (68W15) Distributed systems (68M14)

Cites Work

• Reaching Agreement in the Presence of Faults
• A lower bound for the time to assure interactive consistency
• Exact Quantum Algorithms for the Leader Election Problem
• Bounds on information exchange for Byzantine agreement
• Performing Work Efficiently in the Presence of Faults
• Tight bounds for asynchronous randomized consensus
• An Optimal Probabilistic Protocol for Synchronous Byzantine Agreement
• Title not available (Why is that?)
• Robust gossiping with an application to consensus
• Simple constant-time consensus protocols in realistic failure models
• Message-optimal protocols for Byzantine Agreement
• Lower bounds for distributed coin-flipping and randomized consensus
• Title not available (Why is that?)
• On the message complexity of binary Byzantine agreement under crash failures
• Fast scalable deterministic consensus for crash failures
• A tight lower bound for randomized synchronous consensus
• Communication-efficient randomized consensus
• Communication Complexity of Byzantine Agreement, Revisited
• Breaking the O ( n ² ) bit barrier
• Quantum Byzantine agreement for any number of dishonest parties
• Quantum multi-valued Byzantine agreement based on d-dimensional entangled states
• Scalable Quantum Consensus for Crash Failures

This page was built for publication: Brief Announcement: Improved Consensus in Quantum Networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6202264)