How to prove impossibility under global fairness: on space complexity of self-stabilizing leader election on a population protocol model (Q692907)

From MaRDI portal
Revision as of 00:59, 5 March 2024 by Import240304020342 (talk | contribs) (Set profile property.)
scientific article
Language Label Description Also known as
English
How to prove impossibility under global fairness: on space complexity of self-stabilizing leader election on a population protocol model
scientific article

    Statements

    How to prove impossibility under global fairness: on space complexity of self-stabilizing leader election on a population protocol model (English)
    0 references
    0 references
    0 references
    0 references
    6 December 2012
    0 references
    Population protocols is one of the distributed computing models where a number of mobile agents change their states by pairwise interactions. A self-stabilizing protocol ensures that the system converges to the desired behavior regardless its initial configuration. A leader election allows to distinguish a single agent with the final state ELECTED, the state of the other agents is NON-ELECTED. Global fairness guarantees the occurrence of any possible transition. This paper proves that under the assumption of global fairness, no protocol using only \(n-1\) states (where \(n\) is the number of agents) can solve the self-stabilizing leader election in complete interaction graphs.
    0 references
    distributed algorithm
    0 references
    leader election
    0 references
    population protocol
    0 references
    self-stabilization
    0 references
    global fairness
    0 references

    Identifiers