Search Results

Documents authored by Taïani, François

Document
DOI: 10.4230/LIPIcs.OPODIS.2024.14
Near-Optimal Communication Byzantine Reliable Broadcast Under a Message Adversary

Authors: Timothé Albouy, Davide Frey, Ran Gelles, Carmit Hazay, Michel Raynal, Elad Michael Schiller, François Taïani, and Vassilis Zikas

Published in: LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 2024)

Abstract
We address the problem of Reliable Broadcast in asynchronous message-passing systems with n nodes, of which up to t are malicious (faulty), in addition to a message adversary that can drop some of the messages sent by correct (non-faulty) nodes. We present a Message-Adversary-Tolerant Byzantine Reliable Broadcast (MBRB) algorithm that communicates O(|m|+nκ) bits per node, where |m| represents the length of the application message and κ = Ω(log n) is a security parameter. This communication complexity is optimal up to the parameter κ. This significantly improves upon the state-of-the-art MBRB solution (Albouy, Frey, Raynal, and Taïani, TCS 2023), which incurs communication of O(n|m|+n²κ) bits per node. Our solution sends at most 4n² messages overall, which is asymptotically optimal. Reduced communication is achieved by employing coding techniques that replace the need for all nodes to (re-)broadcast the entire application message m. Instead, nodes forward authenticated fragments of the encoding of m using an erasure-correcting code. Under the cryptographic assumptions of threshold signatures and vector commitments, and assuming n > 3t+2d, where the adversary drops at most d messages per broadcast, our algorithm allows at least 𝓁 = n - t - (1 + ε)d (for any arbitrarily low ε > 0) correct nodes to reconstruct m, despite missing fragments caused by the malicious nodes and the message adversary.
Cite as

