TY - GEN
T1 - Logical clocks are not fair
T2 - 2018 Workshop on Advanced Tools, Programming Languages, and PLatforms for Implementing and Evaluating Algorithms for Distributed Systems, ApPLIED 2018, co-located with the 37th ACM Symposium on the Principles of Distributed Computing, PODC 2018
AU - Liu, Yanhong A.
N1 - Publisher Copyright:
© 2018 Association for Computing Machinery.
PY - 2018/7/23
Y1 - 2018/7/23
N2 - This paper describes the use of a high-level, precise, and executable language, DistAlgo, for expressing, understanding, running, optimizing, and improving distributed algorithms, through the study of Lamport's algorithm for distributed mutual exclusion. We show how a simplified algorithm, reached by several rounds of better understanding and improvement of the original algorithm, leads to further simplification and improved understanding of fairness. This allows us to use any ordering for fairness, including improved fairness for granting requests in the order in which they are made, over using logical clock values. This leads to the discovery that logical clocks are not fair in general.
AB - This paper describes the use of a high-level, precise, and executable language, DistAlgo, for expressing, understanding, running, optimizing, and improving distributed algorithms, through the study of Lamport's algorithm for distributed mutual exclusion. We show how a simplified algorithm, reached by several rounds of better understanding and improvement of the original algorithm, leads to further simplification and improved understanding of fairness. This allows us to use any ordering for fairness, including improved fairness for granting requests in the order in which they are made, over using logical clock values. This leads to the discovery that logical clocks are not fair in general.
KW - Fairness
KW - High-level language
KW - Logical clock
KW - Mutual exclusion
UR - https://www.scopus.com/pages/publications/85052367028
U2 - 10.1145/3231104.3231109
DO - 10.1145/3231104.3231109
M3 - Conference contribution
AN - SCOPUS:85052367028
SN - 9781450357753
T3 - Proceedings of the Annual ACM Symposium on Principles of Distributed Computing
SP - 21
EP - 28
BT - ApPLIED 2018 - Proceedings of the 2018 Workshop on Advanced Tools, Programming Languages, and PLatforms for Implementing and Evaluating Algorithms for Distributed Systems, Co-located with PODC 2018
PB - Association for Computing Machinery
Y2 - 28 July 2017 through 28 July 2017
ER -