Search Results

Documents authored by Dufay, Marc

Document
DOI: 10.4230/LIPIcs.DISC.2026.8
Predictions Can Only Help! Communication Efficient Byzantine Agreement with Predictions

Authors: Marc Dufay, Muhammad Ayaz Dzulfikar, and Seth Gilbert

Published in: LIPIcs, Volume 397, 40th International Symposium on Distributed Computing (DISC 2026)

Abstract
In Byzantine agreement with predictions each process begins with an input value and some (unreliable) prediction bits. Recently, it has been shown that with classification predictions - where the predictions predict each process to be honest or faulty - Byzantine agreement can be completed more quickly than without predictions, circumventing the traditional Ω(f) round lower bound. However, existing algorithms either handle limited prediction errors or send too many messages. Moreover, they all exchange Ω(n³) bits - enough to allow the processes to approximately agree on the classifications. In fact, it almost seemed necessary to share a significant number of prediction bits if one wanted to tolerate a high number of incorrect predictions. In this paper, we show that this high level of communication is not inherent to a round-efficient protocol with predictions. We provide an unauthenticated algorithm with near-optimal 𝒪̃(n²) communication complexity and optimal resilience t < n/3. Furthermore, with authentication, we give an algorithm with optimal 𝒪(n²κ) communication complexity (where κ is a security parameter) and near-optimal resilience t < (1/2 - ε)n for any constant ε > 0. All of our results achieve optimal round complexity for any number of errors in the predictions.
Cite as

