skip to main content
Idioma:

On the performance of Dijkstra’s third self-stabilizing algorithm for mutual exclusion and related algorithms

Chernoy, Viacheslav ; Shalom, Mordechai ; Zaks, Shmuel

Distributed computing, 2010-09, Vol.23 (1), p.43-60 [Periódico revisado por pares]

Berlin/Heidelberg: Springer-Verlag

Texto completo disponível

Citações Citado por
  • Título:
    On the performance of Dijkstra’s third self-stabilizing algorithm for mutual exclusion and related algorithms
  • Autor: Chernoy, Viacheslav ; Shalom, Mordechai ; Zaks, Shmuel
  • Assuntos: Algorithms ; Complexity ; Computer Communication Networks ; Computer Hardware ; Computer Science ; Computer Systems Organization and Communication Networks ; Lower bounds ; Mathematical analysis ; Processors ; Software Engineering/Programming and Operating Systems ; Stabilization ; Theory of Computation ; Upper bounds ; Workshops
  • É parte de: Distributed computing, 2010-09, Vol.23 (1), p.43-60
  • Notas: ObjectType-Article-2
    SourceType-Scholarly Journals-1
    ObjectType-Feature-1
    content type line 23
  • Descrição: In Dijkstra (Commun ACM 17(11):643–644, 1974) introduced the notion of self-stabilizing algorithms and presented three such algorithms for the problem of mutual exclusion on a ring of n processors. The third algorithm is the most interesting of these three but is rather non intuitive. In Dijkstra (Distrib Comput 1:5–6, 1986) a proof of its correctness was presented, but the question of determining its worst case complexity—that is, providing an upper bound on the number of moves of this algorithm until it stabilizes—remained open. In this paper we solve this question and prove an upper bound of for the complexity of this algorithm. We also show a lower bound of for the worst case complexity. For computing the upper bound, we use two techniques: potential functions and amortized analysis. We also present a new-three state self-stabilizing algorithm for mutual exclusion and show a tight bound of for the worst case complexity of this algorithm. In Beauquier and Debas (Proceedings of the second workshop on self-stabilizing systems, pp 17.1–17.13, 1995) presented a similar three-state algorithm, with an upper bound of and a lower bound of for its stabilization time. For this algorithm we prove an upper bound of and show a lower bound of n 2 − O ( n ). As far as the worst case performance is considered, the algorithm in Beauquier and Debas (Proceedings of the second workshop on self-stabilizing systems, pp 17.1–17.13, 1995) is better than the one in Dijkstra (Commun ACM 17(11):643–644, 1974) and our algorithm is better than both.
  • Editor: Berlin/Heidelberg: Springer-Verlag
  • Idioma: Inglês
Voltar para lista de resultados

  • Realização: ABCD-USP USP   Logos de Redes Sociais: Freepik

Buscando em bases de dados remotas. Favor aguardar.