Marked graph
A marked graph is a Petri net in which every place has exactly one incoming arc, and exactly one outgoing arc. This means, that there can not be conflict, but there can be concurrency. Mathematically: ∀ p ∈ P : | p ∙ | = | ∙ p | = 1 {\displaystyle \forall p\in P:|p\bullet |=|\bullet p|=1} . Marked graphs are used mostly to mathematically represent concurrently running operations, such as a multiprocessor machine's internal process state. This class of Petri nets gets the name from a popular way of representing them: as a graph where each place is an edge and each transition is a node.
 | This article needs additional citations for verification. (May 2025) |
A marked graph is a Petri net in which every place has exactly one incoming arc, and exactly one outgoing arc.[1]: 561 This means, that there can not be conflict, but there can be concurrency. Mathematically: . Marked graphs are used mostly to mathematically represent concurrently running operations, such as a multiprocessor machine's internal process state. This class of Petri nets gets the name from a popular way of representing them: as a graph where each place is an edge and each transition is a node.
Uses
[edit]Marked graphs are mainly used to mathematically represent concurrent mechanisms, in order to be able to mathematically derive certain characteristics of the design.
Example
[edit]
This example presents a Marked Graph, where a process is forked at transition T1 and synchronised at T4. In between, two operations take place in non-deterministic fashion, T2 and T3. In fact, Petri nets are so much non-deterministic, that they may not take place at all. But the reason for having this non-deterministic property is not this, but to mimic real-life experiences which shows that parallel computing always means that it is impossible to determine which process/thread will finish first i.e. which operation(s) will execute faster. This can be due to waiting for I/O in real world, or just the different parameters given to the processes/threads.
See also
[edit]References
[edit]- ^ Johnsonbaugh, Richard; Murata, Tadao (October 1982). "Petri Nets and Marked Graphs–Mathematical Models of Concurrent Computation". The American Mathematical Monthly. 89 (8): 552–566. doi:10.1080/00029890.1982.11995494.