Distributed System

Semester VI · BCA 355 · 3 credits

7 units · 50 teaching hours · about 3 h of reading

0 / 7 chapters done

Introduction, Goals, Architectures and Naming 7 hrs · 23 min read · 4 figures
The syllabus asks for
- What is a distributed system?
- Goals
- The eight fallacies
- System architectures
- Processes, threads and servers
- Naming and the Chord DHT
- System models
- Seeing distributed systems: hardware, architecture and numbers
Key points
- A distributed system is autonomous nodes cooperating by messages to look like one system; it has concurrency, no global clock and independent failures.
- Goals: resource sharing, transparency (access, location, migration, replication, concurrency, failure), openness, scalability (size, geography, administration) and dependability.
- Serial availability multiplies (five 99.9% services give 99.5010%); parallel replicas raise it as 1 − (1 − a)ⁿ; latency is bounded by distance.
- Architectures: client-server (tiers), P2P (unstructured, structured DHT, hybrid); middleware hides heterogeneity.
- Chord places keys on a ring with O(log N) lookup; DNS combines partitioning and replication.
Read the chapter
Communication: Sockets, RPC, RMI, gRPC and Message Queues 8 hrs · 23 min read · 4 figures
The syllabus asks for
- Sockets
- Marshalling and serialization
- Remote procedure call
- Remote method invocation (RMI)
- gRPC
- Message-oriented communication
- Seeing communication: wires, handshakes, stubs and queues
Key points
- Sockets expose TCP streams (reliable, ordered, need framing) and UDP datagrams (lossy, message-preserving); TCP's reliability does not replace end-to-end application acknowledgements.
- Marshalling fixes byte order and layout: the 11-byte fixed record and the 35-byte JSON for the same data; protobuf varints encode 150 as 96 01 and 300 as ac 02.
- RPC hides communication behind stubs, but the caller must still handle timeouts; at-least-once plus a request ID gives at-most-once. The retry experiment charged 300 instead of 100 without dedup.
- RMI passes remote references; gRPC uses protobuf over HTTP/2 with unary and streaming calls and deadlines.
- Message queues decouple sender and receiver in time and space; at-least-once delivery means duplicates and reordering, so handlers must be idempotent.
Read the chapter
Time, Clocks and Global State 8 hrs · 23 min read · 4 figures
The syllabus asks for
- Physical clocks, drift and skew
- Cristian's algorithm
- The Berkeley algorithm
- The Network Time Protocol
- Happened-before and Lamport clocks
- Vector clocks
- Seeing time: clocks, clock servers and event diagrams
Key points
- Physical clocks drift at ρ (about 10 ppm = 0.864 s/day); synchronisation must repeat about every δ/2ρ.
- Cristian: estimate = Tₛ + RTT/2, accuracy ± (RTT/2 − min). Berkeley: average clock differences and send each node its adjustment. NTP: θ = ((t₁−t₀)+(t₂−t₃))/2, δ = (t₃−t₀) − (t₂−t₁); path asymmetry remains as error.
- Happened-before is a partial order; Lamport clocks give L(a) < L(b) whenever a → b but not the converse; vector clocks give a → b ⇔ V(a) < V(b) and expose concurrency.
Read the chapter
Coordination: Mutual Exclusion and Leader Election 7 hrs · 22 min read · 4 figures
The syllabus asks for
- The mutual exclusion problem
- Centralised algorithm
- Ricart–Agrawala (distributed, timestamp-based)
- Maekawa's quorum algorithm
- Token-ring algorithm
- Leader election
- In practice: leases and coordination services
- Seeing coordination: shared hardware, quorums and elections
Key points
- Mutual exclusion must be safe, live and fair; compare algorithms by messages and delay.
- Centralised: 3 messages; Ricart–Agrawala: 2(N − 1) messages and a timestamp order (24 messages for N = 4 in the simulation); Maekawa: about 3√N messages using intersecting quorums; token ring: token hops, with loss to handle.
- Bully: highest live id wins; best case 6 messages, worst case 41 for N = 7 with the top process dead. Ring: 2 × live processes = 12 messages.
- Leases and fencing tokens plus consensus-backed services replace hand-written algorithms in practice.
Read the chapter
Distributed Transactions and Concurrency Control 7 hrs · 21 min read · 4 figures
The syllabus asks for
- Transactions and ACID
- Atomic commit: two-phase commit
- Three-phase commit
- Concurrency control: serializability
- Distributed deadlocks
- Sagas for microservices
- Seeing transactions: logs, graphs and compensations
Key points
- Distributed atomic commit uses a coordinator; 2PC votes then decides and costs 4N messages for N participants (12 for N = 3), but blocks when the coordinator crashes in the READY state.
- 3PC adds PRE-COMMIT and avoids blocking only under synchrony; modern systems use consensus-replicated commit instead.
- A schedule is conflict-serializable iff its precedence graph is acyclic; strict 2PL guarantees it; timestamp ordering and optimistic control are alternatives.
- Distributed deadlocks are cycles in the global wait-for graph; edge chasing detects them with probes; wait-die and wound-wait prevent them.
- Sagas replace distributed ACID with local transactions plus compensation.
Read the chapter
Replication, Consistency Models and Consensus 8 hrs · 22 min read · 4 figures
The syllabus asks for
- Replication
- Consistency models
- The CAP theorem and PACELC
- Quorums
- Consensus and Paxos
- Raft
- Seeing replication: copies, quorums, proposals and logs
Key points
- Replicate for availability, performance and fault tolerance; state machine replication keeps replicas identical by ordering commands through consensus.
- Models: linearizable ⊃ sequential ⊃ causal ⊃ eventual (in strength). A stale read after a completed write is sequentially consistent but not linearizable (H2).
- CAP: under partition choose consistency or availability; PACELC adds latency vs consistency otherwise.
- Quorums: R + W > N forces intersection; enumeration found 10 disjoint pairs for (N, W, R) = (5, 2, 3) and none for (5, 3, 3).
- Paxos is safe because a new proposer must adopt the highest accepted value from its majority; Raft uses terms, randomised timeouts, majority commit and the current-term rule.
Read the chapter
Fault Tolerance and Distributed File Systems 5 hrs · 22 min read · 4 figures
The syllabus asks for
- Dependability and failure detection
- Byzantine agreement
- Recovery: checkpoints and snapshots
- Distributed file systems
- Seeing failure: walls, disks, racks and snapshots
Key points
- Redundancy is the basis of fault tolerance; failure detectors suspect silent nodes by timeout; crash tolerance needs 2f + 1 replicas for majorities, Byzantine tolerance 3f + 1.
- OM(1) works for n = 4 and fails validity for n = 3 with one traitor; PBFT quorums are 2f + 1 of 3f + 1.
- Chandy–Lamport records a consistent global state (90 + 55 + 5 = 150 here); checkpointing avoids the domino effect when coordinated.
- NFS is stateless with close-to-open consistency; AFS caches whole files with callbacks; GFS/HDFS use a master plus large replicated blocks with rack-aware placement.
Read the chapter