research-article

Public Access

Logical Clocks Are Not Fair: What Is Fair?

Author:

Yanhong A. LiuAuthors Info & Claims

ApPLIED '18: Proceedings of the 2018 Workshop on Advanced Tools, Programming Languages, and PLatforms for Implementing and Evaluating Algorithms for Distributed systems

Pages 21 - 27

https://doi.org/10.1145/3231104.3231109

Published: 23 July 2018 Publication History

Abstract

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.

References

[1]

Paulo Sérgio Almeida, Carlos Baquero, and Victor Fonte. 2008. Interval tree clocks. In Proceedings of the 12th International Conference on Principles of Distributed Systems. Springer, 259--274.

Digital Library

[2]

Carlos Baquero and Nuno Preguiça. 2016. Why logical clocks are easy. Queue 14, 1 (2016), 60.

Digital Library

[3]

Carlos Baquero and Nuno Preguiça. 2016. Why logical clocks are easy. Commun. ACM 59, 4 (2016), 43--47.

Digital Library

[4]

Andrew P. Black, Norman C. Hutchinson, Eric Jul, and Henry M. Levy. 2007. The Development of the Emerald Programming Language. In Proceedings of the 3rd ACM SIGPLAN Conference on History of Programming Languages. 11--1--11--51.

Digital Library

[5]

Saksham Chand and Yanhong A. Liu. 2018. Simpler Specifications and Easier Proofs of Distributed Algorithms Using History Variables. In Proceedings of the 10th NASA Formal Methods Symposium. Springer, 70--86.

[6]

Saksham Chand, Yanhong A. Liu, and Scott D. Stoller. 2016. Formal Verification of Multi-Paxos for Distributed Consensus. In Proceedings of the 21st International Symposium on Formal Methods. Springer, 119--136.

[7]

Colin J. Fidge. 1988. Timestamps in Message-Passing Systems That Preserve the Partial Ordering. In Proceedings of the 11th Australian Computer Science Conference. 56--66.

[8]

Wan Fokkink. 2013. Distributed Algorithms: An Intuitive Approach. MIT Press.

Digital Library

[9]

Vijay K. Garg. 2002. Elements of Distributed Computing. Wiley.

Digital Library

[10]

Sukhendu Kanrar, Nabendu Chaki, and Samiran Chattopadhyay. 2018. Concurrency Control in Distributed System Using Mutual Exclusion. Springer.

Digital Library

[11]

Dilsun Kaynar, Nancy Lynch, Roberto Segala, and Frits Vaandrager. 2010. The Theory of Timed I/O Automata (2nd ed.). Morgan & Claypool.

Digital Library

[12]

A.D. Kshemkalyani and M. Singhal. 2008. Distributed Computing: Principles, Algorithms, and Systems. Cambridge University Press.

Digital Library

[13]

Leslie Lamport. 1978. Time, Clocks, and the Ordering of Events in a Distributed System. Commun. ACM 21, 7 (1978), 558--565.

Digital Library

[14]

Leslie Lamport. 2000. Distributed Algorithms in TLA+. PODC 2000 Tutorial https://www.podc.org/podc2000/lamport.html.

Digital Library

[15]

Leslie Lamport. 2002. Specifying Systems: The TLA+ Language and Tools for Hardware and Software Engineers. Addison-Wesley.

Digital Library

[16]

Jim Larson. 2009. Erlang for Concurrent Programming. Commun. ACM 52, 3 (2009), 48--56.

Digital Library

[17]

Barbara Liskov. 1988. Distributed Programming in Argus. Commun. ACM 31, 3 (Mar. 1988), 300--312.

Digital Library

[18]

Yanhong A. Liu, Jon Brandvein, Scott D. Stoller, and Bo Lin. 2016. Demand-Driven Incremental Object Queries. In Proceedings of the 18th International Symposium on Principles and Practice of Declarative Programming. ACM Press, 228--241.

Digital Library

[19]

