Jump to : Download | Abstract | Contact | BibTex reference | EndNote reference |

GODARD_2002_HAL-00307375_1

Emmanuel Godard, Yves Métivier. A characterization of families of graphs in which election is possible. In Foundations of Software Science and Computation Structures Foundations of System Specification and Computation Structures (FoSSaCS) (EATCS best paper award), Lecture notes in computer science, Volume 2303, Pages 159-171, Espagne, 2002.

Download

Download paper: Follow the link

Copyright notice:This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Abstract

{I}n this paper, using some techniques developed for the termination detection problem, we characterize which knowledge is necessary and sufficient to have an election algorithm, or equivalently, what is the general condition for a class of graphs to admit an election algorithm. {M}ore precisely we prove the following theorem: it {T}here is an election algorithm for a family {I} of graphs if and only if graphs of {I} are minimal for the covering relation and every graph {G} of {I} has quasi-coverings of bounded radius in {I}. {S}ufficient conditions given below are just special cases of criteria of the theorem. {W}e explain new parts in this theorem. {I}t is well known (see above) that the existence of an election algorithm needs graphs minimal for the covering relation. {W}e prove in this paper that if a graph is minimal for the covering relation and admits quasi-coverings of arbitrary large size in the family there is no election algorithm. {T}his part can be illustrated by the family of prime rings. {I}ndeed, prime rings are minimal for the covering relation nevertheless there is no election algorithm for this family: without the knowledge of the size, a ring admits quasi-covering prime rings of arbitrary large size. {T}hese two results prove one direction of the theorem . {T}o prove the converse: we extend the {M}azurkiewicz algorithm to labelled graphs; we prove that the {M}azurkiewicz algorithm applied in a graph {G} enables the reconstruction, on each node of {G}, of a graph {K} such that {G} is a quasi-covering of {K}; and when the computation is terminated {G} is a covering of {K}; we use an extension of an algorithm by {S}zymanski, {S}hi and {P}rywes which enables the distributed detection of stable properties in a graph; we prove that the bounded size of quasi-coverings of a given graph enables to each node v to detect the termination of the {M}azurkiewicz algorithm and finally each node can decide if it has obtained the maximum number among numbers computed by the {M}azurkiewicz algorithm.

Contact

Emmanuel Godard
Yves Métivier

BibTex Reference

@InProceedings{GODARD_2002_HAL-00307375_1,
   Author = {Godard, Emmanuel and Métivier, Yves},
   Title = {{A} characterization of families of graphs in which election is possible},
   BookTitle = {{F}oundations of {S}oftware {S}cience and {C}omputation {S}tructures {F}oundations of {S}ystem {S}pecification and {C}omputation {S}tructures ({F}o{SS}a{CS}) ({EATCS} best paper award)},
   Volume = {2303},
   Pages = {159--171},
   Series = {{L}ecture notes in computer science},
   Publisher = {{S}pringer},
   Address = {{E}spagne},
   Year = {2002}
}

EndNote Reference [help]

Get EndNote Reference (.ref)