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

Morikazu NAKAMURA  Kenji ONAGA  Seiki KYAN  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E78-A    No.3    pp.371-381
Publication Date: 1995/03/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section of Selected Papers from the 7th Karuizawa Workshop on Circuits and Systems)
Category: Graphs and Networks
acyclic graph evolution,  firing concurrency,  mutual exclusion,  marked graph,  

Full Text: PDF>>
Buy this Article

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.