Distributed_Systems

Distributed Systems Overview using A Stacked Assumption-Relaxation and Constraint-Introduction Framework

Arpit Rathi

---

Abstract

Distributed systems are difficult to reason about primarily because they force several interacting concerns (concurrency, storage, data volume, throughput, network behavior, time, and failure) to be addressed simultaneously. This paper presents a framework for reasoning about distributed systems by starting from an idealized, single-machine baseline in which computation is deterministic, resources are unbounded, and failures never occur. From this baseline, we systematically relax one simplifying assumption at a time, replace it with the corresponding real-world constraint, and examine the mechanisms, trade-offs, and theoretical results that the relaxation makes necessary. The resulting seven-stage progression (processes, storage, data volume, throughput, network, clocks, and failures) reconstructs the major results of distributed systems theory and engineering practice, from ACID transactions and B-trees to CAP/PACELC, replication, vector clocks, consensus, and state machine replication, as consequences of specific, named assumptions being dropped, rather than as an unordered catalogue of mechanisms. The goal is pedagogical: to give practitioners and researchers a single mental model, an "assumption stack," for navigating the field's breadth while retaining conceptual coherence.

---

Table of Contents

• Introduction

• The Assumption–Constraint Framework

• Video Timeline (Course Introduction):

  • 0:00 Course Introduction
  • 3:13 Graphical Legend System
  • 5:05 Assumption-Constraint Framework

• Chapter 1 — Processes

  • 1.1 Foundational Definitions
  • 1.2 ACID Properties
  • 1.3 Achieving Atomicity
  • 1.4 Achieving Isolation
  • 1.5 Algorithms for Preventing Anomalies
  • 1.6 Isolation Levels
  • 1.7 Chapter Summary

• Video Timeline (Chapter 1):

  • 0:00 Relaxing Processes-related Assumptions
  • 2:12 Process, Thread, and Transaction
  • 3:26 ACID
  • 5:01 Write-ahead log
  • 6:30 Concurrency Anomalies (frame-1/2)
  • 7:59 Concurrency Anomalies (frame-2/2)
  • 9:39 OCC vs PCC
  • 11:01 2PL
  • 13:19 MVCC
  • 14:58 Isolation Levels
  • 18:14 Chapter Summary

• Chapter 2 — Storage

  • 2.1 Data Structures
  • 2.2 Data Models
  • 2.3 Specialized Databases
  • 2.4 Caching Strategies
  • 2.5 Chapter Summary

• Video Timeline (Chapter 2):

  • 0:00 Relaxing Storage-related Assumptions
  • 1:45 Hash Index
  • 2:59 B-Trees & B+ Trees
  • 4:39 LSM Tree
  • 7:08 Data Structures' Trade-off Analysis
  • 8:26 Data Models
  • 12:02 Specialized Databases
  • 13:58 Caching Mechanisms
  • 16:39 Chapter Summary

• Chapter 3 — Data

  • 3.1 Partitioning
  • 3.2 Request Routing
  • 3.3 Scaling and Rebalancing
  • 3.4 Secondary Indexing
  • 3.5 Chapter Summary

• Video Timeline (Chapter 3):

  • 0:00 Relaxing Data-related Assumptions
  • 1:40 Range vs Hash Partitioning
  • 3:20 Consistent Hashing
  • 5:23 Request Routing
  • 7:03 Scaling & Rebalancing Partitions
  • 8:29 Secondary Indexes
  • 10:16 Chapter Summary

• Chapter 4 — Throughput

  • 4.1 CAP and PACELC Theorems
  • 4.2 Single-Leader Replication
  • 4.3 Multi-Leader Replication
  • 4.4 Leaderless Replication
  • 4.5 Scaling Replicas
  • 4.6 Replication Modes
  • 4.7 Data-Centric Consistency Models
  • 4.8 Client-Centric Consistency Models
  • 4.9 Analyzing Replication Schemes and Consistency
  • 4.10 Chapter Summary

• Video Timeline (Chapter 4):

  • 0:00 Relaxing Throughput-related Assumptions
  • 1:59 CAP & PACELC
  • 5:37 Single-leader Replication
  • 6:29 Multi-leader Replication
  • 8:51 CRDTs
  • 10:33 Replication Topologies
  • 11:35 Leaderless Replication
  • 13:17 Adding Replicas
  • 14:19 Replication Models
  • 15:41 Data-centric Consistency Levels
  • 18:42 Client-centric Consistency Levels
  • 20:20 Replication Models x Consistency Levels
  • 24:36 Chapter Summary

• Chapter 5 — Network

  • 5.1 Communication Protocols
  • 5.2 Information Dissemination Mechanisms
  • 5.3 Anti-Entropy Mechanisms
  • 5.4 Implications for Replication
  • 5.5 Chapter Summary

• Video Timeline (Chapter 5):

  • 0:00 Relaxing Network-related Assumptions
  • 2:22 Communication Protocols
  • 5:08 Gossip Protocols
  • 6:24 Read-repair & Merkle-trees
  • 9:07 Geo-distributed DBs & Replication Consistency
  • 11:14 Chapter Summary

• Chapter 6 — Clocks

  • 6.1 Synchronized Clocks
  • 6.2 Event Ordering
  • 6.3 Causal Relationships
  • 6.4 Logical Clocks
  • 6.5 Managing Data Consistency
  • 6.6 Revisiting Replication
  • 6.7 Chapter Summary

• Video Timeline (Chapter 6):

  • 0:00 Relaxing Clocks-related Assumptions
  • 1:57 Tackling Clock Skew
  • 4:09 Event Ordering & Causality
  • 6:36 Lamport Clocks
  • 8:29 Vector Clocks
  • 10:04 Version Vectors
  • 11:47 Replication Consistency under Clock Skew
  • 13:45 Chapter Summary

• Chapter 7 — Failures

  • 7.1 Foundational Definitions
  • 7.2 Failure Detection
  • 7.3 Achieving Atomicity in Distributed Transactions
  • 7.4 Ensuring Isolation in Distributed Transactions
  • 7.5 Failure Handling Mechanisms
  • 7.6 Leader Election in Distributed Systems
  • 7.7 Consensus Algorithms
  • 7.8 Broadcast Protocols
  • 7.9 State Machine Replication
  • 7.10 Theoretical Results
  • 7.11 Recovering from Failures
  • 7.12 Replication and Consistency, Revisited
  • 7.13 Chapter Summary

• Video Timeline (Chapter 7):

  • 0:00 Relaxing Failures-related Assumptions
  • 1:31 Key Definitions
  • 3:25 Failure Detection
  • 5:28 2PC
  • 7:04 3PC
  • 8:28 Distributed Locking
  • 10:28 Handling Node Failures
  • 12:56 Leader Election Algorithms
  • 15:32 Consensus: Paxos & Raft
  • 18:41 Broadcast Ordering & State Machine Replication
  • 22:04 Two Generals Problem & FLP Impossibility
  • 24:07 Distributed Snapshots
  • 25:47 Replication Models x Consistency Levels (revisited)
  • 27:53 Chapter Summary

• Summary

• References

• Video Timeline (Course Summary):

  • 0:00 Course Summary
  • 3:40 References & Recommendations

---