How distributed algorithms play the token game | SpringerLink
Skip to main content
Springer Nature Link
Log in

How distributed algorithms play the token game

  • Chapter
  • First Online:
Foundations of Computer Science

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

Abstract

We argue that high-level Petri nets are an appropriate technique for the formulation of distributed algorithms. To this end, we introduce sufficient conditions for a faithful modeling of message-passing algorithms and of shared-memory algorithms.

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

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. A.V. Aho and J.D. Ullmann. Foundations of Computer Science. Computer Science Press (1992)

    Google Scholar 

  2. F.L. Bauer and G. Goos. Informatik — eine einführende übersicht. 4. Auflage, Springer-Verlag (1991)

    Google Scholar 

  3. E. Best. Representing a Program Invariant as a Linear Invariant in a Petri Net. Bulletin of the EATCS 17, 2–11 (1982)

    Google Scholar 

  4. E. Best. Semantics of Sequential and Parallel Programs. Prentice Hall International Series in Computer Science. Prentice Hall (1996)

    Google Scholar 

  5. E. Best, H. Fleischhack, W. Fraczak, R.P. Hopkins. H. Klaudel and E. Pelz. An M-net Semantics of B(PN)2. Structures in Concurrency Theory, Berlin 1995 (J. Desel, ed.), Workshops in Computing, Springer-Verlag, 85–100 (1995)

    Google Scholar 

  6. W. Brauer. How to Play the Token Game. Petri Net Newsletter 16, Gesellschaft für Informatik, 3–13 (1984)

    Google Scholar 

  7. W. Brauer, W. Reisig and G. Rozenberg (ed.). Petri Nets: Central Models and Their Properties. LNCS 254. Springer-Verlag (1987)

    Google Scholar 

  8. J. Desel and E. Kindler. Proving Correctness of Distributed Algorithms — A Petri Net Approach. Forschungsbericht 348 des Institutes AIFB der Universität Karlsruhe

    Google Scholar 

  9. J. Desel, W. Reisig and R. Walter. The Alternating Bit Protocol — Fairness Versus Priority. Petri Net Newsletter 35, Gesellschaft für Informatik, 3–5 (1990)

    Google Scholar 

  10. E.W. Dijkstra. Cooperating Sequential Processes. Programming Languages (F. Genuys, ed.), Academic Press. 43–112 (1968)

    Google Scholar 

  11. J. Esparza and G. Bruns. Trapping Mutual Exclusion in the Box Calculus. Theoretical Computer Science 153(1–2), 95–128 (1996)

    Article  MathSciNet  Google Scholar 

  12. H.J. Genrich and K. Lautenbach. System Modelling with High-level Petri Nets. Theoretical Computer Science 13, 109–136 (1981)

    Article  MathSciNet  Google Scholar 

  13. G. Goos. Vorlesungen über Informatik — Band 1: Grundlagen und funktionales Programmieren. Springer-Verlag (1995)

    Google Scholar 

  14. D. Harel. Algorithmics: The Spirit of Computing. Addison Wesley (1992)

    Google Scholar 

  15. D. Hauschildt. A Petri Net Implementation. Mitteilung 145 des Fachbereiches Informatik der Universität Hamburg (1987)

    Google Scholar 

  16. R.M. Keller: Formal Verification of Parallel Programs. Communications of the ACM 19(7), 371–384 (1976)

    Article  MATH  Google Scholar 

  17. E. Kindler and R. Walter. Message Passing Mutex. Structures in Concurrency Theory (J. Desel, ed.), Workshops in Computing, Springer-Verlag, 205–219 (1995)

    Google Scholar 

  18. G.L. Peterson. Myths about the Mutual Exclusion Problem. Information Processing Letters 12(3), 115–116 (1981)

    Article  MATH  Google Scholar 

  19. N. Lynch. Distributed Algorithms. Morgan Kaufmann (1996)

    Google Scholar 

  20. K. Raymond. A Tree-Based Algorithm for Distributed Mutual Exclusion. ACM Transactions on Computer Systems 7(1), 61–77 (1989)

    Article  MathSciNet  Google Scholar 

  21. M. Raynal. Algorithms for Mutual Exclusion. North Oxford Academic (1986)

    Google Scholar 

  22. W. Reisig. Petri Net Models of Distributed Algorithms. Computer Science Today (J. v. Leeuwen, ed.), LNCS 1000. Springer-Verlag, 441–455 (1988)

    Google Scholar 

  23. W. Reisig. Modelling and Verification of Distributed Algorithms. CONCUR'96, (U. Montanari and V. Sassone, ed.), LNCS 1119, Springer-Verlag, 579–595 (1996)

    Google Scholar 

  24. D. Taubner. On the Implementation of Petri Nets. Advances in Petri Nets 1988 (G. Rozenberg, ed.), LNCS 340. Springer-Verlag, 418–439 (1988)

    Google Scholar 

  25. R. Valk. On Theory and Practice: An Exercise in Fairness. Petri Net Newsletter 26, Gesellschaft für Informatik. 4–11 (1987)

    Google Scholar 

  26. R. Walter. Petrinetzmodelle verteilter Algorithmen. Edition VERSAL 2, Bertz Verlag (1995)

    Google Scholar 

  27. R. Walter, H. Völzer, T. Vesper, W. Reisig, E. Kindler, J. Freiheit and J. Desel. Memorandum Petrinetzmodelle zur Verifikation Verteilter Algorithmen. Informatik-Bericht 67 der Humboldt-Universität zu Berlin (1996).

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institut für Angewandte Informatik und Formale Beschreibungsverfahren, Universität Karlsruhe, Germany

    Jörg Desel

Authors
  1. Jörg Desel
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Christian Freksa Matthias Jantzen Rüdiger Valk

Rights and permissions

Reprints and permissions

Copyright information

© 1997 Springer-Verlag Berlin Heidelberg

About this chapter

Cite this chapter

Desel, J. (1997). How distributed algorithms play the token game. In: Freksa, C., Jantzen, M., Valk, R. (eds) Foundations of Computer Science. Lecture Notes in Computer Science, vol 1337. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0052098

Download citation

  • DOI: https://doi.org/10.1007/BFb0052098

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-63746-2

  • Online ISBN: 978-3-540-69640-7

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation