iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://doi.org/10.1007/978-3-031-60603-8_29
Network Abstractions for Characterizing Communication Requirements in Asynchronous Distributed Systems | SpringerLink
Skip to main content
Springer Nature Link
Log in

Network Abstractions for Characterizing Communication Requirements in Asynchronous Distributed Systems

  • Conference paper
  • First Online:
Structural Information and Communication Complexity (SIROCCO 2024)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 14662))

  • 173 Accesses

Abstract

Whereas distributed computing research has been very successful in exploring the solvability/impossibility border of distributed computing problems like consensus in representative classes of computing models with respect to model parameters like failure bounds, this is not the case for characterizing necessary and sufficient communication requirements. In this paper, we introduce network abstractions as a novel approach for modeling communication requirements in asynchronous distributed systems. A network abstraction of a run is a sequence of directed graphs on the set of processes, where the i-th graph defines the potential message chains that may arise in the i-th portion of the run. Formally, it is defined via associating (potential) message sending times with the corresponding message receiving times in a message schedule. Network abstractions allow to reason about the future causal cones that might arise in a run, hence also facilitate reasoning about liveness properties, and are inherently compatible with temporal epistemic reasoning frameworks. We demonstrate the utility of our approach by providing necessary and sufficient network abstractions for solving the canonical firing rebels with relay (FRR) problem, and variants thereof, in asynchronous systems with up to f byzantine processes. FRR is not only a basic primitive in clock synchronization and consensus algorithms, but also integrates several distributed computing problems, namely triggering events, agreement and even stabilizing agreement, in a single problem instance.

H. R. Galeana—This work was supported by the FWF projects ByzDEL (P33600) and DMAC (P32431), and the Doctoral College Resilient Embedded Systems, which is run jointly by the TU Wien’s Faculty of Informatics and the UAS Technikum Wien.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 109.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 139.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Notes

  1. 1.

    An Arxiv version of this paper may be consulted at [13].

References

  1. Afek, Y., Gafni, E.: Asynchrony from synchrony. In: Frey, D., Raynal, M., Sarkar, S., Shyamasundar, R.K., Sinha, P. (eds.) ICDCN 2013. LNCS, vol. 7730, pp. 225–239. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-35668-1_16

    Chapter  Google Scholar 

  2. Basu, A., Charron-Bost, B., Toueg, S.: Crash failures vs. crash + link failures. In: PODC 1996, p. 246. ACM Press, Philadelphia (1996). https://doi.org/10.1145/248052.248102

  3. Ben-Zvi, I., Moses, Y.: Beyond Lamport’s happened-before: on time bounds and the ordering of events in distributed systems. J. ACM 61(2), 13:1–13:26 (2014). https://doi.org/10.1145/2542181, http://doi.acm.org/10.1145/2542181

  4. Charron-Bost, B., Moran, S.: The firing squad problem revisited. Theoret. Comput. Sci. 793, 100–112 (2019). https://doi.org/10.1016/j.tcs.2019.07.023

    Article  MathSciNet  Google Scholar 

  5. Charron-Bost, B., Moran, S.: Minmax algorithms for stabilizing consensus. Distrib. Comput. 34(3), 195–206 (2021). https://doi.org/10.1007/s00446-021-00392-9

    Article  MathSciNet  Google Scholar 

  6. Coan, B.A., Dolev, D., Dwork, C., Stockmeyer, L.: The distributed firing squad problem. In: STOC 1985, pp. 335–345. ACM, New York (1985). https://doi.org/10.1145/22145.22182

  7. Étienne Coulouma, Godard, E., Peters, J.: A characterization of oblivious message adversaries for which consensus is solvable. Theor. Comput. Sci. 584, 80–90 (2015). https://doi.org/10.1016/j.tcs.2015.01.024, https://www.sciencedirect.com/science/article/pii/S0304397515000602

  8. Dinitz, Y., Moran, S., Rajsbaum, S.: Bit complexity of breaking and achieving symmetry in chains and rings. J. ACM 55(1), 3:1–3:28 (2008). https://doi.org/10.1145/1326554.1326557

  9. Dwork, C., Lynch, N., Stockmeyer, L.: Consensus in the presence of partial synchrony. J. ACM 35(2), 288–323 (1988)

    Article  MathSciNet  Google Scholar 

  10. Fischer, M.J., Lynch, N., Merritt, M.: Easy impossibility proofs for distributed consensus problems. Distrib. Comput. 1(1), 26–39 (1986)

    Article  Google Scholar 

  11. Fischer, M.J., Lynch, N.A., Paterson, M.S.: Impossibility of distributed consensus with one faulty process. J. ACM 32(2), 374–382 (1985)

    Article  MathSciNet  Google Scholar 

  12. Fruzsa, K., Kuznets, R., Schmid, U.: Fire! In: TARK 2021. EPTCS, vol. 335, pp. 139–153 (2021). https://doi.org/10.4204/EPTCS.335.13

  13. Galeana, H.R., Schmid, U.: Network abstractions for characterizing communication requirements in asynchronous distributed systems (2023). https://doi.org/10.48550/arXiv.2310.12615

  14. Rincon Galeana, H., Winkler, K., Schmid, U., Rajsbaum, S.: A topological view of partitioning arguments: reducing k-set agreement to consensus. In: Ghaffari, M., Nesterenko, M., Tixeuil, S., Tucci, S., Yamauchi, Y. (eds.) SSS 2019. LNCS, vol. 11914, pp. 307–322. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-34992-9_25

    Chapter  Google Scholar 

  15. Godard, E., Perdereau, E.: k-set agreement in communication networks with omission faults. In: OPODIS 2016. LIPICS, vol. 70, pp. 8:1–8:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016). https://doi.org/10.4230/LIPIcs.OPODIS.2016.8

  16. Holzer, S., Wattenhofer, R.: Optimal distributed all pairs shortest paths and applications. In: PODC 2012, pp. 355–364. ACM, New York (2012). https://doi.org/10.1145/2332432.2332504

  17. Kuhn, F., Oshman, R.: Dynamic networks: models and algorithms. SIGACT News 42(1), 82–96 (2011)

    Article  Google Scholar 

  18. Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press (1997). https://books.google.at/books?id=yiV6pwAACAAJ

  19. Kuznets, R., Prosperi, L., Schmid, U., Fruzsa, K.: Causality and epistemic reasoning in byzantine multi-agent systems. In: TARK 2019. EPTCS, vol. 297, pp. 293–312. Open Publishing Association (2019). https://doi.org/10.4204/EPTCS.297.19

  20. Lamport, L., Shostak, R., Pease, M.: The byzantine generals problem. ACM Trans. Program. Lang. Syst. 4(3), 382–401 (1982). https://doi.org/10.1145/357172.357176

    Article  Google Scholar 

  21. Mendes, H., Tasson, C., Herlihy, M.: Distributed computability in byzantine asynchronous systems. In: STOC 2014, pp. 704–713. ACM, New York (2014). https://doi.org/10.1145/2591796.2591853

  22. Nowak, T., Schmid, U., Winkler, K.: Topological characterization of consensus under general message adversaries. In: PODC 2019, pp. 218–227. ACM, New York (2019).https://doi.org/10.1145/3293611.3331624

  23. Robinson, P., Schmid, U.: The asynchronous bounded-cycle model. Theoret. Comput. Sci. 412(40), 5580–5601 (2011). https://doi.org/10.1016/j.tcs.2010.08.001

    Article  MathSciNet  Google Scholar 

  24. Schmid, U., Schwarz, M., Winkler, K.: On the strongest message adversary for consensus in directed dynamic networks. In: SIROCCO 2018, pp. 102–120 (2018).https://doi.org/10.1007/978-3-030-01325-7_13

  25. Schwarz, M., Schmid, U.: Round-oblivious stabilizing consensus in dynamic networks. In: Johnen, C., Schiller, E.M., Schmid, S. (eds.) SSS 2021. LNCS, vol. 13046, pp. 154–172. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-91081-5_11

    Chapter  Google Scholar 

  26. Srikanth, T.K., Toueg, S.: Simulating authenticated broadcasts to derive simple fault-tolerant algorithms. Distrib. Comput. 2(2), 80–94 (1987). https://doi.org/10.1007/BF01667080

    Article  Google Scholar 

  27. Tseng, L., Vaidya, N.H.: Fault-tolerant consensus in directed graphs. In: PODC 2015, pp. 451–460. ACM, New York (2015). https://doi.org/10.1145/2767386.2767399

  28. Widder, J., Schmid, U.: The Theta-model: achieving synchrony without clocks. Distrib. Comput. 22(1), 29–47 (2009). https://doi.org/10.1007/s00446-009-0080-x, http://www.vmars.tuwien.ac.at/documents/extern/1724/paper.pdf

  29. Winkler, K., Paz, A., Rincon Galeana, H., Schmid, S., Schmid, U.: The time complexity of consensus under oblivious message adversaries. In: ITCS 2023, vol. 251, pp. 100:1–100:28. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany (2023). https://doi.org/10.4230/LIPIcs.ITCS.2023.100, https://drops.dagstuhl.de/opus/volltexte/2023/17603

  30. Winkler, K., Schwarz, M., Schmid, U.: Consensus in directed dynamic networks with short-lived stability. Distrib. Comput. 32(5), 443–458 (2019). https://doi.org/10.1007/s00446-019-00348-0

    Article  MathSciNet  Google Scholar 

  31. Yao, A.C.: Some complexity questions related to distributive computing (preliminary report). In: STOC 79, 30 April–2 May 1979, Atlanta, Georgia, USA, pp. 209–213 (1979). https://doi.org/10.1145/800135.804414, http://doi.acm.org/10.1145/800135.804414

Download references

Author information

Authors and Affiliations

  1. TU Wien, Vienna, Austria

    Hugo Rincon Galeana & Ulrich Schmid

Authors
  1. Hugo Rincon Galeana
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ulrich Schmid
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Hugo Rincon Galeana .

Editor information

Editors and Affiliations

  1. Faculty of Data and Decision Sciences, Technion – Israel Institute of Technolog, Haifa, Israel

    Yuval Emek

Rights and permissions

Reprints and permissions

Copyright information

© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Rincon Galeana, H., Schmid, U. (2024). Network Abstractions for Characterizing Communication Requirements in Asynchronous Distributed Systems. In: Emek, Y. (eds) Structural Information and Communication Complexity. SIROCCO 2024. Lecture Notes in Computer Science, vol 14662. Springer, Cham. https://doi.org/10.1007/978-3-031-60603-8_29

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-60603-8_29

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-60602-1

  • Online ISBN: 978-3-031-60603-8

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation