Concurrency and Periodicity Analysis of Acyclic-Graph Evolution Driven by Node Firing

Morikazu NAKAMURA; Kenji ONAGA; Seiki KYAN

Concurrency and Periodicity Analysis of Acyclic-Graph Evolution Driven by Node Firing

Morikazu NAKAMURA, Kenji ONAGA, Seiki KYAN

Full Text Views

0

Share
Cite this

Summary :

We discuss properties of acyclic graph evolution driven by node-firing. The research background and basic concepts of acyclic graph evolution are from the mutual exclusion problem in distributed environments. We proposed in our previous work a mutual exclusion protocol which is based on the notion of evolution trajectories of acyclic graphs. In this paper, we analyze firing concurrency and periodicity of the acyclic graph evolution, from graph theoretical point of views, and investigate topological conditions for assuring the number of firable nodes below a some fixed constant, at any instance of the evolution trajectory. A marked graph, a subclass of Petri nets, is often utilized as a proof tool in analysis.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E78-A No.3 pp.371-381

Publication Date: 1995/03/25

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section of Selected Papers from the 7th Karuizawa Workshop on Circuits and Systems)

Category: Graphs and Networks

Cite this

Copy

Morikazu NAKAMURA, Kenji ONAGA, Seiki KYAN, "Concurrency and Periodicity Analysis of Acyclic-Graph Evolution Driven by Node Firing" in IEICE TRANSACTIONS on Fundamentals, vol. E78-A, no. 3, pp. 371-381, March 1995, doi: .
Abstract: We discuss properties of acyclic graph evolution driven by node-firing. The research background and basic concepts of acyclic graph evolution are from the mutual exclusion problem in distributed environments. We proposed in our previous work a mutual exclusion protocol which is based on the notion of evolution trajectories of acyclic graphs. In this paper, we analyze firing concurrency and periodicity of the acyclic graph evolution, from graph theoretical point of views, and investigate topological conditions for assuring the number of firable nodes below a some fixed constant, at any instance of the evolution trajectory. A marked graph, a subclass of Petri nets, is often utilized as a proof tool in analysis.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1587/e78-a_3_371/_p

Copy

@ARTICLE{e78-a_3_371,
author={Morikazu NAKAMURA, Kenji ONAGA, Seiki KYAN, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Concurrency and Periodicity Analysis of Acyclic-Graph Evolution Driven by Node Firing},
year={1995},
volume={E78-A},
number={3},
pages={371-381},
abstract={We discuss properties of acyclic graph evolution driven by node-firing. The research background and basic concepts of acyclic graph evolution are from the mutual exclusion problem in distributed environments. We proposed in our previous work a mutual exclusion protocol which is based on the notion of evolution trajectories of acyclic graphs. In this paper, we analyze firing concurrency and periodicity of the acyclic graph evolution, from graph theoretical point of views, and investigate topological conditions for assuring the number of firable nodes below a some fixed constant, at any instance of the evolution trajectory. A marked graph, a subclass of Petri nets, is often utilized as a proof tool in analysis.},
keywords={},
doi={},
ISSN={},
month={March},}

Copy

TY - JOUR
TI - Concurrency and Periodicity Analysis of Acyclic-Graph Evolution Driven by Node Firing
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 371
EP - 381
AU - Morikazu NAKAMURA
AU - Kenji ONAGA
AU - Seiki KYAN
PY - 1995
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E78-A
IS - 3
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - March 1995
AB - We discuss properties of acyclic graph evolution driven by node-firing. The research background and basic concepts of acyclic graph evolution are from the mutual exclusion problem in distributed environments. We proposed in our previous work a mutual exclusion protocol which is based on the notion of evolution trajectories of acyclic graphs. In this paper, we analyze firing concurrency and periodicity of the acyclic graph evolution, from graph theoretical point of views, and investigate topological conditions for assuring the number of firable nodes below a some fixed constant, at any instance of the evolution trajectory. A marked graph, a subclass of Petri nets, is often utilized as a proof tool in analysis.
ER -