Marc Dufay, Muhammad Ayaz Dzulfikar, and Seth Gilbert. Predictions Can Only Help! Communication Efficient Byzantine Agreement with Predictions. In 40th International Symposium on Distributed Computing (DISC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 397, pp. 8:1-8:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{dufay_et_al:LIPIcs.DISC.2026.8,
  author =	{Dufay, Marc and Dzulfikar, Muhammad Ayaz and Gilbert, Seth},
  title =	{{Predictions Can Only Help! Communication Efficient Byzantine Agreement with Predictions}},
  booktitle =	{40th International Symposium on Distributed Computing (DISC 2026)},
  pages =	{8:1--8:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-454-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{397},
  editor =	{Moses Jr., William K. and Censor-Hillel, Keren},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2026.8},
  URN =		{urn:nbn:de:0030-drops-281145},
  doi =		{10.4230/LIPIcs.DISC.2026.8},
  annote =	{Keywords: Byzantine agreement, Algorithm with predictions, Synchronous network}
}
Document
DOI: 10.4230/LIPIcs.DISC.2026.35
General Convex Agreement with Near-Optimal Communication

Authors: Marc Dufay, Diana Ghinea, and Anton Paramonov

Published in: LIPIcs, Volume 397, 40th International Symposium on Distributed Computing (DISC 2026)

Abstract
Byzantine Agreement (BA) considers a setting of n parties out of which up to t can be byzantine (malicious), and requires the honest parties to agree on a value subject to a condition called validity: if all honest parties have input v, the output agreed upon must be v. Convex Agreement (CA) strengthens BA by requiring the output agreed upon to lie in the convex hull of the honest parties' inputs. This validity condition captures aggregation tasks, such as robust learning and sensor fusion, where honest inputs may differ but should still constrain the final decision. Existing protocols for CA over general convexity spaces require at least Ω(L⋅n²) bits of communication for L-bit inputs, leaving a gap with BA’s Ω(L⋅n) lower bound. We investigate this gap, and we present deterministic synchronous CA protocols with near-optimal communication complexity in the long-message regime. When L = Ω(n⋅κ), where κ is a security parameter, our protocols use 𝒪(L⋅nlog n) bits of communication for finite convexity spaces and 𝒪(L⋅n^{1+o(1)}) communication for Euclidean spaces ℝ^d. Our protocols also have asymptotically optimal round complexity 𝒪(n). If an upper bound L on the honest inputs' length in bits is known in advance, we achieve near-optimal resilience t < n/(ω+ε) for any constant ε > 0, where ω is the Helly number of the convexity space. When no such bound is known, we achieve resilience t < n/(ω+ε+1). Our main technical contribution is the use of extractor graphs to obtain a deterministic assignment of parties to committees, which is robust against adaptive adversaries. As an application, our protocols can be used to obtain efficient solutions for parallel BA instances.
Cite as

Marc Dufay, Diana Ghinea, and Anton Paramonov. General Convex Agreement with Near-Optimal Communication. In 40th International Symposium on Distributed Computing (DISC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 397, pp. 35:1-35:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{dufay_et_al:LIPIcs.DISC.2026.35,
  author =	{Dufay, Marc and Ghinea, Diana and Paramonov, Anton},
  title =	{{General Convex Agreement with Near-Optimal Communication}},
  booktitle =	{40th International Symposium on Distributed Computing (DISC 2026)},
  pages =	{35:1--35:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-454-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{397},
  editor =	{Moses Jr., William K. and Censor-Hillel, Keren},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2026.35},
  URN =		{urn:nbn:de:0030-drops-281417},
  doi =		{10.4230/LIPIcs.DISC.2026.35},
  annote =	{Keywords: byzantine agreement, convex agreement, communication complexity, long messages, extractors}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2026.63
Brief Announcement: Optimal Adaptive Multi-Valued Byzantine Agreement

Authors: Marc Dufay, Anton Paramonov, and Roger Wattenhofer

Published in: LIPIcs, Volume 397, 40th International Symposium on Distributed Computing (DISC 2026)

Abstract
In Byzantine Agreement (BA), n parties, out of which t can be Byzantine, run a distributed protocol to agree on a common valid input. Traditionally, these protocols have a linear latency and quadratic communication complexity, making them impractical at a large scale. In their recent work, Constantinescu, Dufay, Paramonov, and Wattenhofer [PODC'26] consider the actual number of byzantine parties f ≤ t and work toward decoupling the dependency on n and t in the complexity. They obtain a BA protocol with 𝒪̃(n + t⋅f) communication complexity and 𝒪̃(f) round complexity. However, their results are strictly limited to agreement on a binary value. Using the framework given by their work along with novel techniques, we extend these results for BA on an L-bit value. With κ being a security parameter, and with optimal resiliency (t < n/2 in the synchronous setting or t < n/3 otherwise), we obtain: - In synchrony, a deterministic protocol with 𝒪(n⋅ (L + f⋅κ)) bit complexity and 𝒪(f + log n) round complexity. - In synchrony and partial synchrony, deterministic protocols with 𝒪̃(n⋅κ + t⋅ (L + f⋅κ)) bit complexity and 𝒪(f) round complexity. - In asynchrony, a protocol with 𝒪̃(n ⋅ κ + t⋅(L + t⋅κ)) expected bit complexity and expected 𝒪(1) latency.
Cite as

Marc Dufay, Anton Paramonov, and Roger Wattenhofer. Brief Announcement: Optimal Adaptive Multi-Valued Byzantine Agreement. In 40th International Symposium on Distributed Computing (DISC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 397, pp. 63:1-63:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{dufay_et_al:LIPIcs.DISC.2026.63,
  author =	{Dufay, Marc and Paramonov, Anton and Wattenhofer, Roger},
  title =	{{Brief Announcement: Optimal Adaptive Multi-Valued Byzantine Agreement}},
  booktitle =	{40th International Symposium on Distributed Computing (DISC 2026)},
  pages =	{63:1--63:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-454-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{397},
  editor =	{Moses Jr., William K. and Censor-Hillel, Keren},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2026.63},
  URN =		{urn:nbn:de:0030-drops-281698},
  doi =		{10.4230/LIPIcs.DISC.2026.63},
  annote =	{Keywords: Byzantine Agreement, Communication Complexity, Adaptive Communication Complexity, Resilience}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.24
Validity in Network-Agnostic Byzantine Agreement

Authors: Andrei Constantinescu, Marc Dufay, Diana Ghinea, and Roger Wattenhofer

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
Byzantine Agreement (BA) considers a setting of n parties, out of which up to t can exhibit byzantine (malicious) behavior. Honest parties must decide on a common value (agreement), which must belong to a set determined by the honest inputs (validity). Depending on the use case, this set can grow or shrink, leading to various possible desiderata collectively known as validity conditions. Varying the validity property requirement can affect the regime under which BA is solvable. Our work investigates how the selected validity property impacts BA solvability in the network-agnostic model, where the network can either be synchronous with up to t_s byzantine parties or asynchronous with up to t_a ≤ t_s byzantine parties. We give necessary and sufficient conditions for a validity property to render BA solvable, both for the case with cryptographic setup and for the one without. This traces the precise boundary of solvability in the network-agnostic model for every validity property. Our proof of sufficiency provides a universal protocol, that achieves BA for a given validity property whenever the provided conditions are satisfied. We note that, for any non-trivial validity property, the condition 2 ⋅ t_s + t_a < n is necessary for BA to be solvable, even with cryptographic setup. Specializing this claim to t_a = 0 gives that t < n / 2 is required whenever one expects a purely synchronous protocol to also work in an asynchronous network when there are no corruptions. This is especially surprising given that, for some validity properties, t < n is a sufficient condition without the last stipulation.
Cite as

Andrei Constantinescu, Marc Dufay, Diana Ghinea, and Roger Wattenhofer. Validity in Network-Agnostic Byzantine Agreement. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 24:1-24:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{constantinescu_et_al:LIPIcs.DISC.2025.24,
  author =	{Constantinescu, Andrei and Dufay, Marc and Ghinea, Diana and Wattenhofer, Roger},
  title =	{{Validity in Network-Agnostic Byzantine Agreement}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{24:1--24:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.24},
  URN =		{urn:nbn:de:0030-drops-248413},
  doi =		{10.4230/LIPIcs.DISC.2025.24},
  annote =	{Keywords: byzantine agreement, validity, network-agnostic protocols}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2025.52
Brief Announcement: From Few to Many Faults: Adaptive Byzantine Agreement with Optimal Communication

Authors: Andrei Constantinescu, Marc Dufay, Anton Paramonov, and Roger Wattenhofer

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
We study the problem of Strong Byzantine Agreement and establish tight upper and lower bounds on communication complexity, parameterized by the actual number of Byzantine faults. Specifically, for a system of n parties tolerating up to t Byzantine faults, out of which only f ≤ t are actually faulty, we obtain the following results: In the partially synchronous setting, we present the first Byzantine Agreement protocol that achieves adaptive communication complexity of 𝒪(n + t ⋅ f) words, which is asymptotically optimal. Our protocol has an optimal resilience of t < n/3. In the asynchronous setting, we prove a lower bound of Ω(n + t²) on the expected number of messages, and design an almost matching protocol with an optimal resilience that solves agreement with 𝒪((n + t²)⋅ log n) words. Our main technical contribution in the asynchronous setting is the utilization of a bipartite expander graph that allows for low-cost information dissemination.
Cite as

Andrei Constantinescu, Marc Dufay, Anton Paramonov, and Roger Wattenhofer. Brief Announcement: From Few to Many Faults: Adaptive Byzantine Agreement with Optimal Communication. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 52:1-52:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{constantinescu_et_al:LIPIcs.DISC.2025.52,
  author =	{Constantinescu, Andrei and Dufay, Marc and Paramonov, Anton and Wattenhofer, Roger},
  title =	{{Brief Announcement: From Few to Many Faults: Adaptive Byzantine Agreement with Optimal Communication}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{52:1--52:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.52},
  URN =		{urn:nbn:de:0030-drops-248680},
  doi =		{10.4230/LIPIcs.DISC.2025.52},
  annote =	{Keywords: Byzantine Agreement, Communication Complexity, Adaptive Communication Complexity, Resilience}
}
Document
DOI: 10.4230/LIPIcs.STACS.2023.27
An Approximation Algorithm for Distance-Constrained Vehicle Routing on Trees

Authors: Marc Dufay, Claire Mathieu, and Hang Zhou

Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)

Abstract
In the Distance-constrained Vehicle Routing Problem (DVRP), we are given a graph with integer edge weights, a depot, a set of n terminals, and a distance constraint D. The goal is to find a minimum number of tours starting and ending at the depot such that those tours together cover all the terminals and the length of each tour is at most D. The DVRP on trees is of independent interest, because it is equivalent to the "virtual machine packing" problem on trees studied by Sindelar et al. [SPAA'11]. We design a simple and natural approximation algorithm for the tree DVRP, parameterized by ε > 0. We show that its approximation ratio is α + ε, where α ≈ 1.691, and in addition, that our analysis is essentially tight. The running time is polynomial in n and D. The approximation ratio improves on the ratio of 2 due to Nagarajan and Ravi [Networks'12]. The main novelty of this paper lies in the analysis of the algorithm. It relies on a reduction from the tree DVRP to the bounded space online bin packing problem via a new notion of "reduced length".
Cite as

Marc Dufay, Claire Mathieu, and Hang Zhou. An Approximation Algorithm for Distance-Constrained Vehicle Routing on Trees. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 27:1-27:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{dufay_et_al:LIPIcs.STACS.2023.27,
  author =	{Dufay, Marc and Mathieu, Claire and Zhou, Hang},
  title =	{{An Approximation Algorithm for Distance-Constrained Vehicle Routing on Trees}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{27:1--27:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-266-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{254},
  editor =	{Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.27},
  URN =		{urn:nbn:de:0030-drops-176794},
  doi =		{10.4230/LIPIcs.STACS.2023.27},
  annote =	{Keywords: vehicle routing, distance constraint, approximation algorithms, trees}
}

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact