Verification of Hypertorus Communication Grids by Infinite Petri Nets and Process Algebra |
| |
| Authors: | Dmitry A Zaitsev Tatiana R Shmeleva Jan Friso Groote |
| |
| Affiliation: | 1.Vistula University, Warsaw 02-787, Poland2.A.S. Popov Odessa National Academy of Telecommunications, Odessa 65023, Ukrain3.Eindhoven University of Technology, PO Box 513, 5600 MB Eindhoven, The Netherlands |
| |
| Abstract: | A model of a hypertorus communication grid has been constructed in the form of an infinite Petri net. A grid cell represents either a packet switching device or a bioplast cell. A parametric expression is obtained to allow a finite specification of an infinite Petri net. To prove properties of an ideal communication protocol, we derive an infinite Diophantine system of equations from it, which is subsequently solved. Then we present the programs htgen and ht-mcrl2-gen, developed in the C language, which generate Petri net and process algebra models of a hypertorus with a given number of dimensions and grid size. These are the inputs for the respective modeling tools Tina and mCRL2, which provide model visualization, step simulation, state space generation and reduction, and structural analysis techniques. Benchmarks to compare the two approaches are obtained. An ad-hoc induction-like technique on invariants, obtained for a series of generated models, allows the calculation of a solution of the Diophantine system in a parametric form. It is proven that the basic solutions of the infinite system have been found and that the infinite Petri net is bounded and conservative. Some remarks regarding liveness and liveness enforcing techniques are also presented. |
| |
| Keywords: | Computing grid conservativeness deadlock hypertorus infinite Petri nets process algebra systems biology |
|
| 点击此处可从《》浏览原始摘要信息 |
|
点击此处可从《》下载全文 |
|
