Randomized Non-sequential Processes (Preliminary Version)

摘要

A non-sequential, i.e. "true concurrency", semantics for randomized distributed algorithms is suggested. It is based on Petri nets and their branching processes. We introduce randomaized Petri nets and their semantics, probabilistic branching processes. As a main result, we show that each probabilistic branching process defines a unique canonical probability space. Finally, we show that the non-sequential semantics differs from the classical sequential semantics, modelling a new adversary, called the distributed adversary.