Yanhong A. Liu, Saksham Chand, and Scott D. Stoller. 2017. Moderately Complex Paxos Made Simple: High-Level Specification of Distributed Algorithm. Computing Research Repository arXiv:1704.00082 {cs.DC} (2017).

[20]

Yanhong A. Liu, Michael Gorbovitski, and Scott D. Stoller. 2009. A Language and Framework for Invariant-Driven Transformations. In Proceedings of the 8th International Conference on Generative Programming and Component Engineering. ACM Press, 55--64.

Digital Library

[21]

Yanhong A. Liu, Scott D. Stoller, Michael Gorbovitski, Tom Rothamel, and Yanni E. Liu. 2005. Incrementalization Across Object Abstraction. In Proceedings of the 20th ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications. 473--486.

Digital Library

[22]

Yanhong A. Liu, Scott D. Stoller, and Bo Lin. 2012. High-Level Executable Specifications of Distributed Algorithms. In Proceedings of the 14th International Symposium on Stabilization, Safety, and Security of Distributed Systems. Springer, 95--110.

Digital Library

[23]

Yanhong A. Liu, Scott D. Stoller, and Bo Lin. 2017. From Clarity to Efficiency for Distributed Algorithms. ACM Transactions on Programming Languages and Systems 39, 3 (May 2017), 12:1--12:41.

Digital Library

[24]

Yanhong A. Liu, Scott D. Stoller, Bo Lin, and Michael Gorbovitski. 2012. From Clarity to Efficiency for Distributed Algorithms. In Proceedings of the 27th ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages and Applications. 395--410.

Digital Library

[25]

Sandeep Lodha and Ajay Kshemkalyani. 2000. A fair distributed mutual exclusion algorithm. IEEE Transactions on Parallel and Distributed Systems 11, 6 (2000), 537--549.

Digital Library

[26]

Nancy A. Lynch. 1996. Distributed Algorithms. Morgan Kaufman.

Digital Library

[27]

Friedemann Mattern. 1989. Virtual Time and Global States of Distributed Systems. In Proceedings of the International Workshop on Parallel and Distributed Algorithms. North-Holland, 120--131.

[28]

Stephan Merz. 2010. Lamport's algorithm. Email with Annie Liu.

[29]

Robert Paige and Shaye Koenig. 1982. Finite Differencing of Computable Expressions. ACM Transactions on Programming Languages and Systems 4, 3 (1982), 402--454.

Digital Library

[30]

Said K. Rahimi and William R. Franta. 1982. Fair Timestamp Allocation in Distributed Systems. In Proceedings of the 1982 National Computer Conference. 589--594.

Digital Library

[31]

Kerry Raymond. 1989. A tree-based algorithm for distributed mutual exclusion. ACM Transactions on Computer Systems 7, 1 (Jan. 1989), 61--77.

Digital Library

[32]

Michel Raynal. 1986. Algorithms for Mutual Exclusion. MIT Press.

Digital Library

[33]

Michel Raynal. 1988. Distributed Algorithms and Protocols. Wiley.

Digital Library

[34]

Glenn Ricart and Ashok K. Agrawala. 1981. An Optimal Algorithm for Mutual Exclusion in Computer Networks. Commun. ACM 24, 1 (1981), 9--17.

Digital Library

[35]

PC Saxena and Jagmohan Rai. 2003. A survey of permission-based distributed mutual exclusion algorithms. Computer standards & interfaces 25, 2 (2003), 159-- 181.

Digital Library

[36]

Ichiro Suzuki and Tadao Kasami. 1985. A Distributed Mutual Exclusion Algorithm. ACM Transactions on Computer Systems 3, 4 (1985), 344--349.

Digital Library

[37]

Robbert van Renesse and Deniz Altinbuken. 2015. Paxos Made Moderately Complex. Comput. Surveys 47, 3 (Feb. 2015), 42:1--42:36.

Digital Library

[38]

