OciorCOOL: Faster Byzantine Agreement and Reliable Broadcast

• URL: http://arxiv.org/abs/2409.06008v1
• Date: Mon, 9 Sep 2024 19:02:45 GMT
• Title: OciorCOOL: Faster Byzantine Agreement and Reliable Broadcast
• Authors: Jinyuan Chen,
• Abstract summary: 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.
• Score: 15.464948077412021
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: COOL (Chen'21) is an error-free and deterministic Byzantine agreement protocol that achieves consensus on an $\ell$-bit message with a communication complexity of $O(\max\{n\ell, n t \log t \})$ bits in four phases, given $n\geq 3t + 1$, for a network of $n$ nodes, where up to $t$ nodes may be dishonest. In this work we show that COOL can be optimized by reducing one communication round. The new protocol is called OciorCOOL. Additionally, building on OciorCOOL, we design an optimal reliable broadcast protocol that requires only six communication rounds.

Related papers

• 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. In our protocol design, we introduce a new primitive: asynchronous partial vector agreement (APVA)
  arXiv  Detail & Related papers  (2025-01-20T23:36:11Z)
• Asynchronous Approximate Agreement with Quadratic Communication [23.27199615640474]
  We consider an asynchronous network of $n$ message-sending parties, up to $t$ of which are byzantine. We study approximate agreement, where the parties obtain approximately equal outputs in the convex hull of their inputs. This takes $Theta(n2)$ messages per reliable broadcast, or $Theta(n3)$ messages per iteration.
  arXiv  Detail & Related papers  (2024-08-10T09:03:06Z)
• 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)
• Travelers: A scalable fair ordering BFT system [7.891481513306302]
  Most efficient BFT consensus requires $O(nTL + n2T)$ communication complexity. We propose a new system of BFT fair ordering protocols, Travelers, that substantially reduce the communication complexity.
  arXiv  Detail & Related papers  (2024-01-04T02:14:18Z)
• Communication Lower Bounds for Cryptographic Broadcast Protocols [7.233482131020069]
  Broadcast protocols enable a set of $n$ parties to agree on the input of a designated sender, even facing attacks by malicious parties. We show that any broadcast protocol within this setting can be attacked to force an arbitrary party to send messages to $k$ other parties.
  arXiv  Detail & Related papers  (2023-09-04T09:24:39Z)
• Trade-offs between Entanglement and Communication [5.88864611435337]
  We show that quantum simultaneous protocols with $tildeTheta(k5 log3 n)$ qubits of entanglement can exponentially outperform two-way randomized protocols with $O(k)$ qubits of entanglement. Prior to our work, only a relational separation was known.
  arXiv  Detail & Related papers  (2023-06-02T01:49:39Z)
• 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)
• Compression for Qubit Clocks [55.38708484314286]
  We propose a compression protocol for $n$ identically prepared states of qubit clocks. The protocol faithfully encodes the states into $(1/2)log n$ qubits and $(1/2)log n$ classical bits.
  arXiv  Detail & Related papers  (2022-09-14T09:45:53Z)
• Distributed Contextual Linear Bandits with Minimax Optimal Communication Cost [48.288452411283444]
  We study distributed contextual linear bandits with contexts, where $N$ agents act cooperatively to solve a linear bandit-optimization problem with $d$-dimensional features. We propose a distributed batch elimination version of the LinUCB algorithm, DisBE-LUCB, where the agents share information among each other through a central server. We prove that over $T$ rounds ($NT$ actions in total) the communication cost of DisBE-LUCB is only $tildemathcalO(dN)$ and its regret is at most $tildemathcalO
  arXiv  Detail & Related papers  (2022-05-26T05:56:23Z)
• SwiftAgg+: Achieving Asymptotically Optimal Communication Load in Secure Aggregation for Federated Learning [83.94234859890402]
  SwiftAgg+ is a novel secure aggregation protocol for federated learning systems. A central server aggregates local models of $NinmathbbN$ distributed users, each of size $L in mathbbN$, trained on their local data, in a privacy-preserving manner.
  arXiv  Detail & Related papers  (2022-03-24T13:12:23Z)
• 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.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.