On the Time Complexity of Dijkstra's Three-State Mutual Exclusion Algorithm
Masahiro Kimoto, Tatsuhiro Tsuchiya, Tohru Kikuno · IEICE Transactions on Information and Systems · 2009
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.