Coupling and self-stabilization
Autor: | Claudine Picaronny, Laurent Fribourg, Stéphane Messika |
---|---|
Rok vydání: | 2005 |
Předmět: |
Markov chain
Computer Networks and Communications Function (mathematics) Mathematical proof Coupling (probability) Theoretical Computer Science Computational Theory and Mathematics Rate of convergence Hardware and Architecture Iterated function Convergence (routing) Theory of computation Applied mathematics Algorithm Mathematics |
Zdroj: | Distributed Computing. 18:221-232 |
ISSN: | 1432-0452 0178-2770 |
DOI: | 10.1007/s00446-005-0142-7 |
Popis: | A randomized self-stabilizing algorithm A is an algorithm that, whatever the initial configuration is, reaches a set L of legal configurations in finite time with probability 1. The proof of convergence towards L is generally done by exhibiting a potential function ϕ, which measures the "vertical" distance of any configuration to L, such that ϕ decreases with non-null probability at each step of A. We propose here a method, based on the notion of coupling, which makes use of a "horizontal" distance δ between any pair of configurations, such that δ decreases in expectation at each step of A. In contrast with classical methods, our coupling method does not require the knowledge of L. In addition to the proof of convergence, the method allows us to assess the convergence rate according to two different measures. Proofs produced by the method are often simpler or give better upper bounds than their classical counterparts, as examplified here on Herman's mutual exclusion and Iterated Prisoner's Dilemma algorithms in the case of cyclic graphs. |
Databáze: | OpenAIRE |
Externí odkaz: |