Search Results

Documents authored by Nguyen, Minh Hang

Document
DOI: 10.4230/LIPIcs.DISC.2025.31
Lower Bounds for k-Set Agreement in Fault-Prone Networks

Authors: Pierre Fraigniaud, Minh Hang Nguyen, Ami Paz, Ulrich Schmid, and Hugo Rincon-Galeana

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

Abstract
We develop a new lower bound for k-set agreement in synchronous message-passing systems connected by an arbitrary directed communication network, where up to t processes may crash. Our result thus generalizes the ⌊t/k⌋ + 1 lower bound for complete networks in the t-resilient model by Chaudhuri, Herlihy, Lynch, and Tuttle [JACM 2000]. Moreover, it generalizes two lower bounds for oblivious algorithms in synchronous systems connected by an arbitrary undirected communication network known to the processes, namely, the domination number-based lower bound by Castañeda, Fraigniaud, Paz, Rajsbaum, Roy, and Travers [TCS 2021] for failure-free processes, and the radius-based lower bound in the t-resilient model by Fraigniaud, Nguyen, and Paz [STACS 2024]. Our topological proof non-trivially generalizes and extends the connectivity-based approach for the complete network, as presented in the book by Herlihy, Kozlov, and Rajsbaum (2013). It is based on a sequence of shellable carrier maps that, starting from a shellable input complex, determine the evolution of the protocol complex: During the first ⌊t/k⌋ rounds, carrier maps that crash exactly k processes per round are used, which ensure high connectivity of their images. A Sperner’s lemma style argument can thus be used to prove that k-set agreement is still impossible by that round. From round ⌊t/k⌋ + 1 up to our actual lower bound, a novel carrier map is employed, which maintains high connectivity. As a by-product, our proof also provides a strikingly simple lower-bound for k-set agreement in synchronous systems with an arbitrary communication network, where exactly t ≥ 0 processes crash initially, i.e., before taking any step. We demonstrate that the resulting additional agreement overhead can be expressed via an appropriately defined radius of the communication graphs, and show that the usual input pseudosphere complex for k-set agreement can be replaced by an exponentially smaller input complex based on Kuhn triangulations, which we prove to be also shellable.
Cite as

Pierre Fraigniaud, Minh Hang Nguyen, Ami Paz, Ulrich Schmid, and Hugo Rincon-Galeana. Lower Bounds for k-Set Agreement in Fault-Prone Networks. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 31:1-31:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fraigniaud_et_al:LIPIcs.DISC.2025.31,
  author =	{Fraigniaud, Pierre and Nguyen, Minh Hang and Paz, Ami and Schmid, Ulrich and Rincon-Galeana, Hugo},
  title =	{{Lower Bounds for k-Set Agreement in Fault-Prone Networks}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{31:1--31:22},
  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.31},
  URN =		{urn:nbn:de:0030-drops-248480},
  doi =		{10.4230/LIPIcs.DISC.2025.31},
  annote =	{Keywords: Distributed computing, k-set agreement, time complexity, lower bounds, topology}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.34
Agreement Tasks in Fault-Prone Synchronous Networks of Arbitrary Structure

Authors: Pierre Fraigniaud, Minh Hang Nguyen, and Ami Paz

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
Consensus is arguably the most studied problem in distributed computing as a whole, and particularly in the distributed message-passing setting. In this latter framework, research on consensus has considered various hypotheses regarding the failure types, the memory constraints, the algorithmic performances (e.g., early stopping and obliviousness), etc. Surprisingly, almost all of this work assumes that messages are passed in a complete network, i.e., each process has a direct link to every other process. A noticeable exception is the recent work of Castañeda et al. (Inf. Comput. 2023) who designed a generic oblivious algorithm for consensus running in radius(G,t) rounds in every graph G, when up to t nodes can crash by irrevocably stopping, where t is smaller than the node-connectivity κ of G. Here, radius(G,t) denotes a graph parameter called the radius of G whenever up to t nodes can crash. For t = 0, this parameter coincides with radius(G), the standard radius of a graph, and, for G = K_n, the running time radius(K_n,t) = t+1 of the algorithm exactly matches the known round-complexity of consensus in the clique K_n. Our main result is a proof that radius(G,t) rounds are necessary for oblivious algorithms solving consensus in G when up to t nodes can crash, thus validating a conjecture of Castañeda et al., and demonstrating that their consensus algorithm is optimal for any graph G. We also extend the result of Castañeda et al. to two different settings: First, to the case where the number t of failures is not necessarily smaller than the connectivity κ of the considered graph; Second, to the k-set agreement problem for which agreement is not restricted to be on a single value as in consensus, but on up to k different values.
Cite as

Pierre Fraigniaud, Minh Hang Nguyen, and Ami Paz. Agreement Tasks in Fault-Prone Synchronous Networks of Arbitrary Structure. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 34:1-34:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fraigniaud_et_al:LIPIcs.STACS.2025.34,
  author =	{Fraigniaud, Pierre and Nguyen, Minh Hang and Paz, Ami},
  title =	{{Agreement Tasks in Fault-Prone Synchronous Networks of Arbitrary Structure}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{34:1--34:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.34},
  URN =		{urn:nbn:de:0030-drops-228606},
  doi =		{10.4230/LIPIcs.STACS.2025.34},
  annote =	{Keywords: Consensus, set-agreement, fault tolerance, crash failures}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2024.47
Brief Announcement: Agreement Tasks in Fault-Prone Synchronous Networks of Arbitrary Structures

Authors: Pierre Fraigniaud, Minh Hang Nguyen, and Ami Paz

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

Abstract
Consensus is arguably the most studied problem in distributed computing as a whole, and particularly in distributed message-passing settings. Research on consensus has considered various failure types, memory constraints, and much more. Surprisingly, almost all of this work assumes that messages are passed in a complete network, i.e., each process has a direct link to every other process. Set agreement, a relaxed variant of consensus, has also been heavily studied in different settings, yet research on it has also been limited to complete networks. We address this situation by considering consensus and set agreement in general networks, i.e., that can have an arbitrary graph G as their communication graph. We focus on fault-prone networks, where up to t nodes may crash and irrevocably stop communicating, and present upper and lower bounds for such networks. We establish the following collection of results: - The consensus algorithm by [Castañeda et al., 2023] is optimal for all graphs, and not only for symmetric graphs. - This algorithm can be extended to a generic algorithm for k-set agreement, for every k ≥ 1. For k = 1, our generic algorithm coincides with the existing one for consensus. - All these algorithms can be extended to the case where the number t of failures exceeds the connectivity κ of the graph, while the existing consensus algorithm assumed that t < κ.
Cite as

Pierre Fraigniaud, Minh Hang Nguyen, and Ami Paz. Brief Announcement: Agreement Tasks in Fault-Prone Synchronous Networks of Arbitrary Structures. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 47:1-47:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{fraigniaud_et_al:LIPIcs.DISC.2024.47,
  author =	{Fraigniaud, Pierre and Nguyen, Minh Hang and Paz, Ami},
  title =	{{Brief Announcement: Agreement Tasks in Fault-Prone Synchronous Networks of Arbitrary Structures}},
  booktitle =	{38th International Symposium on Distributed Computing (DISC 2024)},
  pages =	{47:1--47:5},
  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.47},
  URN =		{urn:nbn:de:0030-drops-212755},
  doi =		{10.4230/LIPIcs.DISC.2024.47},
  annote =	{Keywords: Consensus, set-agreement, fault tolerance, crash failures}
}
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact