[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Fault-Tolerant Multiparty Session Types

  • Conference paper
  • First Online:
Formal Techniques for Distributed Objects, Components, and Systems (FORTE 2022)

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

Abstract

Multiparty session types are designed to abstractly capture the structure of communication protocols and verify behavioural properties. One important such property is progress, i.e., the absence of deadlock. Distributed algorithms often resemble multiparty communication protocols. But proving their properties, in particular termination that is closely related to progress, can be elaborate. Since distributed algorithms are often designed to cope with faults, a first step towards using session types to verify distributed algorithms is to integrate fault-tolerance.

We extend multiparty session types to cope with system failures such as unreliable communication and process crashes. Moreover, we augment the semantics of processes by failure patterns that can be used to represent system requirements (as, e.g., failure detectors). To illustrate our approach we analyse a variant of the well-known rotating coordinator algorithm by Chandra and Toueg.

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
£29.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
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 47.99
Price includes VAT (United Kingdom)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 59.99
Price includes VAT (United Kingdom)
  • 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

Similar content being viewed by others

References

  1. Adameit, M., Peters, K., Nestmann, U.: Session types for link failures. In: Bouajjani, A., Silva, A. (eds.) FORTE 2017. LNCS, vol. 10321, pp. 1–16. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-60225-7_1

    Chapter  Google Scholar 

  2. Kawazoe Aguilera, M., Chen, W., Toueg, S.: Heartbeat: a timeout-free failure detector for quiescent reliable communication. In: Mavronicolas, M., Tsigas, P. (eds.) WDAG 1997. LNCS, vol. 1320, pp. 126–140. Springer, Heidelberg (1997). https://doi.org/10.1007/BFb0030680

    Chapter  Google Scholar 

  3. Bettini, L., Coppo, M., D’Antoni, L., De Luca, M., Dezani-Ciancaglini, M., Yoshida, N.: Global progress in dynamically interleaved multiparty sessions. In: van Breugel, F., Chechik, M. (eds.) CONCUR 2008. LNCS, vol. 5201, pp. 418–433. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85361-9_33

    Chapter  Google Scholar 

  4. Bocchi, L., Honda, K., Tuosto, E., Yoshida, N.: A theory of design-by-contract for distributed multiparty interactions. In: Gastin, P., Laroussinie, F. (eds.) CONCUR 2010. LNCS, vol. 6269, pp. 162–176. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15375-4_12

    Chapter  MATH  Google Scholar 

  5. Caires, L., Vieira, H.T.: Conversation types. Theoret. Comput. Sci. 411(51–52), 4399–4440 (2010). https://doi.org/10.1016/j.tcs.2010.09.010

    Article  MathSciNet  MATH  Google Scholar 

  6. Capecchi, S., Giachino, E., Yoshida, N.: Global escape in multiparty sessions. Math. Struct. Comput. Sci. 26(2), 156–205 (2016). https://doi.org/10.1017/S0960129514000164

    Article  MathSciNet  MATH  Google Scholar 

  7. Carbone, M., Honda, K., Yoshida, N.: Structured interactional exceptions in session types. In: van Breugel, F., Chechik, M. (eds.) CONCUR 2008. LNCS, vol. 5201, pp. 402–417. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85361-9_32

    Chapter  Google Scholar 

  8. Castellani, I., Dezani-Ciancaglini, M., Giannini, P.: Concurrent reversible sessions. In: Proceedings of CONCUR. LIPIcs, vol. 85, pp. 30:1–30:17 (2017). https://doi.org/10.4230/LIPIcs.CONCUR.2017.30

  9. Castellani, I., Dezani-Ciancaglini, M., Giannini, P., Horne, R.: Global types with internal delegation. Theoret. Comput. Sci. 807, 128–153 (2020). https://doi.org/10.1016/j.tcs.2019.09.027

    Article  MathSciNet  MATH  Google Scholar 

  10. Chandra, T.D., Toueg, S.: Unreliable failure detectors for reliable distributed systems. J. ACM 43(2), 225–267 (1996). https://doi.org/10.1145/226643.226647

    Article  MathSciNet  MATH  Google Scholar 

  11. Charron-Bost, B., Schiper, A.: The heard-of model: computing in distributed systems with benign faults. Distrib. Comput. 22(1), 49–71 (2009). https://doi.org/10.1007/s00446-009-0084-6

    Article  MATH  Google Scholar 

  12. Chen, T.-C., Viering, M., Bejleri, A., Ziarek, L., Eugster, P.: A type theory for robust failure handling in distributed systems. In: Albert, E., Lanese, I. (eds.) FORTE 2016. LNCS, vol. 9688, pp. 96–113. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-39570-8_7

    Chapter  MATH  Google Scholar 

  13. Coppo, M., Dezani-Ciancaglini, M., Padovani, L., Yoshida, N.: A gentle introduction to multiparty asynchronous session types. In: Bernardo, M., Johnsen, E.B. (eds.) SFM 2015. LNCS, vol. 9104, pp. 146–178. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-18941-3_4

    Chapter  Google Scholar 

  14. Demangeon, R.: Nested Protocols in Session Types (2015), personal communication about an extended version of [15] that is currently prepared by R. Demangeon

    Google Scholar 

  15. Demangeon, R., Honda, K.: Nested protocols in session types. In: Koutny, M., Ulidowski, I. (eds.) CONCUR 2012. LNCS, vol. 7454, pp. 272–286. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-32940-1_20

    Chapter  Google Scholar 

  16. Demangeon, R., Honda, K., Hu, R., Neykova, R., Yoshida, N.: Practical interruptible conversations: distributed dynamic verification with multiparty session types and Python. Formal Methods Syst. Des. 46(3), 197–225 (2014). https://doi.org/10.1007/s10703-014-0218-8

    Article  MATH  Google Scholar 

  17. Francalanza, A., Hennessy, M.: A fault tolerance bisimulation proof for consensus (extended abstract). In: De Nicola, R. (ed.) ESOP 2007. LNCS, vol. 4421, pp. 395–410. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-71316-6_27

    Chapter  Google Scholar 

  18. Fuzzati, R., Merro, M., Nestmann, U.: Distributed Consensus, revisited. Acta Informatica, 377–425 (2007). https://doi.org/10.1007/s00236-007-0052-1

  19. Gärtner, F.C.: Fundamentals of fault-tolerant distributed computing in asynchronous environments. ACM Comput. Surv. 31(1), 1–26 (1999). https://doi.org/10.1145/311531.311532

    Article  Google Scholar 

  20. van Glabbeek, R., Höfner, P., Horne, R.: Assuming just enough fairness to make session types complete for lock-freedom. In: Proceedings of LICS, pp. 1–13. IEEE (2021)

    Google Scholar 

  21. Honda, K., Yoshida, N., Carbone, M.: Multiparty asynchronous session types. In: Proceedings of POPL, vol. 43, pp. 273–284. ACM (2008). https://doi.org/10.1145/1328438.1328472

  22. Honda, K., Yoshida, N., Carbone, M.: Multiparty asynchronous session types. J. ACM 63(1) (2016). https://doi.org/10.1145/2827695

  23. Kouzapas, D., Gutkovas, R., Gay, S.J.: Session types for broadcasting. In: Proceedings of PLACES. EPTCS, vol. 155, pp. 25–31 (2014). https://doi.org/10.4204/EPTCS.155.4

  24. Kühnrich, M., Nestmann, U.: On process-algebraic proof methods for fault tolerant distributed systems. In: Lee, D., Lopes, A., Poetzsch-Heffter, A. (eds.) FMOODS/FORTE -2009. LNCS, vol. 5522, pp. 198–212. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-02138-1_13

    Chapter  Google Scholar 

  25. Lamport, L.: Paxos made simple. ACM SIGACT News 32(4), 18–25 (2001)

    Google Scholar 

  26. Lynch, N.A.: Distributed Algorithms. Morgan Kaufmann (1996)

    Google Scholar 

  27. Nestmann, U., Fuzzati, R.: Unreliable failure detectors via operational semantics. In: Saraswat, V.A. (ed.) ASIAN 2003. LNCS, vol. 2896, pp. 54–71. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-40965-6_5

    Chapter  Google Scholar 

  28. Nestmann, U., Fuzzati, R., Merro, M.: Modeling consensus in a process calculus. In: Amadio, R., Lugiez, D. (eds.) CONCUR 2003. LNCS, vol. 2761, pp. 399–414. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-45187-7_26

    Chapter  Google Scholar 

  29. Neykova, R., Yoshida, N.: Let it recover: multiparty protocol-induced recovery. In: Proceedings of CC, pp. 98–108. ACM (2017). https://doi.org/10.1145/3033019.3033031

  30. Peters, K., Nestmann, U., Wagner, C.: Fault-tolerant multiparty session types (Technical Report). Technical report (2022). https://doi.org/10.48550/arXiv.2204.07728

  31. Peters, K., Wagner, C., Nestmann, U.: Taming concurrency for verification using multiparty session types. In: Hierons, R.M., Mosbah, M. (eds.) ICTAC 2019. LNCS, vol. 11884, pp. 196–215. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-32505-3_12

    Chapter  Google Scholar 

  32. van Steen, M., Tanenbaum, A.S.: Distributed Systems. Maarten van Steen (2017)

    Google Scholar 

  33. Tel, G.: Introduction to Distributed Algorithms. Cambridge University Press, Cambridge (1994)

    Google Scholar 

  34. Viering, M., Chen, T.-C., Eugster, P., Hu, R., Ziarek, L.: A typing discipline for statically verified crash failure handling in distributed systems. In: Ahmed, A. (ed.) ESOP 2018. LNCS, vol. 10801, pp. 799–826. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-89884-1_28

    Chapter  MATH  Google Scholar 

  35. Wagner, C., Nestmann, U.: States in process calculi. In: Proceedings of EXPRESS/SOS. EPTCS, vol. 160, pp. 48–62 (2014). https://doi.org/10.4204/EPTCS.160.6

  36. Yoshida, N., Deniélou, P.-M., Bejleri, A., Hu, R.: Parameterised multiparty session types. In: Ong, L. (ed.) FoSSaCS 2010. LNCS, vol. 6014, pp. 128–145. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-12032-9_10

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. TU Darmstadt, Darmstadt, Germany

    Kirstin Peters

  2. TU Berlin, Berlin, Germany

    Uwe Nestmann

  3. Siemens Mobility, Braunschweig, Germany

    Christoph Wagner

Authors
  1. Kirstin Peters
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Uwe Nestmann
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Christoph Wagner
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Kirstin Peters .

Editor information

Editors and Affiliations

  1. King's College London, London, UK

    Mohammad Reza Mousavi

  2. University of Cyprus, Nicosia, Cyprus

    Anna Philippou

Rights and permissions

Reprints and permissions

Copyright information

© 2022 IFIP International Federation for Information Processing

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Peters, K., Nestmann, U., Wagner, C. (2022). Fault-Tolerant Multiparty Session Types. In: Mousavi, M.R., Philippou, A. (eds) Formal Techniques for Distributed Objects, Components, and Systems. FORTE 2022. Lecture Notes in Computer Science, vol 13273. Springer, Cham. https://doi.org/10.1007/978-3-031-08679-3_7

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-08679-3_7

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-08678-6

  • Online ISBN: 978-3-031-08679-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Societies and partnerships

Search

Navigation