Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

Distributed algorithms for networks of agents

: Reisig, W.; Kindler, E.; Vesper, T.; Völzer, H.; Walter, R.

Reisig, W.:
Lectures on Petri nets. Advances in Petri nets. Vol. 2: Applications
Berlin: Springer, 1998 (Lecture notes in computer science 1492)
ISBN: 3-540-65307-4
ISSN: 0302-9743
Book Article
Fraunhofer ISST ()
distributed algorithms; petri net; verification

A new kind of algorithms, called distributed algorithms, has emerged during the last decade, aimed at efficiently solving problems that occur whenever distributed computing systems are to be made applicable to real world problems. Distributed computing systems are frequently organized as networks of neighboring agents. Algorithms running on such networks are called distributed. A network algorithm is a schema, intended to run on any network in a whole class of networks. Such an algorithm can be modeled as a high-level Petri net schema. Each interpretation of the schema yields an algorithm for a condrete network. This paper suggests a variety of Petri net models of network algorithms, formally represents their most decisive properties, and proves their validity. To this end, wellknown techniques such as place invariants and traps are adjusted to Petri net schemata, and new techniques to prove progress properties are suggested.