Piotr Dembinski

Randomized Enumeration

848

Abstract

The paper describes a randomized version of the distributed enumeration algorithm (protocol) in a network of processes. The advantage of the randomized approach is in that the resulting algorithm works for all network topologies and for fully asynchronous communication (which is not the case for the deterministic case). Correctness of the protocol is examined as well as its efficiency. The latter is estimated in probabilistic terms by means of the expected number of "drawing rounds" in which the algorithm is defined. The value is shown to be close to one and it means that practically the algorithm is performed in time needed to broadcast a message in the network. The algorithm is implemented in the specification language Estelle. Simulation experiments (with both deterministic and randomized Estelle specifications) confirmed the obtained results.

Key words: randomized algorithms, distributed algorithms, network protocols.