Distributed Computing

A distributed system is one in which the failure of a computer you didn't even know existed can render your own computer unusable.

— Leslie Lamport (https://research.microsoft.com/en-us/um/people/lamport/pubs/distributed-system.txt)

Terms of Interest

• Consistent Hashing: https://en.wikipedia.org/wiki/Consistent_hashing
  • Jump: http://arxiv.org/abs/1406.2294
• Conflict-free Replicated Data Type (CRDT): https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type
  • Data structure that facilitates merging diverged versions. One example is collaborative editing, e.g. if user edits todo list on two temporarily offline devices, how can the changes be reconciled when the devices are synced with the server later?
  • http://christophermeiklejohn.com/crdt/2014/07/22/readings-in-crdts.html
• Harvest, Yield, and Scalable Tolerant Systems http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.24.3690&rep=rep1&type=pdf
  • Harvest: Completeness of response
  • Yield: Probability of completing a request
  • Paper proposes ways to sacrifice harvest to increase availability (yield): return incomplete/approximate results or decompose system into non-fault tolerant subsystems and handle failure at a higher layer

Concepts

Lamport Clocks

Because physical time can vary from system to system, how can we accurately order a series of events in a distributed system?

Time, Clocks, and Ordering in a Distributed System

Byzantine Generals Problem

TODO: Add description

Dr. Dobbs | The Byzantine Generals Problem

Chord

A peer-to-peer Distributed HashTable (DHT) algorithm/protocol using consistent hashing to reduce shifting upon node join/leave.

Chord: A scalable peer-to-peer lookup service for internet applications

Dynamo

Dynamo: Amazon's Highly Available Key-value Store

Paxos

TODO: Add information

• Paxos Made Simple
• Paxos Made Live

Reading Lists

• Readings in Distributed Systems
• A Distributed Systems Reading List
• UIUC CS598IG: Adv. Topics in Dist. Sys. Spring