Distributed Systems pt.0

This post is a work in progress.

Introduction

Distributed computing systems are an important reality to wrestle with at many levels of technical exposure. Similar to the concept of a cluster I discussed in this blog post, a distributed system is “a collection of autonomous computing elements that appears to its users as a single coherent system” (van Steen, Tanenbaum). Distributed computing environments introduce new dynamics which can affect application development. Enterprise-level corporations (< 500-1000 employees) are best known to operate in distributed environments, and any organization larger than that is guaranteed to use distributed computing. To contrast a cluster from a distributed system, I would say that a cluster is a galaxy and a distributed computing environment is a universe.

It is common for someone new to a distributed system to make some basic assumptions which will cause more issues given time. These assumptions are known as the Fallacies of Distributed Computing.

Fallacies of Distributed Computing

The fallacies of distributed computing are:

1. The network is reliable;
2. Latency is zero;
3. Bandwidth is infinite;
4. The network is secure;
5. Topology doesn’t change;
6. There is one administrator;
7. Transport cost is zero;
8. The network is homogeneous.

Reading List

The reading list below is a copy of the currently available version written by Christopher Meiklejohn.

Consensus

The problems of establishing consensus in a distributed system.

• In Search of an Understandable Consensus Algorithm

  Diego Ongaro, John Ousterhout 2013

• A Simple Totally Ordered Broadcast Protocol

  Benjamin Reed, Flavio P. Junqueira 2008

• Paxos Made Live - An Engineering Perspective

  Tushar Deepak Chandra, Robert Griesemer, Joshua Redstone 2007

• The Chubby Lock Service for Loosely-Coupled Distributed Systems

  Mike Burrows 2006

• Paxos Made Simple

  Leslie Lamport 2001

• Impossibility of Distributed Consensus with One Faulty Process

  Michael Fischer, Nancy Lynch, Michael Patterson 1985

• The Byzantine Generals Problem

  Leslie Lamport 1982

Consistency

Types of consistency, and practical solutions to solving ensuring atomic operations across a set of replicas.

• Highly Available Transactions: Virtues and Limitations

  Peter Bailis, Aaron Davidson, Alan Fekete, Ali Ghodsi, Joseph M. Hellerstein, Ion Stoica 2013

• Consistency Tradeoffs in Modern Distributed Database System Design

  Daniel J. Abadi 2012

• CAP Twelve Years Later: How the “Rules” Have Changed

  Eric Brewer 2012

• Calvin: Fast Distributed Transactions for Partitioned Database Systems

  Alexander Thomson, Thaddeus Diamond, Shu-Chun Weng, Kun Ren, Philip Shao, Daniel J. Abadi 2012

• Optimistic Replication

  Yasushi Saito and Marc Shapiro 2005

• Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services

  Seth Gilbert, Nancy Lynch 2002

• Harvest, Yield, and Scalable Tolerant Systems

  Armando Fox, Eric A. Brewer 1999

• Linearizability: A Correctness Condition for Concurrent Objects

  Maurice P. Herlihy, Jeannette M. Wing 1990

• Time, Clocks, and the Ordering of Events in a Distributed System

  Leslie Lamport 1978

Conflict-free data structures

Studies on data structures which do not require coordination to ensure convergence to the correct value.

• A Comprehensive Study of Convergent and Commutative Replicated Data Types

  Mark Shapiro, Nuno Preguiça, Carlos Baquero, Marek Zawirski 2011

• A Commutative Replicated Data Type For Cooperative Editing

  Nuno Preguica, Joan Manuel Marques, Marc Shapiro, Mihai Letia 2009

• CRDTs: Consistency Without Concurrency Control

  Mihai Letia, Nuno Preguiça, Marc Shapiro 2009

Distributed programming

Languages aimed towards disorderly distributed programming as well as case studies on problems in distributed programming.

• Logic and Lattices for Distributed Programming

  Neil Conway, William Marczak, Peter Alvaro, Joseph M. Hellerstein, David Maier 2012

• Dedalus: Datalog in Time and Space

  Peter Alvaro, William R. Marczak, Neil Conway, Joseph M. Hellerstein, David Maier, Russell Sears 2011

• MapReduce: Simplified Data Processing on Large Clusters

  Jeffrey Dean, Sanjay Ghemawat 2004

• A Note On Distributed Computing

  Samuel C. Kendall, Jim Waldo, Ann Wollrath, Geoff Wyant 1994

Systems

Implemented and theoretical distributed systems.

• Spanner: Google’s Globally-Distributed Database

  James C. Corbett, Jeffrey Dean, Michael Epstein, Andrew Fikes, Christopher Frost, JJ Furman,Sanjay Ghemawat, Andrey Gubarev, Christopher Heiser, Peter Hochschild, Wilson Hsieh,Sebastian Kanthak, Eugene Kogan, Hongyi Li, Alexander Lloyd, Sergey Melnik, David Mwaura,David Nagle, Sean Quinlan, Rajesh Rao, Lindsay Rolig, Yasushi Saito, Michal Szymaniak,Christopher Taylor, Ruth Wang, Dale Woodford 2012

• ZooKeeper: Wait-free coordination for Internet-scale systems

  Patrick Hunt, Mahadev Konar, Flavio P. Junqueira, Benjamin Reed 2010

• A History Of The Virtual Synchrony Replication Model

  Ken Birman 2010

• Cassandra — A Decentralized Structured Storage System

  Avinash Lakshman, Prashant Malik 2009

• Dynamo: Amazon’s Highly Available Key-Value Store

  Giuseppe DeCandia, Deniz Hastorun, Madan Jampani, Gunavardhan Kakulapati, Avinash Lakshman, Alex Pilchin, Swaminathan Sivasubramanian, Peter Vosshall and Werner Vogels 2007

• Stasis: Flexible Transactional Storage

  Russell Sears, Eric Brewer 2006

• Bigtable: A Distributed Storage System for Structured Data

  Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C. Hsieh, Deborah A. Wallach, Mike Burrows, Tushar Chandra, Andrew Fikes, and Robert E. Gruber 2006

• The Google File System

  Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung 2003

• Lessons from Giant-Scale Services

  Eric A. Brewer 2001

• Towards Robust Distributed Systems

  Eric A. Brewer 2000

• Cluster-Based Scalable Network Services

  Armando Fox, Steven D. Gribble, Yatin Chawathe, Eric A. Brewer, Paul Gauthier 1997

• The Process Group Approach to Reliable Distributed Computing

  Ken Birman 1993

Books

Overviews and details covering many of the above papers and concepts compiled into single resources.

• Distributed Systems: for fun and profit

  Mikito Takada 2013

• Programming Distributed Computing Systems: A Foundational Approach

  Carlos A.Varela, Gul Agha 2013

• Guide to Reliable Distributed Systems: Building High-Assurance Applications and Cloud-Hosted Services

  Ken Birman 2012

• Introduction to Reliable and Secure Distributed Programming

  Christian Cachin, Rachid Guerraoui, Luís Rodrigues 2011