Distributed Transactions Modeling with the Use of Petri Nets

The attempt of using ordinary Petri Net to model and study Three-Phase Commit protocol (3PC) is presented. A brief overview of Petri Nets is introduced. The nature of typical and distributed transactions are explained. 3PC protocol actions are described. The Petri Net of 3PCprotocol followed by rea...

Full description

Saved in:
Bibliographic Details
Published in:Реєстрація, зберігання і обробка даних
Date:2012
Main Authors: Iwaniak, M., Khadzhynov, W.
Format: Article
Language:English
Published: Інститут проблем реєстрації інформації НАН України 2012
Subjects:
Online Access:https://nasplib.isofts.kiev.ua/handle/123456789/50587
Tags: Add Tag
No Tags, Be the first to tag this record!
Journal Title:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:Distributed Transactions Modeling with the Use of Petri Nets / M. Iwaniak, W. Khadzhynov // Реєстрація, зберігання і оброб. даних. — 2012. — Т. 14, № 3. — С. 81-91. — Бібліогр.: 4 назв. — англ.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
_version_ 1859805522568413184
author Iwaniak, M.
Khadzhynov, W.
author_facet Iwaniak, M.
Khadzhynov, W.
citation_txt Distributed Transactions Modeling with the Use of Petri Nets / M. Iwaniak, W. Khadzhynov // Реєстрація, зберігання і оброб. даних. — 2012. — Т. 14, № 3. — С. 81-91. — Бібліогр.: 4 назв. — англ.
collection DSpace DC
container_title Реєстрація, зберігання і обробка даних
description The attempt of using ordinary Petri Net to model and study Three-Phase Commit protocol (3PC) is presented. A brief overview of Petri Nets is introduced. The nature of typical and distributed transactions are explained. 3PC protocol actions are described. The Petri Net of 3PCprotocol followed by reachability analysis and study of the net properties is presented. Зроблено спробу використання простої мережі Петрі для моделювання й дослідження трифазного протоколу фіксації (ЗРС). Наведено короткий огляд мереж Петрі. Пояснено сутність звичайних і розподілених транзакцій. Дано опис кроків протоколу ЗРС. Проаналізовано доступність мережі Петрі з протоколом ЗРС і досліджено властивості запропонованої мережі.
first_indexed 2025-12-07T15:15:46Z
format Article
fulltext ISSN 1560-9189 , , 2012, . 14, 3 81 UDC 004.5:519.876.2 M. Iwaniak, W. Khadzhynov Technical University of Koszalin Department of Electronics & Informatics ul. niadeckich 2, 75-453 Koszalin, Polska hadginov@ie.tu.koszalin.pl Distributed Transactions Modeling with the Use of Petri Nets The attempt of using ordinary Petri Net to model and study Three-Phase Commit protocol (3PC) is presented. A brief overview of Petri Nets is intro- duced. The nature of typical and distributed transactions are explained. 3PC protocol actions are described. The Petri Net of 3PCprotocol followed by reachability analysis and study of the net properties is presented. Key words: Petri Net, distributed transactions, 3PC, Three-Phase Commit protocol. 1. Introduction The theory and the practice of distributed database is a very complex issue. During many years of studies the standard that would be helpful in projecting and implementa- tion of systems based on distributed database was not developed. There is especially a lack of operative standard for heterogonous distributed database. The theory of Petri Net is used in modeling and analyzing parallel processes. The structure and function of Petri Net could described in algebraic form and processed with the use of numerical methods. The solution allowing projecting, modeling and verifying processes in distributed database with the use of Petri Net is searched. Such a net might serve for supervising the flow of data in distributed database nodes or for generating configurations that allow the realization of projected processes. This work presents the attempt of usage Petri Net for showing the function of 3PC protocol. We try to answer the question: whether the ordinary Petri Net is an adequate tool for modeling such a complex process as a commitment of distributed transaction is. 2. Petri Nets The mathematical theory of Petri Nets was created by Carl Adam Petri. It has wide field of usage in analysis and modeling. © M. Iwaniak, W. Khadzhynov mailto:hadginov@ie.tu.koszalin.pl M. Iwaniak, W. Khadzhynov 82 Most commonly described is The Ordinary Petri Network, also named as network of class position/transition. It’s graphical representation is bipartite graph which con- tains two types of nodes connected by arcs. Nodes of the net are: — places (positions) — represented by circles; — transitions () — represented by rectangles. Petri Net can be expressed as the triplet N = (P, T, D) where: — P is a collection of places |P| = m; — T is a collection of transitions |T| = n; — D is incidence matrix of dimension m×n. This matrix describes relations be- tween collections of places and transitions; — D– is pre-incidence matrix of dimension m×n, it contains elements ijd = w(i, j) which describe the weight of transition j input arc, that is the arc directly connecting place i with transition j (P × T N); — D+ is post-incidence matrix of dimension m×n, it contains elements ( , )ijd w i j which describe the weight of transition j out arc, that is the arc directly connecting transition j with place i with (P × T N); — D = [D+ – D–] is incidence matrix of dimension m×n, this matrix is created by subtracting pre-incidence matrix from post-incidence matrix, it contains elements ij ij ijd d d . These elements come from subtracting weights of input arc from weights of output arcs. 2.1. Marking of net and firing of transitions Marked Petri Net can be described by four-tuple PN = (P, T, D, M0), where M0: P {0,1,2,..} is an initial marking of the net that defines the token distribution in the network places. In Petri Net with given initial marking can occur dynamic events. If the input places of given transition have an amount of tokens equal to input arc weight then the transition can be fired. After firing of the transition from all input places the tokens are taken away and new tokens are inserted into the output places. The amounts of tokens taken away from each input place and inserted into output places are equal to weights of given input and output arcs. The process is presented on Fig. 1. ) b) Fig. 1. Transition: a) transition ready to be fired; b) transition after firing Depending on the initial marking the reachability set for given Petri Net can differ. The sets of reachable markings are created and presented with usage of a directed graph Distributed Transactions Modeling with the Use of Petri Nets ISSN 1560-9189 , , 2012, . 14, 3 83 called a reachability tree. A reachability tree represents one by another both firing of transitions and marking changes. Each sequence of firings and marking changes is called the execution of the net. A reachability tree contains such elements as: — the root — representing initial marking, — nodes — representing each reachable marking, — arcs — representing fired transition, — leaves — representing final or repeated markings. A reachability tree can be prepared by analysis of following transitions firings. This analysis can be simplified by algebraic properties of Petri Net. Each column of the incidence matrix describes a change in marking after a firing of given transition. Each marking can be computed with usage of the following formula Mk = Mk–1 + e[ jt ]D, where k = 1,2,3,… and e[ jt ] a firing vector containing a digit 1 in position correspond- ing j transition. 2.2. Properties of Petri Net Boundness — the net is bounded, when for each place we can determine a finite number of tokens appearing in given place. This means that collection of possible mark- ings is finite and can be searched. Safeness is a detailed property of boundness. The place is safe if for any given marking the number of tokens in place is 0 or 1. If this condition is valid for every place in the net then the net is safe. This property is important when Petri Net is projected for hardware implementation, where place will be replaced by transistor capable of having 0 or 1 value. Conflictuality — a conflict of transition firing can occur when for given marking more than one transitions is enabled. It can also happen if firing of one transition dis- ables other already enabled transition [2]. Conservativness — the net is conservative if sum of tokens in every marking is constant. This can be proven only for simple nets. 2.3. Timed Petri Net In the Timed Petri Net we can define some time delay. If given transition gets ready (required number of tokens for each place is preset), the transition firing will hap- pen only after the delay. For two timed transitions sharing the same input place a spe- cific situation can occur. If one gets fired it can take away the shared tokens and the an- other might not be able to be fired. 2.4. Coloured Petri Net Coloured Petri Net is a graph containing places, transitions and arcs in which the token stores value of given type. For tokens of given type specific colors are assigned. M. Iwaniak, W. Khadzhynov 84 Places of Petri Net can store tokens of many colors. Given place however must allow the specific color to be stored in it. Colours separately are assigned to arcs weight. For example transition can be enabled after number of each tokens colours are equal to col- ours weights defined for the arc. 3. Processing transactions in database The digital collection of properly organized data is called database. The stored da- ta usually model real objects. Database Management System in short DBMS is respon- sible for accuracy, safety and effectiveness of the access to stored data. The structure of database is too complex to work with it without the usage of DBMS. Typically DBMS is responsible for providing data access service. Through local operating system the DBMS cares of safe data storing and mediates in all operations executed by users. Stored data are fully useful only if they are valid and consistent. Each data change takes a whole database into entirely new database state. Many data changes can happen in one unit of time and some of them are erroneous. The transaction mechanism cares for validness and consistence of an actual database state. A transaction is an operation that correctly executed guaranties database consis- tence. Transactions can consist of many operations of reading and writing the data. The changes made by the transaction must be done as a whole or none. The ACID properties are the ones that guaranty proper transactions processing. These properties are: — Atomicity — states that each transaction must be executed as whole or not at all; — Consistency — states that after the transaction is finished the database system will remain consistent. The changes made by the transaction will not be stored in data- base if during the commitment occurs an error like integrity bounds violation or any other that guaranties a data validation; — Isolation — level of isolation determines the possibility of mutual data reading by transactions proceeded concurrently. By the selected level of isolation we determine types of possible anomalies that may occur during transactions execution; — Durability — states that database system can startup after failure and provide consistent, not damaged and actual data stored in bounds of committed transactions. DBMS registers all stages of transaction processing in a transaction log. During database recovery only committed transactions are recovered, because only those can guaranty receiving the consistent state of database. In a single database during processing of transactions many anomalies can occur, like blocking, conflicts or deadlocks. A single DMBS upon its configuration and capa- bilities tries to avoid or removes occurring anomalies. 4. Transactions processing in distributed database Distributed database is a collection of many logically bounded databases con- nected via computer network. Variety of distributed database types is summarized in [1]. Distributed Transactions Modeling with the Use of Petri Nets ISSN 1560-9189 , , 2012, . 14, 3 85 Short time transactions are advised by DBMS. From application or user points of view execution of transaction in distributed system should not be different from tradi- tional system. Standalone database has implemented program called transaction manager shortly TM, that cares for proper database state management and for communication with cli- ents. In distributed environment the additional communication is happening between TMs. One of TMs serves a role of Coordinator, the others take a role of Cohorts. A way of communication between Coordinator and Cohorts are defined by distributed commit protocol. The classical example of such protocol is the one named Two-Phase Commit. This protocol has two phases: phase of voting and phase of committing. The voting phase when Coordinator sends question to its Cohors, asking if they are ready to commit distributed transaction. Returning communicates are called votes. These votes can be: vote-commit or vote-abort. After collecting votes Coordinator makes its decision. If there was any vote for aborting or any of Cohorts did not respond at all, the coordinator will make the decision of global abort of distributed transaction. If all of the votes were positive its decision will be global commit. Making of the decision only when all of the votes are for commit is the main way for assure atomicity into distributed database. 4.1. Three Phase Commit protocol for distributed transaction On Fig. 2 the algorithm of 3PC protocol is presented. Fig. 2 was prepared upon [1]. The circles represent states of Coordinator and Cohort processes. The rectangles represent operations of logging received messages and made decisions into system log. Arrows represent the flow of messages and control. Algorithm looks as follows. 1. The coordinator creates log entry with information <begin_commit> and sends <prepare> message to Cohorts. Coordinator now waits for Chorts votes. Coordinator state is <WAIT>. 2. The cohorts decide if they are ready to commit transaction. They store their de- cision into log file and send <vote-commit> or <vote-abort> to Coordinator. Varing of the decision new state of Cohort process can be READY or ABORT. 3. The coordinator checks received messages from all cohorts: a) If there was any vote-abort or some cohort did send his vote, the Coordinator makes the decision of aborting distributed transaction. Coordinator writes his decision into log file and sends <global-abort> message. Coordinator state is <ABORT>; b) If all cohorts have responded with <vote-commit> message then Coordinator makes decision to begin second phase of commit. Coordinator writes <prepare-to- commit> into log file. It sends <prepare-to-commit> message to Cohorts. Coordinator state is <PRE-COMMIT>. 4. The cohorts write received message into the log. In case of <global-abort> Co- horts processes turn into <ABORT> state and acknowledge is send to Coordinator. In case of <prepare-to-commit> Cohorts processes turn into <PRE-COMMIT> state and sends <ready-to-commit> message to Coordinator. 5. After collecting Cohorts <ready-to-commit> messages Coordinator writes <commit> into log. It sends <global-commit> message to all Cohorts. Coordinator state is now <COMMIT>. M. Iwaniak, W. Khadzhynov 86 6. The cohorts write received message into log and send back acknowledge mes- sage. Cohorts are now in <COMMIT> state. 7. The coordinator writes <end_of_transaction> into log file. Fig. 2. Three Phase Commit protocol algorithm with one participant 5. The ordinary Petri Net model of 3PC protocol Described in point 4.1 the 3PC protocol was introduced as Petri Net model on Fig. 3. The example was prepared for Coordinator and one Cohort. Places of Coordina- tor (Tab. 1) are aligned to left edge of figure. Places of Cohort (Tab. 2) are aligned to right edge of figure. Distributed Transactions Modeling with the Use of Petri Nets ISSN 1560-9189 , , 2012, . 14, 3 87 Fig. 3. Petri Net of 3PC protocol algorithm Table 1. Places and transitions of Coordinator Places Transitions P0 INITIAL T0 1) write to log (begin_commit) 2) message to Cohorts (prepare) P1 WAIT T4 1) write to log (abort) 2) message to Cohorts (global-abort) P2 ABORT T3 1) write to log (prepare-to-commit) 2) message to Cohorts (prepare-to-commit) P3 PRE-COMMIT T7 1) write to log (commit) 2) message to Cohorts (global-commit) P4 COMMIT – – Table 2. Places and transitions of Cohort Places Transitions P5 INITIAL T1 1) write to log (abort) 2) message to Coordinator (vote-abort) P6 ABORT T2 1) write to log (ready) 2) message to Coordinator (vote-commit) P7 READY T5 1) write to log (abort) 2) potwierdzenie do Coordinator P8 PRE-COMMIT T6 1) write to log (prepare-to-commit) 2) message to Coordinator (ready-to-commit) P9 COMMIT T8 1) write to log (commit) 2) potwierdzenie do Coordinator M. Iwaniak, W. Khadzhynov 88 5.1. Incidence Matrixes for Petri Net Rows of Tab. 3 contains places P0, P1, P2, P3, P4 which represent the states of Co- ordinator and places P5, P6, P7, P8, P9 which represent states of the Cohort. Columns t0 – t9 represent transitions. The pre-insidence matrix contains weights of input arcs of given transition. In case of no arc between place i and transition j we enter digit 0. This matrix is marked as [D–]. Tabel 3. Pre-Incidence Matrix D– 0t 1t 2t 3t 4t 5t 6t 7t 8t P0 INITIAL 1 0 0 0 0 0 0 0 0 P1 WAIT 0 0 0 2 2 0 0 0 0 P2 ABORT 0 0 0 0 0 0 0 0 0 P3 PRE-COMMIT 0 0 0 0 0 0 0 2 0 P4 COMMIT 0 0 0 0 0 0 0 0 0 P5 INITIAL 0 1 1 0 0 0 0 0 0 P6 ABORT 0 0 0 0 0 0 0 0 0 P7 READY 0 0 0 0 0 1 2 0 0 P8 PRE-COMMIT 0 0 0 0 0 0 0 0 2 P9 COMMIT 0 0 0 0 0 0 0 0 0 Rows of Tab. 4 contain places P0, P1, P2, P3, P4 which represent the states of Co- ordinator and places P5, P6, P7, P8, P9 which represent states of Cohort. Columns t0 – t9 represent transitions. The post-insidence matrix contains weights of output arc of given transition. In case of no arc between transition j and place i we enter digit 0. This matrix is marked as [D+]. Tabel 4. Post-Incidence Matrix D+ 0t 1t 2t 3t 4t 5t 6t 7t 8t P0 INITIAL 0 0 0 0 0 0 0 0 0 P1 WAIT 1 1 1 0 0 0 0 0 0 P2 ABORT 0 0 0 0 1 1 0 0 0 P3 PRE-COMMIT 0 0 0 1 0 0 1 0 0 P4 COMMIT 0 0 0 0 0 0 0 1 1 P5 INITIAL 1 0 0 0 0 0 0 0 0 P6 ABORT 0 1 0 0 0 1 0 0 0 P7 READY 0 0 1 1 1 0 0 0 0 P8 PRE-COMMIT 0 0 0 0 0 0 1 1 0 P9 COMMIT 0 0 0 0 0 0 0 0 1 Distributed Transactions Modeling with the Use of Petri Nets ISSN 1560-9189 , , 2012, . 14, 3 89 Combined insidence matrix (Tab. 5) is computed by subtracting pre-incidence ma- trix from post-incidence matrix [D+ – D–]. It describes dynamic changes that occur in given Petri Net. It contains information about amount of tokens added and removed in every place after the jt transitions is fired. Table 5. Combined Incidence Matrix D 0t 1t 2t 3t 4t 5t 6t 7t 8t P0 INITIAL –1 0 0 0 0 0 0 0 0 P1 WAIT 1 1 1 –2 -2 0 0 0 0 P2 ABORT 0 0 0 0 1 1 0 0 0 P3 PRE-COMMIT 0 0 0 1 0 0 1 –2 0 P4 COMMIT 0 0 0 0 0 0 0 1 1 P5 INITIAL 1 –1 –1 0 0 0 0 0 0 P6 ABORT 0 1 0 0 0 1 0 0 0 P7 READY 0 0 1 1 1 –1 –2 0 0 P8 PRE-COMMIT 0 0 0 0 0 0 1 1 –2 P9 COMMIT 0 0 0 0 0 0 0 0 1 6. Reachability analysis Initial marking is represented in the form of vector M0 = [10000000000] (Fig. 4). For given marking we check which transitions will became enabled. For instance token in the place P1 will cause firing of transitions t0. Algebraic pattern for designate markings after firing j transition is as follows: Mk = Mk-1 + e[ jt ]D, where Mk — new marking; Mk-1 — previous marking; for k = 1 it is initial marking; e[ jt ] — column vector of size i with digit 1 on index that corresponds fired transition; D — the incidence matrix. For given marking M0 we want to designate marking M1 by firing of transition t0: e[t0]*D = [–1 1 0 0 0 1 0 0 0 0]. M0 = [10000000000]. After addition of two vectors we will have following marking of Petri Net: M1 = [0100010000]. M. Iwaniak, W. Khadzhynov 90 Fig. 4. Reachability tree for Petri net from Fig. 3 (undesirable states are shown without markings) 6.1. Properties of Petri Net model Boundness — maximal amount of tokens in places is 2 therefore the net is bounded. Safeness — there are markings with places where quantity of tokens is 2 therefore the net is not safe. Conflictuality — in the presented model the conflicts take place in the Petri Net places where decision must be made. Accurate amount of tokens in places P1, P2 and P4 make all output transitions enabled (P1(T1, T2), P5(T3, T4), P7(T5, T6)). In place P5 Cohort process in case of error must send abort vote or in case of being ready it must send vote for commit. Conservativnes — presented model is complex, the property cannot be validated. 7. Resume In this work Petri Net model of 3PC protocol was presented. With usage of inci- dence matrixes the reachability tree was created. Undesireble but reachable states were identified on reachability tree. During studies of presented Petri Net model a number of limitations and problems were pointed. Most of them come from the Ordinary Petri Network limitations. We must use higher level Petri Net in further research. Applying Coloured Petri Net should Distributed Transactions Modeling with the Use of Petri Nets ISSN 1560-9189 , , 2012, . 14, 3 91 resolve the problem of decision making in certain markings. It would help reducing number of undesirable states in the analysis of reachability. 1. M. Tamer Özsu. Principles of Distributed Database Systems / M. Tamer Özsu, Patrick Valduriez // Springer. — III ed. — 2011. 2. Banaszak Z. Procesy Wspó bie ne: Modele Efektywno ci Funkcjonowania. Rozdzia 2 «Modele sieci Petriego» / Z. Banaszak, P. Majdzik, R. Wójcik. — Politechnika Koszali ska, Koszalin 2011. — Str. 93–143. 3. Bidyut Biman Sarkar. Transaction Management for Distributed Database using Petri Nets / Bidyut Biman Sarkar, Nabendu Chaki // International Journal of Computer Information Systems and In- dustrial Management Applications (IJCISIM). — 2010. — Vol. 2. — . 069–076. — ISSN: 2150-7988. 4. Bidyut Biman Sarkar. Virtual Data Warehouse Modeling Using Petri Nets for Distributed Deci- sion Making. doi:10.4156/jcit / Bidyut Biman Sarkar, Nabendu Chaki. — 2011. — Vol. 5. — Is. 5.1. Received 01.07.2012
id nasplib_isofts_kiev_ua-123456789-50587
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn 1560-9189
language English
last_indexed 2025-12-07T15:15:46Z
publishDate 2012
publisher Інститут проблем реєстрації інформації НАН України
record_format dspace
spelling Iwaniak, M.
Khadzhynov, W.
2013-10-24T00:11:43Z
2013-10-24T00:11:43Z
2012
Distributed Transactions Modeling with the Use of Petri Nets / M. Iwaniak, W. Khadzhynov // Реєстрація, зберігання і оброб. даних. — 2012. — Т. 14, № 3. — С. 81-91. — Бібліогр.: 4 назв. — англ.
1560-9189
https://nasplib.isofts.kiev.ua/handle/123456789/50587
004.5:519.876.2
The attempt of using ordinary Petri Net to model and study Three-Phase Commit protocol (3PC) is presented. A brief overview of Petri Nets is introduced. The nature of typical and distributed transactions are explained. 3PC protocol actions are described. The Petri Net of 3PCprotocol followed by reachability analysis and study of the net properties is presented.
Зроблено спробу використання простої мережі Петрі для моделювання й дослідження трифазного протоколу фіксації (ЗРС). Наведено короткий огляд мереж Петрі. Пояснено сутність звичайних і розподілених транзакцій. Дано опис кроків протоколу ЗРС. Проаналізовано доступність мережі Петрі з протоколом ЗРС і досліджено властивості запропонованої мережі.
en
Інститут проблем реєстрації інформації НАН України
Реєстрація, зберігання і обробка даних
Технічні засоби отримання і обробки даних
Distributed Transactions Modeling with the Use of Petri Nets
Моделювання розподілених транзакцій за допомогою мереж Петрі
Моделирование распределенных транзакций с помощью сетей Петри
Article
published earlier
spellingShingle Distributed Transactions Modeling with the Use of Petri Nets
Iwaniak, M.
Khadzhynov, W.
Технічні засоби отримання і обробки даних
title Distributed Transactions Modeling with the Use of Petri Nets
title_alt Моделювання розподілених транзакцій за допомогою мереж Петрі
Моделирование распределенных транзакций с помощью сетей Петри
title_full Distributed Transactions Modeling with the Use of Petri Nets
title_fullStr Distributed Transactions Modeling with the Use of Petri Nets
title_full_unstemmed Distributed Transactions Modeling with the Use of Petri Nets
title_short Distributed Transactions Modeling with the Use of Petri Nets
title_sort distributed transactions modeling with the use of petri nets
topic Технічні засоби отримання і обробки даних
topic_facet Технічні засоби отримання і обробки даних
url https://nasplib.isofts.kiev.ua/handle/123456789/50587
work_keys_str_mv AT iwaniakm distributedtransactionsmodelingwiththeuseofpetrinets
AT khadzhynovw distributedtransactionsmodelingwiththeuseofpetrinets
AT iwaniakm modelûvannârozpodílenihtranzakcíizadopomogoûmerežpetrí
AT khadzhynovw modelûvannârozpodílenihtranzakcíizadopomogoûmerežpetrí
AT iwaniakm modelirovanieraspredelennyhtranzakciispomoŝʹûseteipetri
AT khadzhynovw modelirovanieraspredelennyhtranzakciispomoŝʹûseteipetri