Deducible and equivalent structural knowledges in distributed algorithms (Q1762994): Difference between revisions
From MaRDI portal
Created a new Item |
Set OpenAlex properties. |
||
(4 intermediate revisions by 3 users not shown) | |||
Property / author | |||
Property / author: Yves Métivier / rank | |||
Property / author | |||
Property / author: Yves Métivier / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s00224-003-1123-5 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1966104371 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 00:08, 20 March 2024
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