Deducible and equivalent structural knowledges in distributed algorithms (Q1762994): Difference between revisions

The correctness of distributed algorithms usually relies upon the use of some knowledge about the underlying network (a specific topology, some metrics, etc.). We define equivalent structural knowledges to be such knowledges that can be computed distributively, one knowing the other. We present a combinatorial characterization of this equivalence. Some applications are also given: zero knowledge, classical metrics (size, diameter, etc.). This characterization is defined in terms of graphs coverings and quasicoverings. The proofs are based upon an algorithm proposed by Mazurkiewicz, and on techniques of termination detection by Shy, Szymanski, and Prywes.