Timothé Albouy, Davide Frey, Ran Gelles, Carmit Hazay, Michel Raynal, Elad Michael Schiller, François Taïani, and Vassilis Zikas. Near-Optimal Communication Byzantine Reliable Broadcast Under a Message Adversary. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 14:1-14:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{albouy_et_al:LIPIcs.OPODIS.2024.14,
  author =	{Albouy, Timoth\'{e} and Frey, Davide and Gelles, Ran and Hazay, Carmit and Raynal, Michel and Schiller, Elad Michael and Ta\"{i}ani, Fran\c{c}ois and Zikas, Vassilis},
  title =	{{Near-Optimal Communication Byzantine Reliable Broadcast Under a Message Adversary}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{14:1--14:29},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-360-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{324},
  editor =	{Bonomi, Silvia and Galletta, Letterio and Rivi\`{e}re, Etienne and Schiavoni, Valerio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.14},
  URN =		{urn:nbn:de:0030-drops-225503},
  doi =		{10.4230/LIPIcs.OPODIS.2024.14},
  annote =	{Keywords: Asynchronous message-passing, Byzantine fault-tolerance, Message adversary, Reliable broadcast, Erasure-correction codes, \{Threshold\} signatures, \{Vector commitments\}}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2024.41
Brief Announcement: Towards Optimal Communication Byzantine Reliable Broadcast Under a Message Adversary

Authors: Timothé Albouy, Davide Frey, Ran Gelles, Carmit Hazay, Michel Raynal, Elad Michael Schiller, François Taïani, and Vassilis Zikas

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

Abstract
We address the problem of Reliable Broadcast in asynchronous message-passing systems with n nodes, of which up to t are malicious (faulty), in addition to a message adversary that can drop some of the messages sent by correct (non-faulty) nodes. We present a Message-Adversary-Tolerant Byzantine Reliable Broadcast (MBRB) algorithm that communicates an almost optimal amount of O(|m|+n²κ) bits per node, where |m| represents the length of the application message and κ = Ω(log n) is a security parameter. This improves upon the state-of-the-art MBRB solution (Albouy, Frey, Raynal, and Taïani, TCS 2023), which incurs communication of O(n|m|+n²κ) bits per node. Our solution sends at most 4n² messages overall, which is asymptotically optimal. Reduced communication is achieved by employing coding techniques that replace the need for all nodes to (re-)broadcast the entire application message m. Instead, nodes forward authenticated fragments of the encoding of m using an erasure-correcting code. Under the cryptographic assumptions of PKI and collision-resistant hash, and assuming n > 3t+2d, where the adversary drops at most d messages per broadcast, our algorithm allows at least 𝓁 = n - t - (1 + ε)d (for any ε > 0) correct nodes to reconstruct m, despite missing fragments caused by the malicious nodes and the message adversary.
Cite as

Timothé Albouy, Davide Frey, Ran Gelles, Carmit Hazay, Michel Raynal, Elad Michael Schiller, François Taïani, and Vassilis Zikas. Brief Announcement: Towards Optimal Communication Byzantine Reliable Broadcast Under a Message Adversary. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 41:1-41:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{albouy_et_al:LIPIcs.DISC.2024.41,
  author =	{Albouy, Timoth\'{e} and Frey, Davide and Gelles, Ran and Hazay, Carmit and Raynal, Michel and Schiller, Elad Michael and Ta\"{i}ani, Fran\c{c}ois and Zikas, Vassilis},
  title =	{{Brief Announcement: Towards Optimal Communication Byzantine Reliable Broadcast Under a Message Adversary}},
  booktitle =	{38th International Symposium on Distributed Computing (DISC 2024)},
  pages =	{41:1--41:7},
  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.41},
  URN =		{urn:nbn:de:0030-drops-212697},
  doi =		{10.4230/LIPIcs.DISC.2024.41},
  annote =	{Keywords: Asynchronous message-passing, Byzantine fault-tolerance, Message adversary, Reliable Broadcast}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2022.26
A Modular Approach to Construct Signature-Free BRB Algorithms Under a Message Adversary

Authors: Timothé Albouy, Davide Frey, Michel Raynal, and François Taïani

Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)

Abstract
This paper explores how reliable broadcast can be implemented without signatures when facing a dual adversary that can both corrupt processes and remove messages. More precisely, we consider an asynchronous n-process message-passing system in which up to t processes are Byzantine and where, at the network level, for each message broadcast by a correct process, an adversary can prevent up to d processes from receiving it (the integer d defines the power of the message adversary). So, unlike previous works, this work considers that not only can computing entities be faulty (Byzantine processes), but, in addition, that the network can also lose messages. To this end, the paper adopts a modular strategy and first introduces a new basic communication abstraction denoted k2𝓁-cast, which simplifies quorum engineering, and studies its properties in this new adversarial context. Then, the paper deconstructs existing signature-free Byzantine-tolerant asynchronous broadcast algorithms and, with the help of the k2𝓁-cast communication abstraction, reconstructs versions of them that tolerate both Byzantine processes and message adversaries. Interestingly, these reconstructed algorithms are also more efficient than the Byzantine-tolerant-only algorithms from which they originate.
Cite as

Timothé Albouy, Davide Frey, Michel Raynal, and François Taïani. A Modular Approach to Construct Signature-Free BRB Algorithms Under a Message Adversary. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 26:1-26:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{albouy_et_al:LIPIcs.OPODIS.2022.26,
  author =	{Albouy, Timoth\'{e} and Frey, Davide and Raynal, Michel and Ta\"{i}ani, Fran\c{c}ois},
  title =	{{A Modular Approach to Construct Signature-Free BRB Algorithms Under a Message Adversary}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{26:1--26:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-265-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{253},
  editor =	{Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.26},
  URN =		{urn:nbn:de:0030-drops-176464},
  doi =		{10.4230/LIPIcs.OPODIS.2022.26},
  annote =	{Keywords: Asynchronous system, Byzantine processes, Communication abstraction, Delivery predicate, Fault-Tolerance, Forwarding predicate, Message adversary, Message loss, Modularity, Quorum, Reliable broadcast, Signature-free algorithm, Two-phase commit}
}
Document
DOI: 10.4230/LIPIcs.DISC.2022.4
Good-Case Early-Stopping Latency of Synchronous Byzantine Reliable Broadcast: The Deterministic Case

Authors: Timothé Albouy, Davide Frey, Michel Raynal, and François Taïani

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract
This paper considers the good-case latency of Byzantine Reliable Broadcast (BRB), i.e., the time taken by correct processes to deliver a message when the initial sender is correct, and an essential property for practical distributed systems. Although significant strides have been made in recent years on this question, progress has mainly focused on either asynchronous or randomized algorithms. By contrast, the good-case latency of deterministic synchronous BRB under a majority of Byzantine faults has been little studied. In particular, it was not known whether a good-case latency below the worst-case bound of t+1 rounds could be obtained under a Byzantine majority. In this work, we answer this open question positively and propose a deterministic synchronous Byzantine reliable broadcast that achieves a good-case latency of max(2,t+3-c) rounds, where t is the upper bound on the number of Byzantine processes, and c the number of effectively correct processes.
Cite as

Timothé Albouy, Davide Frey, Michel Raynal, and François Taïani. Good-Case Early-Stopping Latency of Synchronous Byzantine Reliable Broadcast: The Deterministic Case. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 4:1-4:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{albouy_et_al:LIPIcs.DISC.2022.4,
  author =	{Albouy, Timoth\'{e} and Frey, Davide and Raynal, Michel and Ta\"{i}ani, Fran\c{c}ois},
  title =	{{Good-Case Early-Stopping Latency of Synchronous Byzantine Reliable Broadcast: The Deterministic Case}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{4:1--4:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.4},
  URN =		{urn:nbn:de:0030-drops-171953},
  doi =		{10.4230/LIPIcs.DISC.2022.4},
  annote =	{Keywords: Reliable Broadcast, Byzantine Faults, Synchronous Systems, Good-case latency, Deterministic Algorithms}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2019.6
Byzantine-Tolerant Set-Constrained Delivery Broadcast

Authors: Alex Auvolat, Michel Raynal, and François Taïani

Published in: LIPIcs, Volume 153, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)

Abstract
Set-Constrained Delivery Broadcast (SCD-broadcast), recently introduced at ICDCN 2018, is a high-level communication abstraction that captures ordering properties not between individual messages but between sets of messages. More precisely, it allows processes to broadcast messages and deliver sets of messages, under the constraint that if a process delivers a set containing a message m before a set containing a message m', then no other process delivers first a set containing m' and later a set containing m. It has been shown that SCD-broadcast and read/write registers are computationally equivalent, and an algorithm implementing SCD-broadcast is known in the context of asynchronous message passing systems prone to crash failures. This paper introduces a Byzantine-tolerant SCD-broadcast algorithm, which we call BSCD-broadcast. Our proposed algorithm assumes an underlying basic Byzantine-tolerant reliable broadcast abstraction. We first introduce an intermediary communication primitive, Byzantine FIFO broadcast (BFIFO-broadcast), which we then use as a primitive in our final BSCD-broadcast algorithm. Unlike the original SCD-broadcast algorithm that is tolerant to up to t<n/2 crashing processes, and unlike the underlying Byzantine reliable broadcast primitive that is tolerant to up to t<n/3 Byzantine processes, our BSCD-broadcast algorithm is tolerant to up to t<n/4 Byzantine processes. As an illustration of the high abstraction power provided by the BSCD-broadcast primitive, we show that it can be used to implement a Byzantine-tolerant read/write snapshot object in an extremely simple way.
Cite as

Alex Auvolat, Michel Raynal, and François Taïani. Byzantine-Tolerant Set-Constrained Delivery Broadcast. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 6:1-6:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{auvolat_et_al:LIPIcs.OPODIS.2019.6,
  author =	{Auvolat, Alex and Raynal, Michel and Ta\"{i}ani, Fran\c{c}ois},
  title =	{{Byzantine-Tolerant Set-Constrained Delivery Broadcast}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{6:1--6:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-133-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{153},
  editor =	{Felber, Pascal and Friedman, Roy and Gilbert, Seth and Miller, Avery},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2019.6},
  URN =		{urn:nbn:de:0030-drops-117922},
  doi =		{10.4230/LIPIcs.OPODIS.2019.6},
  annote =	{Keywords: Algorithm, Asynchronous system, Byzantine process, Communication abstraction, Distributed computing, Distributed software engineering, Fault-tolerance, Message-passing, Modularity, Read/write snapshot object, Reliable broadcast, Set-constrained message delivery}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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