Related papers: OciorABA: Improved Error-Free Asynchronous Byzantine Agreement via Partial Vector Agreement

OciorABA: Improved Error-Free Asynchronous Byzantine Agreement via Partial Vector Agreement

URL: http://arxiv.org/abs/2501.11788v2
Date: Sat, 25 Jan 2025 04:27:12 GMT
Title: OciorABA: Improved Error-Free Asynchronous Byzantine Agreement via Partial Vector Agreement
Authors: Jinyuan Chen,
Abstract summary: 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)
Score: 15.464948077412021
License:
Abstract: In this work, we propose an error-free, information-theoretically secure multi-valued asynchronous Byzantine agreement (ABA) protocol, called OciorABA. This protocol achieves ABA consensus on an $\ell$-bit message with an expected communication complexity of $O(n\ell + n^3 \log q )$ bits and an expected round complexity of $O(1)$ rounds, under the optimal resilience condition $n \geq 3t + 1$ in an $n$-node network, where up to $t$ nodes may be dishonest. Here, $q$ denotes the alphabet size of the error correction code used in the protocol. In our protocol design, we introduce a new primitive: asynchronous partial vector agreement (APVA). In APVA, the distributed nodes input their vectors and aim to output a common vector, where some of the elements of those vectors may be missing or unknown. We propose an APVA protocol with an expected communication complexity of $O( n^3 \log q )$ bits and an expected round complexity of $O(1)$ rounds. This APVA protocol serves as a key building block for our OciorABA protocol.

Related papers

Efficient Extensions for Asynchronous Byzantine Agreement via Weak Agreement [23.27199615640474]
We present a novel reduction from multivalued BA to binary BA. As our reduction uses multivalued WA, we design two new efficient WA protocols for $ell$-bit inputs. Our WA protocols extend binary BA to multivalued BA with a constant round overhead, a quadratic-in-$n$ communication overhead, and near-optimal security.
arXiv Detail & Related papers (2025-02-04T13:44:41Z)
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. 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)
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)
Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
We study multiclass PAC learning with bandit feedback, where inputs are classified into one of $K$ possible labels and feedback is limited to whether or not the predicted labels are correct. Our main contribution is in designing a novel learning algorithm for the agnostic $(varepsilon,delta)$PAC version of the problem.
arXiv Detail & Related papers (2024-06-18T08:54:04Z)
Superposed Decoding: Multiple Generations from a Single Autoregressive Inference Pass [72.07642648108849]
Superposed Decoding is a new decoding algorithm that generates $k$ drafts at the cost of one autoregressive inference pass. Superposed Decoding can be combined with other decoding strategies, resulting in universal coverage gains when scaling inference time compute.
arXiv Detail & Related papers (2024-05-28T17:40:48Z)
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)
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)
Projection-free Graph-based Classifier Learning using Gershgorin Disc Perfect Alignment [59.87663954467815]
In graph-based binary learning, a subset of known labels $hatx_i$ are used to infer unknown labels. When restricting labels $x_i$ to binary values, the problem is NP-hard. We propose a fast projection-free method by solving a sequence of linear programs (LP) instead.
arXiv Detail & Related papers (2021-06-03T07:22:48Z)
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.