DROPS

Document

DOI: 10.4230/LIPIcs.DISC.2024.15

Convex Consensus with Asynchronous Fallback

Authors: Andrei Constantinescu, Diana Ghinea, Roger Wattenhofer, and Floris Westermann

Published in: LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024)

Abstract

Convex Consensus (CC) allows a set of parties to agree on a value v inside the convex hull of their inputs with respect to a predefined abstract convexity notion, even in the presence of byzantine parties. In this work, we focus on achieving CC in the best-of-both-worlds paradigm, i.e., simultaneously tolerating at most t_s corruptions if communication is synchronous, and at most t_a ≤ t_s corruptions if it is asynchronous. Our protocol is randomized, which is a requirement under asynchrony, and we prove that it achieves optimal resilience. In the process, we introduce communication primitives tailored to the network-agnostic model. These are a deterministic primitive allowing parties to obtain intersecting views (Gather), and a randomized primitive leading to identical views (Agreement on a Core-Set). Our primitives provide stronger guarantees than previous counterparts, making them of independent interest.

Cite as

Andrei Constantinescu, Diana Ghinea, Roger Wattenhofer, and Floris Westermann. Convex Consensus with Asynchronous Fallback. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 15:1-15:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{constantinescu_et_al:LIPIcs.DISC.2024.15,
  author =	{Constantinescu, Andrei and Ghinea, Diana and Wattenhofer, Roger and Westermann, Floris},
  title =	{{Convex Consensus with Asynchronous Fallback}},
  booktitle =	{38th International Symposium on Distributed Computing (DISC 2024)},
  pages =	{15:1--15:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-352-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{319},
  editor =	{Alistarh, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.15},
  URN =		{urn:nbn:de:0030-drops-212411},
  doi =		{10.4230/LIPIcs.DISC.2024.15},
  annote =	{Keywords: convex consensus, network-agnostic protocols, agreement on a core-set}
}

Search Results

Documents authored by Westermann, Floris

Convex Consensus with Asynchronous Fallback

Abstract

Cite as

Thanks for your feedback!

Could not send message