2026-07-26T00:58:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21241 2024-10-24T07:40:08Z ddc:004 open_access

Convex Consensus with Asynchronous Fallback Constantinescu, Andrei Ghinea, Diana Wattenhofer, Roger Westermann, Floris convex consensus network-agnostic protocols agreement on a core-set 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Andrei Constantinescu and Diana Ghinea and Roger Wattenhofer and Floris Westermann 2024 Is Part Of LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2024.15 urn:nbn:de:0030-drops-212411 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.15 eng https://creativecommons.org/licenses/by/4.0/legalcode