Distributed Systems ClassicsDistributed Systems ClassicsNicolae Vartolomei · 2017/11, updated on 2022/09A selected list of timeless and influential papers in distributed systems that
shaped the research in the field. Intended to serve as a good starting point for
a better understanding of the problem space.Leslie Lamport. 1978. Time, clocks, and the ordering of events in a
distributed system. https://doi.org/10.1145/359545.359563Leslie Lamport, Robert Shostak, and Marshall Pease. 1982. The Byzantine
Generals Problem. https://doi.org/10.1145/357172.357176K. Mani Chandy and Leslie Lamport. 1985. Distributed snapshots: determining
global states of distributed systems. https://doi.org/10.1145/214451.214456Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. 1985.
Impossibility of distributed consensus with one faulty process. https://doi.org/10.1145/3149.214121Brian M. Oki and Barbara H. Liskov. 1988. Viewstamped Replication: A New
Primary Copy Method to Support Highly-Available Distributed Systems. https://doi.org/10.1145/62546.62549Leslie Lamport. 1998. The part-time parliament. https://doi.org/10.1145/279227.279229Leslie Lamport. 2001. Paxos Made Simple. https://www.microsoft.com/en-us/research/publication/paxos-made-simple/Satoshi Nakamoto. 2008. Bitcoin: A Peer-to-Peer Electronic Cash System. https://bitcoin.org/en/bitcoin-paperMarc Shapiro, Nuno Preguiça, Carlos Baquero, and Marek Zawirski. 2011.
Conflict-free replicated data types. https://dl.acm.org/doi/10.5555/2050613.2050642Diego Ongaro and John Ousterhout. 2014. In search of an understandable
consensus algorithm. https://dl.acm.org/doi/10.5555/2643634.2643666Nicolae Vartolomei

The selected list of papers provides a foundation for understanding the essential research areas that have shaped the field of distributed systems. Early foundational work addressed fundamental issues related to time and ordering in distributed environments, as seen in Leslie Lamport's 1978 work concerning time, clocks, and the ordering of events. Subsequent research tackled complex problems involving fault tolerance and coordination. Leslie Lamport, along with Robert Shostak and Marshall Pease, addressed the theoretical limits of consensus with one faulty process in their 1982 work on the Byzantine Generals Problem, which highlighted the challenges of achieving agreement in unreliable systems. Meanwhile, Chandy and Lamport explored the concept of distributed snapshots in 1985 to determine the global states of distributed systems. The impossibility of distributed consensus with a single faulty process was further explored by Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson in 1985.

The focus shifted to methods for maintaining availability and consistency. Brian M. Oki and Barbara H. Liskov introduced Viewstamped Replication in 1988 as a novel primary copy method designed to support highly-available distributed systems. Further explorations in the area of distributed coordination came with Leslie Lamport’s 1998 paper on the part-time parliament. Later work on consensus was advanced by Leslie Lamport in 2001 with Paxos Made Simple.

The progression continued into modern distributed data management, where conflict-free replicated data types were proposed by Marc Shapiro, Nuno Preguiça, Carlos Baquero, and Marek Zawirski in 2011. The need for understandable and practical consensus algorithms was emphasized by Diego Ongaro and John Ousterhout in 2014. Finally, the context of modern distributed systems was illustrated by Satoshi Nakamoto’s 2008 work on Bitcoin, which introduced concepts pertaining to peer-to-peer electronic cash systems. Collectively, these works illustrate the evolution of distributed systems research from establishing basic temporal and fault constraints to developing robust mechanisms for state determination, replication, and achieving consensus in highly asynchronous and unreliable environments.