Related papers: COOL Is Optimal in Error-Free Asynchronous Byzantine Agreement

COOL Is Optimal in Error-Free Asynchronous Byzantine Agreement

URL: http://arxiv.org/abs/2511.00263v1
Date: Fri, 31 Oct 2025 21:23:55 GMT
Title: COOL Is Optimal in Error-Free Asynchronous Byzantine Agreement
Authors: Jinyuan Chen,
Abstract summary: adaptive variant of COOL achieves error-free, information-theoretically secure BA consensus in the asynchronous setting.<n>OciorACOOL retains the same low-complexity, traditional $(n, k)$ error-correction encoding and decoding as COOL, with $k=t/3$.
Score: 5.48253258922555
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: COOL (Chen'21) is an error-free, information-theoretically secure Byzantine agreement (BA) protocol proven to achieve BA consensus in the synchronous setting for an $\ell$-bit message, with a total communication complexity of $O(\max\{n\ell, nt \log q\})$ bits, four communication rounds in the worst case, and a single invocation of a binary BA, under the optimal resilience assumption $n \geq 3t + 1$ in a network of $n$ nodes, where up to $t$ nodes may behave dishonestly. Here, $q$ denotes the alphabet size of the error correction code used in the protocol. In this work, we present an adaptive variant of COOL, called OciorACOOL, which achieves error-free, information-theoretically secure BA consensus in the asynchronous setting with total $O(\max\{n\ell, n t \log q\})$ communication bits, $O(1)$ rounds, and a single invocation of an asynchronous binary BA protocol, still under the optimal resilience assumption $n \geq 3t + 1$. Moreover, OciorACOOL retains the same low-complexity, traditional $(n, k)$ error-correction encoding and decoding as COOL, with $k=t/3$.

Related papers

Extending Asynchronous Byzantine Agreement with Crusader Agreement [23.27199615640474]
We present a new reduction from multivalued BA to binary BA.<n>As our reduction uses multivalued CA, we also design two new information-theoretic CA protocols for $ell$-bit inputs.
arXiv Detail & Related papers (2025-02-04T13:44:41Z)
OciorABA: Improved Error-Free Asynchronous Byzantine Agreement via Partial Vector Agreement [15.464948077412021]
We propose an error-free, information-theoretically secure multi-valued asynchronous Byzantine agreement protocol, called OciorABA.<n>In our protocol design, we introduce a new primitive: asynchronous partial vector agreement (APVA)
arXiv Detail & Related papers (2025-01-20T23:36:11Z)
OciorMVBA: Near-Optimal Error-Free Asynchronous MVBA [15.464948077412021]
We propose an error-free, information-theoretically secure, asynchronous multi-valued validated Byzantine agreement (MVBA) protocol, called OciorMVBA.<n>We also propose another error-free, IT-secure, asynchronous MVBA protocol, called OciorMVBArr.
arXiv Detail & Related papers (2024-12-31T01:30:24Z)
OciorCOOL: Faster Byzantine Agreement and Reliable Broadcast [15.464948077412021]
COOL (Chen'21) is an error-free and deterministic Byzantine agreement protocol. OciorCOOL can be optimized by reducing one communication round. Building on Ocior, we design an optimal reliable broadcast protocol that requires only six communication rounds.
arXiv Detail & Related papers (2024-09-09T19:02:45Z)
Federated Combinatorial Multi-Agent Multi-Armed Bandits [79.1700188160944]
This paper introduces a federated learning framework tailored for online optimization with bandit. In this setting, agents subsets of arms, observe noisy rewards for these subsets without accessing individual arm information, and can cooperate and share information at specific intervals.
arXiv Detail & Related papers (2024-05-09T17:40:09Z)
Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages [63.366380571397]
We study the problem of private vector mean estimation in the shuffle model of privacy where $n$ users each have a unit vector $v(i) inmathbbRd$. We propose a new multi-message protocol that achieves the optimal error using $tildemathcalOleft(min(nvarepsilon2,d)right)$ messages per user.
arXiv Detail & Related papers (2024-04-16T00:56:36Z)
Federated Contextual Cascading Bandits with Asynchronous Communication and Heterogeneous Users [95.77678166036561]
We propose a UCB-type algorithm with delicate communication protocols. We give sub-linear regret bounds on par with those achieved in the synchronous framework. Empirical evaluation on synthetic and real-world datasets validates our algorithm's superior performance in terms of regrets and communication costs.
arXiv Detail & Related papers (2024-02-26T05:31:14Z)
Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximation [77.09836892653176]
We study multi-agent reinforcement learning in the setting of episodic Markov decision processes. We propose a provably efficient algorithm based on value that enable asynchronous communication. We show that a minimal $Omega(dM)$ communication complexity is required to improve the performance through collaboration.
arXiv Detail & Related papers (2023-05-10T20:29:29Z)
A Simple and Provably Efficient Algorithm for Asynchronous Federated Contextual Linear Bandits [77.09836892653176]
We study federated contextual linear bandits, where $M$ agents cooperate with each other to solve a global contextual linear bandit problem with the help of a central server. We consider the asynchronous setting, where all agents work independently and the communication between one agent and the server will not trigger other agents' communication. We prove that the regret of textttFedLinUCB is bounded by $tildeO(dsqrtsum_m=1M T_m)$ and the communication complexity is $tildeO(dM
arXiv Detail & Related papers (2022-07-07T06:16:19Z)
On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
We study the setup where each of $n$ users holds an element from a discrete set. The goal is to count the number of distinct elements across all users.
arXiv Detail & Related papers (2020-09-21T04:13:34Z)

This list is automatically generated from the titles and abstracts of the papers in this site.