More on the power of random walks: Uniform self-stabilizing randomized algorithms

Autor:	Ran El-Yaniv, Efthymios Anagnostou
Rok vydání:	1992
Předmět:	Leader election Theoretical computer science Token passing Computer science Bounded function Mutual exclusion Network topology Random walk Protocol (object-oriented programming) Randomized algorithm
Zdroj:	Distributed Algorithms ISBN: 9783540552369 WDAG
DOI:	10.1007/bfb0022436
Popis:	We present a self-stabilizing randomized protocol for the Unique Naming problem. In the Unique Naming problem an anonymous system assigns unique names to all the processors in the system. Let G be the underlying interconnection network. If N is a known bound on the network size then our protocol uses O(CGNlogN) bits and stabilizes within O(CG) rounds where CG is the cover time of G. The protocol is uniform, tolerates dynamic changes of the network topology, and works correctly under a very powerful adversary which at any stage has knowledge of a bounded number of future random choices of the processors and it can even bias all future random choices.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::b147da51c35aa02ae07f4ae08a571b36 https://doi.org/10.1007/bfb0022436 Zobrazit plný text záznamu