Marked graph

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: \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.

Uses

Marked graphs are mainly used to mathematically represent concurrent mechanisms, in order to be able to mathematically derive certain characteristics of the design.

Example

Marked Graph example

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.


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Petri net — A Petri net (also known as a place/transition net or P/T net) is one of several mathematical modeling languages for the description of distributed systems. A Petri net is a directed bipartite graph, in which the nodes represent transitions (i.e.… …   Wikipedia

  • Logarithm — The graph of the logarithm to base 2 crosses the x axis (horizontal axis) at 1 and passes through the points with coordinates (2, 1), (4, 2), and (8, 3) …   Wikipedia

  • Strongly connected component — Graph with strongly connected components marked A directed graph is called strongly connected if there is a path from each vertex in the graph to every other vertex. In particular, this means paths in each direction; a path from a to b and also a …   Wikipedia

  • Economic Affairs — ▪ 2006 Introduction In 2005 rising U.S. deficits, tight monetary policies, and higher oil prices triggered by hurricane damage in the Gulf of Mexico were moderating influences on the world economy and on U.S. stock markets, but some other… …   Universalium

  • Dijkstra's algorithm — Not to be confused with Dykstra s projection algorithm. Dijkstra s algorithm Dijkstra s algorithm runtime Class Search algorithm Data structure Graph Worst case performance …   Wikipedia

  • Laws of Form — (hereinafter LoF ) is a book by G. Spencer Brown, published in 1969, that straddles the boundary between mathematics and of philosophy. LoF describes three distinct logical systems: * The primary arithmetic (described in Chapter 4), whose models… …   Wikipedia

  • Business and Industry Review — ▪ 1999 Introduction Overview        Annual Average Rates of Growth of Manufacturing Output, 1980 97, Table Pattern of Output, 1994 97, Table Index Numbers of Production, Employment, and Productivity in Manufacturing Industries, Table (For Annual… …   Universalium

  • Ergograph — An ergograph is a graph that shows a relation between human activities, or agricultural/climate factors, and a seasonal year. The name was coined by Dr. Arthur Geddes of the University of Edinburgh. It can either be a polar coördinate (circular)… …   Wikipedia

  • Agriculture and Food Supplies — ▪ 2007 Introduction Bird flu reached Europe and Africa, and concerns over BSE continued to disrupt trade in beef. An international vault for seeds was under construction on an Arctic island. Stocks of important food fish species were reported… …   Universalium

  • Vertex cover — In the mathematical discipline of graph theory, a vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set. The problem of finding a minimum vertex cover is a classical… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”