DistributedSystemNotes icon indicating copy to clipboard operation
DistributedSystemNotes copied to clipboard

Published 20 hours ago • verified publisher icon ChrisWhealy
→

Metadata

Notes on Lindsey Kuper's lectures on Distributed Systems

Distributed Systems

Lecture notes for course CSE138, Spring 2020 given by Prof Lindsey Kuper, Assistant Professor of Computing at UCSC

Due to the Covid-19 lockdown being enforced at the time, these lectures had to be delivered online and are available on YouTube and Twitch

This series of lectures also includes a discussion panel with recent grad students and two guest lecturers. Notes have not been created for these events; however, you can watch the videos here:

Date Description Subjects Recapped
Lecture 1 There are no notes for this lecture as it was concerned with course administration and logistics
Lecture 2
April 1st, 2020		 Distributed Systems: What and why?
Time and clocks
Lecture 3
April 3rd, 2020		 Lamport diagrams
Causality and the "happens before" relation
Network models
State and events
Partial orders
Lecture 4
April 6th, 2020		 Total orders and Lamport clocks Partial orders
Happens before relation
Lecture 5
April 8th, 2020		 Vector clocks
Protocol runs and anomalies
Message Delivery vs. Message Receipt
FIFO delivery		 Lamport Clocks
Lecture 6
April 10th, 2020		 Causal delivery
Totally-ordered delivery
Implementing FIFO delivery
Preview of implementing causal broadcast		 Delivery vs. Receipt
FIFO delivery
Lecture 7
April 13th, 2020		 Implementing causal broadcast
Uses of causality in distributed systems
Consistent snapshots
Preview of the Chandy-Lamport snapshot algorithm		 Causal anomalies and vector clocks
Lecture 8
April 15th, 2020		 Chandy-Lamport Snapshot Algorithm
Lecture 9
April 17th, 2020		 Chandy-Lamport wrap-up: limitations, assumptions and properties
Uses of snapshots
Centralized vs. decentralized algorithms
Safety and liveness		 Delivery guarantees and protocols
Lecture 10
April 20th, 2020		 Reliable delivery
Fault classification and fault models
The Two Generals problem		 Safety and liveness
Lecture 11
April 22nd, 2020		 Implementing reliable delivery
Idempotence
At-least-once/at-most-once/exactly-once delivery
Unicast/Broadcast/Multicast
Reliable broadcast
Implementing reliable broadcast
Preview of replication
Lecture 12
April 24th, 2020		 Replication
Total order vs. determinism
Consistency models: FIFO, causal and strong
Primary-backup replication
Chain replication
Latency and throughput
Lecture 13
April 27th, 2020		 Pause for breath!
Wrapping up replication techniques
Lecture 14
May 1st, 2020		 Handling node failure in replication protocols
Introduction to consensus
Problems equivalent to consensus
The FLP result
Introduction to Paxos		 Strongly consistent replication protocols
Lecture 15
May 4th, 2020		 Paxos: the interesting parts
Lecture 16
May 6th, 2020		 Paxos wrap-up: Non-termination, Multi-Paxos, Fault tolerance
Other consensus protocols: Viewstamped Replication, Zab, Raft
Passive vs. Active (state machine) replication
Lecture 17
May 8th, 2020		 Eventual consistency
Strong convergence and strong eventual consistency
Introduction to application-specific conflict resolution
Network partitions
Availability
The consistency/availability trade-off
Lecture 18
May 11th, 2020		 Dynamo: A review of old ideas
  • Availability
  • Network partitions
  • Eventual consistency
  • Vector clocks
  • Application-specific conflict resolution
Introduction to:
  • Anti-entropy with Merkle trees
  • Gossip
  • Quorum consistency
Lecture 19
May 13th, 2020		 More about Quorum Consistency
Introduction to sharding
Consistent hashing
Lecture 20
May 18th, 2020		 Online systems vs. Offline systems
Raw data vs. Derived data
Introduction to Google's MapReduce framework
MapReduce example: transform a forward index into an inverted index
Lecture 21
May 20th, 2020		 MapReduce
  • Types
  • Approach to fault tolerance
  • Combine functions
  • More examples
 MapReduce phases
Lecture 22
May 29th, 2020		 The math behind replica conflict resolution
  • Upper bounds
  • Least upper bounds
  • Join-semilattices
 Strong convergence
Partial orders
Lecture 23
June 1st, 2020		 Filling in the gaps: Overviews of 2-phase commit and Practical Byzantine Fault Tolerance (PBFT)
Quick overview of the history of:
  • Lamport and Vector Clocks
  • Replication Strategies
  • Consensus
  • Replication Needs Consensus

← Metadata

450
Stars
85
Forks
Watchers

Owner

verified publisher icon ChrisWhealy

Metadata

Notes on Lindsey Kuper's lectures on Distributed Systems

Back