On the Time Complexity of Dijkstra's Three-State Mutual Exclusion Algorithm

Masahiro KIMOTO  Tatsuhiro TSUCHIYA  Tohru KIKUNO 

Publication
IEICE TRANSACTIONS on Information and Systems  Vol.E92-D  No.8  pp.1570-1573
Publication Date: 2009/08/01
Online ISSN: 1745-1361
Print ISSN: 0916-8532
Type of Manuscript: LETTER
Category: Computation and Computational Models
Keyword: 
analysis of algorithms,  distributed computing,  self-stabilization,  stabilization time, 

Full Text: PDF(78KB)

Summary: 
In this letter we give a lower bound on the worst-case time complexity of Dijkstra's three-state mutual exclusion algorithm by specifying a concrete behavior of the algorithm. We also show that our result is more accurate than the known best bound.