Courses/Distributed Systems

Distributed Systems

CS3.401

Prof. Kishore Kothapalli•Monsoon 2025-26•4 credits

Formulas & Diagrams

High-ROI section — formulas improve marks, diagrams improve recall.

Formulas

Scalar clock receive rule (R2)

—

c_{i} := max (c_{i}, t_{msg}) + d

On receive of message timestamped t, set local clock to max(local, t) plus d (usually 1).

Vector clock receive rule

—

\forall k : V_{i} [k] := max (V_{i} [k], V_{m} [k]); V_{i} [i] := V_{i} [i] + 1

Component-wise max then increment own. Strongly consistent: e → e' ⇔ V(e) < V(e').

Vector clock comparison

—

V_{h} < V_{k} ⟺ (\forall i : V_{h} [i] \leq V_{k} [i]) \land (\exists i : V_{h} [i] < V_{k} [i])

Strict less-than: dominated component-wise with at least one strict. Otherwise V_h || V_k (concurrent).

Matrix clock obsolete-message GC

—

k min M_{i} [k, i] \geq t \Rightarrow discard msgs \leq t

When every process is known to have seen i's clock pass t, i can safely discard buffered messages with timestamp ≤ t.

Lamport's DME message count

—

3 (N - 1) messages per CS

REQUEST + REPLY + RELEASE to each of the N-1 other sites.

Ricart-Agrawala message count

—

2 (N - 1) messages per CS

REQUEST + REPLY; no RELEASE because deferred replies serve the same purpose.

Maekawa message count (V2)

—

3 N (V1) up to 5 N (V2 with FAILED/INQUIRE/YIELD)

Quorum-based. K = D = √N optimal. V2 adds 3 messages to break deadlocks.

Byzantine resilience bound

—

n \geq 3 f + 1 \land rounds \geq f + 1

f Byzantine processes need >2/3 honest. At least f+1 rounds. FLP: impossible in async even with 1 crash.

Phase King decision rule

—

v_{i} := {majority value v_{king} if multiplicity > n /2 + f otherwise

Adopt majority only if strictly majority + Byzantine slack; else trust the king. Needs n ≥ 4f+1.

Crash-failure consensus message complexity

—

(f + 1) \cdot n^{2} messages

f+1 rounds × n² per round (every non-crashed process sends to all).

GHS distributed MST complexity

—

O (N lo g N + E) messages, O (N lo g N) time

Optimal among comparison-based distributed MST. N log N from up-to-log-N level increments × initiates.

DME throughput

—

Throughput = \frac{1}{SD + E}

Inverse of synchronisation delay + average CS execution time. Higher SD ⇒ lower throughput.

Diagrams

CAP triangle

Triangle with C, A, P at corners. Real systems sit on an edge (CP or AP). 'CA' point unreachable because partitions are real.

[ diagram placeholder ]

Vector-clock lattice

2D grid for 2 processes; events as dots; arrows show happened-before; concurrent events are non-comparable in the partial order.

[ diagram placeholder ]

Chandy-Lamport marker flow

3 processes with bidirectional FIFO channels; initiator P1 fires markers; subsequent first-vs-later marker rules annotated.

[ diagram placeholder ]

BSS causal-delivery buffer

Pi receives m from Pj; check Vm[j] = Vi[j]+1 and Vm[k] ≤ Vi[k] ∀k. If false, buffer; deliver later when conditions met.

[ diagram placeholder ]

DME comparison table

Rows = Lamport / Ricart-Agrawala / Maekawa / Suzuki-Kasami / Raymond. Cols = Type, Msgs/CS, Sync Delay, Assumptions.

[ diagram placeholder ]

Maekawa quorum lattice

N=7 example with √N=3 quorums. Show pairwise intersection — the common member arbitrates between any two requesters.

[ diagram placeholder ]

Raymond tree + Holder pointers

Balanced binary tree of 7 nodes; Holder pointers all converge to root (current token holder); REQUEST flows up, token flows down along Holder chain.

[ diagram placeholder ]

Wait-For Graph + knot

8 processes; SCC of 4 forms a knot (no outgoing edges from SCC); other 4 outside lead into SCC but are also deadlocked under OR model.

[ diagram placeholder ]

Chandy-Misra-Haas probe flow

4-process cycle; probe(1,1,2) → (1,2,3) → (1,3,4) → (1,4,1) returns to initiator.

[ diagram placeholder ]

OM(m) recursion tree

OM(2) for N=7, m=2. General at root; each lieutenant becomes a general for OM(1) over the remaining N-2; final majority at each leaf.

[ diagram placeholder ]

2PC timeline (coordinator vs participants)

Vertical lines for C and Pi; arrows for PREPARE, READY/NO, COMMIT/ABORT. Block-region shaded if C crashes after all ready.

[ diagram placeholder ]

3PC timeline with PRE-COMMIT

Same as 2PC plus PRE-COMMIT phase + acks. Show recovery path: if any survivor has <pre-commit T>, new coordinator commits.

[ diagram placeholder ]

Raft state machine

Three states: Follower → Candidate (timeout) → Leader (majority). Higher-term observed → revert to Follower.

[ diagram placeholder ]

GHS fragment merge

Two fragments at level L with mutual MWOE → merge to L+1 with name = w(MWOE) ('core edge').

[ diagram placeholder ]

GFS three-component architecture

Master with metadata + log; multiple chunkservers with 64 MB chunks replicated 3× across racks; clients consulting master then chunkservers directly.

[ diagram placeholder ]

GFS write flow (pipelined data + control)

Data flows linearly through closest replica chain; control flow client→primary→secondaries in star.

[ diagram placeholder ]