Paper 2023/449

Multidimensional Approximate Agreement with Asynchronous Fallback

Abstract

Multidimensional Approximate Agreement considers a setting of $n$ parties, where each party holds a vector in ${\mathbb{R}}^D$ as input. The honest parties are required to obtain very close outputs in ${\mathbb{R}}^D$ that lie inside the convex hull of their inputs. Existing Multidimensional Approximate Agreement protocols achieve resilience against $$ corruptions under a synchronous network where messages are delivered within some time $$, but become completely insecure as soon as a single message is further delayed. On the other hand, asynchronous solutions do not rely on any delay upper bound, but only achieve resilience up to $$ corruptions. We investigate the feasibility of achieving Multidimensional Approximate Agreement protocols that achieve simultaneously guarantees in both network settings: We want to tolerate $$ corruptions when the network is synchronous, and also tolerate $$ corruptions when the network is asynchronous. We provide a protocol that works as long as $$, and matches several existing lower bounds.