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

• Autorzy: Ievgen Ivanov , Mykola Nikitchenko , Uri Abraham
• Języki publikacji: EN

Abstrakty

EN

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. Analysis of the literature [1], [7], [12], [9], [13], [14], [15] shows that state-based approaches are more widely used than event-based approaches for proving properties of algorithms, and the difficulties in the event-based approach are often emphasized. We believe, however, that there is a certain naturalness and intuitive content in event-based proofs of correctness of distributed algorithms that makes this approach worthwhile. Besides, state-based proofs of correctness of distributed algorithms are usually applicable only to discrete-time models of distributed systems and cannot be easily adapted to the continuous time case which is important in the domain of cyber-physical systems. On the other hand, event-based proofs can be readily applied to continuous-time / hybrid models of distributed systems. In the paper [2] we presented a compositional approach to reasoning about behavior of distributed systems in terms of events. Compositionality here means (informally) that semantics and properties of a program is determined by semantics of processes and process communication mechanisms. We demonstrated the proposed approach on a proof of the mutual exclusion property of the Peterson’s algorithm [11]. We have also demonstrated an application of this approach for proving the mutual exclusion property in the setting of continuous-time models of cyber-physical systems in [8]. Using Mizar [3], in this paper we give a formal proof of the mutual exclusion property of the Peterson’s algorithm in Mizar on the basis of the event-based approach proposed in [2]. Firstly, we define an event-based model of a shared-memory distributed system as a multi-sorted algebraic structure in which sorts are events, processes, locations (i.e. addresses in the shared memory), traces (of the system). The operations of this structure include a binary precedence relation ⩽ on the set of events which turns it into a linear preorder (events are considered simultaneous, if e1 ⩽ e2 and e2 ⩽ e1), special predicates which check if an event occurs in a given process or trace, predicates which check if an event causes the system to read from or write to a given memory location, and a special partial function “val of” on events which gives the value associated with a memory read or write event (i.e. a value which is written or is read in this event) [2]. Then we define several natural consistency requirements (axioms) for this structure which must hold in every distributed system, e.g. each event occurs in some process, etc. (details are given in [2]). After this we formulate and prove the main theorem about the mutual exclusion property of the Peterson’s algorithm in an arbitrary consistent algebraic structure of events. Informally, the main theorem states that if a system consists of two processes, and in some trace there occur two events e1 and e2 in different processes and each of these events is preceded by a series of three special events (in the same process) guaranteed by execution of the Peterson’s algorithm (setting the flag of the current process, writing the identifier of the opposite process to the “turn” shared variable, and reading zero from the flag of the opposite process or reading the identifier of the current process from the “turn” variable), and moreover, if neither process writes to the flag of the opposite process or writes its own identifier to the “turn” variable, then either the events e1 and e2 coincide, or they are not simultaneous (mutual exclusion property).

Słowa kluczowe

EN

distributed system; parallel computing; algorithm; verification; mathematical model

Kategorie tematyczne

• 03B35: Mechanization of proofs and logical operations
• 68M14: Distributed systems
• 68N30: Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.)
• 68W15: Distributed algorithms

• Wydawca: De Gruyter Open
• Czasopismo: Formalized Mathematics
• Rocznik: 2015
• Tom: 23
• Numer: 4
• Strony: 325-331

Daty

wydano

2015-12-01

otrzymano

2015-08-14

online

2016-03-25

Twórcy

autor

Ievgen Ivanov

• Taras Shevchenko National University, Kyiv, Ukraine

autor

Mykola Nikitchenko

• Taras Shevchenko National University, Kyiv, Ukraine

autor

Uri Abraham

• Ben-Gurion University, Beer-Sheva, Israel

Bibliografia

• [1] Uri Abraham. Models for Concurrency. Gordon and Breach, 1999.
• [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.
• [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.[Crossref]
• [4] Czesław Byliński. Functions and their basic properties. Formalized Mathematics, 1(1): 55–65, 1990.
• [5] Czesław Byliński. Functions from a set to a set. Formalized Mathematics, 1(1):153–164, 1990.
• [6] Czesław Byliński. Some basic properties of sets. Formalized Mathematics, 1(1):47–53, 1990.
• [7] K. Chandy and J. Misra. Parallel Program Design: A Foundation. Addison Wesley, 1988.
• [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.[Crossref]
• [9] L. Lamport. On interprocess communication. Part I: Basic formalism; Part II: Algorithms. Distributed Computing, 1:77–101, 1986.
• [10] Beata Padlewska. Families of sets. Formalized Mathematics, 1(1):147–152, 1990.
• [11] G. Peterson. Myths about the mutual exclusion problem. Information Processing Letters, 12:1133–1145, 1981.
• [12] V. Pratt. Modeling concurrency with partial orders. International Journal of Parallel Programming, 15:33–71, 1986.
• [13] M. Raynal. A simple taxonomy for distributed mutual exclusion algorithms. ACM SIGOPS Operating Systems Review, 25:47–50, 1991.
• [14] Tom Ridge. Peterson’s algorithm in Isabelle/HOL. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.99.3484, 2006.
• [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.[Crossref]
• [16] Wojciech A. Trybulec and Grzegorz Bancerek. Kuratowski – Zorn lemma. Formalized Mathematics, 1(2):387–393, 1990.
• [17] Zinaida Trybulec. Properties of subsets. Formalized Mathematics, 1(1):67–71, 1990.
• [18] Edmund Woronowicz. Relations and their basic properties. Formalized Mathematics, 1 (1):73–83, 1990.
• [19] Edmund Woronowicz and Anna Zalewska. Properties of binary relations. Formalized Mathematics, 1(1):85–89, 1990.

Identyfikatory

DOI

10.1515/forma-2015-0026

bwmeta1.id-class.MML

PETERSON