Multidimensional approximate agreement with asynchronous fallback
Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and …, 2023•dl.acm.org
Multidimensional Approximate Agreement considers a setting of n parties, where each party
holds a vector in ℝD as input. The honest parties are required to obtain very close outputs in
ℝD that lie inside the convex hull of their inputs. Existing Multidimensional Approximate
Agreement protocols achieve resilience against ts< n/(D+ 1) corruptions under a
synchronous network where messages are delivered within some time Δ, but become
completely insecure as soon as a single message sent by an honest party is further delayed …
holds a vector in ℝD as input. The honest parties are required to obtain very close outputs in
ℝD that lie inside the convex hull of their inputs. Existing Multidimensional Approximate
Agreement protocols achieve resilience against ts< n/(D+ 1) corruptions under a
synchronous network where messages are delivered within some time Δ, but become
completely insecure as soon as a single message sent by an honest party is further delayed …
Multidimensional Approximate Agreement considers a setting of n parties, where each party holds a vector in ℝD as input. The honest parties are required to obtain very close outputs in ℝD that lie inside the convex hull of their inputs.
Existing Multidimensional Approximate Agreement protocols achieve resilience against ts < n / (D + 1) corruptions under a synchronous network where messages are delivered within some time Δ, but become completely insecure as soon as a single message sent by an honest party is further delayed. On the other hand, asynchronous solutions do not rely on any delay upper bound, but only achieve resilience up to ta < n / (D + 2) corruptions.
We investigate the feasibility of achieving Multidimensional Approximate Agreement protocols that achieve simultaneously guarantees in both network settings: We want to tolerate ts corruptions when the network is synchronous, and also tolerate ta ≤ ts corruptions when the network is asynchronous. We provide a protocol that works as long as (D + 1) · ts + ta < n, and matches several existing lower bounds.
ACM Digital LibraryShowing the best result for this search. See all results
