Distributed systems

Distributed Systems

Course

  1. Revision Deck - Martin Kleppmann (PDF) for the youtube lecture series

  2. Notes on Theory of Distributed Systems (PDF)

NTP Clock sync:

Estimated clock Skew - θ = (t2 − t1 + t3 − t4) / 2

Monotonic Clocks:

  • Systems maintain a different monotonic clock

  • it measures the time from some arbitrary local event like a server restart

  • use for benchmarking or finding time lapse between two events on the system instead of the global time which is prone to changes due to corrections.

Lamport and Vector Clocks

Lamport Clock

  • confident event A happened after B.

  • Keeps a local counter and increments it every time any event occurs or is sent or received.

Vector Clock

  • Fully confident about the causality of non-concurrent events.

  • Vector Clock maintains an array of counters with one entry per node.

Common solutions to build best effort systems

  • deterministic - Order inputs for state machine replication,

  • commutative - f(g(x)) = g(f(x))

  • idempotent - on every event send a unique identifier from the source (nodeid/userid, action timestamp)

  • tolerates-message-loss with retries (exponential backoff in the real world)

CRDT

Watch on youtube

📌 Tagged As