• Computer Science > Distributed, Parallel, and Cluster Computing [Submitted on 24 Feb 2026] Title:General Convex Agreement with Near-Optimal Communication View PDFAbstract:Convex Agreement (CA) strengthens Byzantine Agreement (BA) by requiring the output agreed upon to lie in the convex hull of the honest parties’ inputs • This validity condition is motivated by practical aggregation tasks (e • , robust learning or sensor fusion) where honest inputs need not coincide but should still constrain the decision • CA inherits BA lower bounds, and optimal synchronous round complexity is easy to obtain (e • , via Byzantine Broadcast) • The main challenge is \emph{communication}: standard approaches for CA have a communication complexity of $\Theta(Ln^2)$ for large $L$-bit inputs, leaving a gap in contrast to BA’s lower bound of $\Omega(Ln)$ bits

Article Summaries:

  • Computer Science > Distributed, Parallel, and Cluster Computing [Submitted on 24 Feb 2026] Title:General Convex Agreement with Near-Optimal Communication View PDFAbstract:Convex Agreement (CA) strengthens Byzantine Agreement (BA) by requiring the output agreed upon to lie in the convex hull of the honest parties’ inputs. This validity condition is motivated by practical aggregation tasks (e.g., robust learning or sensor fusion) where honest inputs need not coincide but should still constrain the decision. CA inherits BA lower bounds, and optimal synchronous round complexity is easy to obtain (

Sources: