1. bookVolume 23 (2015): Issue 4 (December 2015)
Journal Details
License
Format
Journal
First Published
09 Jun 2008
Publication timeframe
4 times per year
Languages
English
Copyright
© 2020 Sciendo

Event-Based Proof of the Mutual Exclusion Property of Peterson’s Algorithm

Published Online: 25 Mar 2016
Page range: 325 - 331
Received: 14 Aug 2015
Journal Details
License
Format
Journal
First Published
09 Jun 2008
Publication timeframe
4 times per year
Languages
English
Copyright
© 2020 Sciendo

Proving properties of distributed algorithms is still a highly challenging problem and various approaches that have been proposed to tackle it [1] can be roughly divided into state-based and event-based proofs. Informally speaking, state-based approaches define the behavior of a distributed algorithm as a set of sequences of memory states during its executions, while event-based approaches treat the behaviors by means of events which are produced by the executions of an algorithm. Of course, combined approaches are also possible.

Keywords

MSC:

MML

[1] Uri Abraham. Models for Concurrency. Gordon and Breach, 1999.Search in Google Scholar

[2] Uri Abraham, Ievgen Ivanov, and Mykola Nikitchenko. Proving behavioral properties of distributed algorithms using their compositional semantics. In Proceedings of the First International Seminar Specification and Verification of Hybrid Systems, October 10-12, 2011, Taras Shevchenko National University of Kyiv, pages 9–19, 2011.Search in Google Scholar

[3] Grzegorz Bancerek, Czesław Byliński, Adam Grabowski, Artur Korniłowicz, Roman Matuszewski, Adam Naumowicz, Karol Pąk, and Josef Urban. Mizar: State-of-the-art and beyond. In Manfred Kerber, Jacques Carette, Cezary Kaliszyk, Florian Rabe, and Volker Sorge, editors, Intelligent Computer Mathematics, volume 9150 of Lecture Notes in Computer Science, pages 261–279. Springer International Publishing, 2015. ISBN 978-3-319-20614-1. doi:10.1007/978-3-319-20615-8 17.Search in Google Scholar

[4] Czesław Byliński. Functions and their basic properties. Formalized Mathematics, 1(1): 55–65, 1990.Search in Google Scholar

[5] Czesław Byliński. Functions from a set to a set. Formalized Mathematics, 1(1):153–164, 1990.Search in Google Scholar

[6] Czesław Byliński. Some basic properties of sets. Formalized Mathematics, 1(1):47–53, 1990.Search in Google Scholar

[7] K. Chandy and J. Misra. Parallel Program Design: A Foundation. Addison Wesley, 1988.Search in Google Scholar

[8] Ievgen Ivanov, Mykola Nikitchenko, and Uri Abraham. On a decidable formal theory for abstract continuous-time dynamical systems. In Vadim Ermolayev, Heinrich C. Mayr, Mykola Nikitchenko, Aleksander Spivakovsky, and Grygoriy Zholtkevych, editors, Information and Communication Technologies in Education, Research, and Industrial Applications, volume 469 of Communications in Computer and Information Science, pages 78–99. Springer International Publishing, 2014. ISBN 978-3-319-13205-1. doi:10.1007/978-3-319-13206-8 4.Search in Google Scholar

[9] L. Lamport. On interprocess communication. Part I: Basic formalism; Part II: Algorithms. Distributed Computing, 1:77–101, 1986.Search in Google Scholar

[10] Beata Padlewska. Families of sets. Formalized Mathematics, 1(1):147–152, 1990.Search in Google Scholar

[11] G. Peterson. Myths about the mutual exclusion problem. Information Processing Letters, 12:1133–1145, 1981.Search in Google Scholar

[12] V. Pratt. Modeling concurrency with partial orders. International Journal of Parallel Programming, 15:33–71, 1986.Search in Google Scholar

[13] M. Raynal. A simple taxonomy for distributed mutual exclusion algorithms. ACM SIGOPS Operating Systems Review, 25:47–50, 1991.Search in Google Scholar

[14] Tom Ridge. Peterson’s algorithm in Isabelle/HOL. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.99.3484, 2006.Search in Google Scholar

[15] Tom Ridge. Operational reasoning for concurrent Caml programs and weak memory models. In Klaus Schneider and Jens Brandt, editors, Theorem Proving in Higher Order Logics, volume 4732 of Lecture Notes in Computer Science, pages 278–293. Springer Berlin Heidelberg, 2007. ISBN 978-3-540-74590-7. doi:10.1007/978-3-540-74591-4 21.Search in Google Scholar

[16] Wojciech A. Trybulec and Grzegorz Bancerek. Kuratowski – Zorn lemma. Formalized Mathematics, 1(2):387–393, 1990.Search in Google Scholar

[17] Zinaida Trybulec. Properties of subsets. Formalized Mathematics, 1(1):67–71, 1990.Search in Google Scholar

[18] Edmund Woronowicz. Relations and their basic properties. Formalized Mathematics, 1 (1):73–83, 1990.Search in Google Scholar

[19] Edmund Woronowicz and Anna Zalewska. Properties of binary relations. Formalized Mathematics, 1(1):85–89, 1990.Search in Google Scholar

Plan your remote conference with Sciendo