Distributed algorithms for networks of agents

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 agents, with each agent asynchronously interacting with some of its 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 concrete 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, well-known techniques such as place invariants and traps are adjusted to Petri net schemata, and new techniques to prove progress properties are suggested.