Brief Announcement: Communication-Optimal Convex Agreement
METADATA ONLY
Loading...
Author / Producer
Date
2024-06
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
Abstract
Byzantine Agreement (BA) allows a set of n parties to agree on a value even when up to t of the parties involved are corrupted. While previous works have shown that, for ℓ-bit inputs, BA can be achieved with the optimal communication complexity Õ(ℓn) for sufficiently large ℓ, BA only ensures that honest parties agree on a meaningful output when they hold the same input, rendering the primitive inadequate for many real-world applications.
This gave rise to the notion of Convex Agreement (CA), introduced by Vaidya and Garg [PODC'13], which requires the honest parties' outputs to be in the convex hull of the honest inputs. Unfortunately, all existing CA protocols incur a communication complexity of at least Ω(ℓn2). In this work, we introduce the first CA protocol with the optimal communication of O(ℓn) bits for inputs in ℤ of size ℓ = Ω(κ · n2 log n), where κ is the security parameter.
Permanent link
Publication status
published
External links
Editor
Book title
PODC '24: Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing
Journal / series
Volume
Pages / Article No.
492 - 495
Publisher
Association for Computing Machinery
Event
43rd ACM Symposium on Principles of Distributed Computing (PODC 2024)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
convex agreement; optimal communication; long messages
Organisational unit
03604 - Wattenhofer, Roger / Wattenhofer, Roger