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 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.