Deducible and equivalent structural knowledges in distributed algorithms (Q1762994)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Deducible and equivalent structural knowledges in distributed algorithms |
scientific article |
Statements
Deducible and equivalent structural knowledges in distributed algorithms (English)
0 references
11 February 2005
0 references
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.
0 references