Verification of hypertorus communication grids by infinite Petri nets and process algebra

Dmitry Zaitsev (Corresponding author), Tatiana Shmeleva, Jan Friso Groote

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)

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.
Original languageEnglish
Article number8707130
Pages (from-to)733-742
Number of pages10
JournalIEEE/CAA Journal of Automatica Sinica
Volume6
Issue number3
DOIs
Publication statusPublished - May 2019

Keywords

  • Petri nets , Mathematical model , Algebra , Hypercubes , Analytical models , Benchmark testing , Biological system modeling
  • systems biology
  • process algebra
  • conservativeness
  • deadlock
  • Computing grid
  • hypertorus
  • infinite Petri nets

Fingerprint Dive into the research topics of 'Verification of hypertorus communication grids by infinite Petri nets and process algebra'. Together they form a unique fingerprint.

  • Cite this