Piotr Dembinski

Distributed and Always Successful Enumeration Algorithm

812

Abstract

The paper describes a truly distributed version of the enumeration algorithm (protocol) presented and proved correct in [Maz96]. The protocol is then implemented in the specification language Estelle allowing for computer experiments simulating the protocol behavior in networks of various topologies. The first version is optimized and slightly modified to finally obtain a protocol that "always" successfully terminates, i.e., the probability of reaching a correct enumeration is arbitrarily high. This practical solution allows forgetting theoretical "impossibility results", which prove non-existence of such successful distributed solutions for some classes of networks that abstractly are characterized by, so called, "ambiguous" graphs.