On the Time Complexity of Dijkstra's Three-State Mutual Exclusion Algorithm
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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E92-D No.8 pp.1570-1573
- Publication Date
- 2009/08/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.E92.D.1570
- Type of Manuscript
- LETTER
- Category
- Computation and Computational Models
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Masahiro KIMOTO, Tatsuhiro TSUCHIYA, Tohru KIKUNO, "On the Time Complexity of Dijkstra's Three-State Mutual Exclusion Algorithm" in IEICE TRANSACTIONS on Information,
vol. E92-D, no. 8, pp. 1570-1573, August 2009, doi: 10.1587/transinf.E92.D.1570.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E92.D.1570/_p
Copy
@ARTICLE{e92-d_8_1570,
author={Masahiro KIMOTO, Tatsuhiro TSUCHIYA, Tohru KIKUNO, },
journal={IEICE TRANSACTIONS on Information},
title={On the Time Complexity of Dijkstra's Three-State Mutual Exclusion Algorithm},
year={2009},
volume={E92-D},
number={8},
pages={1570-1573},
abstract={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.},
keywords={},
doi={10.1587/transinf.E92.D.1570},
ISSN={1745-1361},
month={August},}
Copy
TY - JOUR
TI - On the Time Complexity of Dijkstra's Three-State Mutual Exclusion Algorithm
T2 - IEICE TRANSACTIONS on Information
SP - 1570
EP - 1573
AU - Masahiro KIMOTO
AU - Tatsuhiro TSUCHIYA
AU - Tohru KIKUNO
PY - 2009
DO - 10.1587/transinf.E92.D.1570
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E92-D
IS - 8
JA - IEICE TRANSACTIONS on Information
Y1 - August 2009
AB - 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.
ER -
English