Martin G. Velazquez. 1993. A Survey of Distributed Mutual Exclusion Algorithms. Technical Report CS-93--116. Department of Computer Science, Colorado State University. http://www.cs.colostate.edu/pubserv/pubs/ Velazquez-TechReports-Reports-1993-tr-116.pdf

Cited By

Liu YStoller S(2020)Assurance of Distributed Algorithms and Systems: Runtime Checking of Safety and LivenessRuntime Verification10.1007/978-3-030-60508-7_3(47-66)Online publication date: 2-Oct-2020
https://doi.org/10.1007/978-3-030-60508-7_3
Liu YStoller SRobinson PEllen F(2019)From Classical to Blockchain ConsensusProceedings of the 2019 ACM Symposium on Principles of Distributed Computing10.1145/3293611.3338022(544-545)Online publication date: 16-Jul-2019
https://dl.acm.org/doi/10.1145/3293611.3338022
Stoller SLiu Y(2019)Algorithm Diversity for Resilient SystemsData and Applications Security and Privacy XXXIII10.1007/978-3-030-22479-0_19(359-378)Online publication date: 11-Jun-2019
https://doi.org/10.1007/978-3-030-22479-0_19

Index Terms

Logical Clocks Are Not Fair: What Is Fair?
1. Computing methodologies
  1. Distributed computing methodologies
    1. Distributed algorithms
    2. Distributed programming languages

Recommendations

Performance evaluation of a fair backoff algorithm for IEEE 802.11 DFWMAC
MobiHoc '02: Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing

Due to hidden terminals and a dynamic topology, contention among stations in an ad-hoc network is not homogeneous. Some stations are at a disadvantage in opportunity of access to the shared channel and can suffer severe throughput degradation when the ...
Enhanced binary exponential backoff algorithm for fair channel access in the ieee 802.11 medium access control protocol

The medium access control protocol determines system throughput in wireless mobile ad hoc networks following the ieee 802.11 standard. Under this standard, asynchronous data transmissions have a defined distributed coordination function that allows ...
Fair TDMA scheduling in wireless multihop networks

In wireless multihop networks, communication between two end-nodes is carried out by hopping over multiple wireless links. However, the fact that each node has to transmit not only its own traffic, but also traffic on behalf of other nodes, leads to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

ApPLIED '18: Proceedings of the 2018 Workshop on Advanced Tools, Programming Languages, and PLatforms for Implementing and Evaluating Algorithms for Distributed systems

July 2018

54 pages

ISBN:9781450357753

DOI:10.1145/3231104

General Chairs:
Chryssis Georgiou
University of Cyprus, Cyprus
,
Elad M. Schiller
Chalmers University of Technology, Sweden

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

In-Cooperation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 July 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

PODC '18

PODC '18: ACM Symposium on Principles of Distributed Computing

July 27, 2018

Egham, United Kingdom

Acceptance Rates

ApPLIED '18 Paper Acceptance Rate 3 of 4 submissions, 75%;

Overall Acceptance Rate 3 of 4 submissions, 75%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
296
Total Downloads

Downloads (Last 12 months)67
Downloads (Last 6 weeks)13

Reflects downloads up to 03 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Liu YStoller S(2020)Assurance of Distributed Algorithms and Systems: Runtime Checking of Safety and LivenessRuntime Verification10.1007/978-3-030-60508-7_3(47-66)Online publication date: 2-Oct-2020
https://doi.org/10.1007/978-3-030-60508-7_3
Liu YStoller SRobinson PEllen F(2019)From Classical to Blockchain ConsensusProceedings of the 2019 ACM Symposium on Principles of Distributed Computing10.1145/3293611.3338022(544-545)Online publication date: 16-Jul-2019
https://dl.acm.org/doi/10.1145/3293611.3338022
Stoller SLiu Y(2019)Algorithm Diversity for Resilient SystemsData and Applications Security and Privacy XXXIII10.1007/978-3-030-22479-0_19(359-378)Online publication date: 11-Jun-2019
https://doi.org/10.1007/978-3-030-22479-0_19

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents