Introduction to Distributed Systems

What is a Distributed System?

A distributed system is a collection of independent computers that appears to its users as a single coherent system. These machines work together by passing messages over a network to achieve a common goal.

                    Leslie Lamport's Definition:

                    "A distributed system is one in which the failure of a computer you didn't even know existed can
                    render your own computer unusable."
                

This definition is humorous but captures a fundamental truth: distributed systems are hard because of failures. When you build a system across multiple machines, you inherit all the complexities of:

Networks: Message delays, packet loss, network partitions
Operating Systems: Process crashes, resource contention, timing issues
Coordination: Keeping machines in sync without a global clock
Scale: What works on 3 machines might fail on 3000

Why Build Distributed Systems?

If distributed systems are so hard, why not just use one big machine? Because some problems require distribution:

Scalability

One machine has limits. To handle billions of requests (Google, Facebook), you need thousands of machines working together.

Fault Tolerance

Hardware fails. Disks crash. Data centers lose power. Replication across machines ensures the system survives failures.

Geographic Distribution

Users are worldwide. Placing servers close to users (CDNs, edge computing) reduces latency dramatically.

Inherent Distribution

Some data is naturally distributed. Banking systems span branches. IoT sensors are geographically scattered.

The Network Foundation

Distributed systems are built on top of computer networks. Every distributed systems challenge stems from the unreliable nature of network communication.

Network Realities

In an OS, when you call a function, you get an immediate response. In a distributed system, when you send a message:

Network Uncertainties:

Latency: Messages take time to travel (milliseconds to seconds)
Packet Loss: Messages can disappear (routers drop packets)
Reordering: Messages might arrive out of order
Partitions: Network can split, isolating groups of nodes
Byzantine Failures: Nodes might send corrupted or malicious messages

Communication Models

Distributed systems use different communication patterns, each with tradeoffs:

Model	Description	Examples
RPC (Remote Procedure Call)	Call a function on another machine as if it's local	gRPC, Apache Thrift
Message Passing	Send messages asynchronously through queues	RabbitMQ, Kafka
Shared Memory	Simulate shared memory across network	Redis, Memcached
Streaming	Continuous data flow between nodes	Apache Flink, Spark Streaming

The Two Generals Problem

A Classic Network Problem:

Two armies on opposite hills need to attack a city simultaneously. They can only communicate via messengers who might get captured. How do they coordinate?

Answer: They can't! This is provably impossible with unreliable communication. It illustrates why consensus is hard in distributed systems.

Operating Systems Concepts at Scale

If you understand operating systems, you already have intuition for distributed systems. The concepts are similar, but scaled across multiple machines:

OS Concept	Distributed Systems Equivalent
Process	Node/Service - An independent machine running code
Thread	Concurrent Request - Multiple operations happening simultaneously
Mutex/Lock	Distributed Lock - Coordinating access across machines (e.g., Redis locks)
Deadlock	Distributed Deadlock - Nodes waiting on each other in a cycle
Shared Memory	Distributed Cache - Shared data store accessible by all nodes
IPC (Pipes, Sockets)	Network Protocols - TCP, UDP, HTTP, RPC
File System	Distributed File System - HDFS, GFS, Ceph
Scheduling	Load Balancing - Distributing work across nodes

Concurrency Challenges

Remember race conditions from OS? In distributed systems, they're worse:

                    
# OS: Two threads updating a counter

Thread 1: reads count = 10

Thread 2: reads count = 10

Thread 1: writes count = 11

Thread 2: writes count = 11  # Lost update!

# Distributed: Two nodes updating a database

Node A: reads balance = $100

Node B: reads balance = $100

Network delay...

Node A: writes balance = $90  (withdraw $10)

Node B: writes balance = $80  (withdraw $20)

# Result: $80 instead of $70! Money created from nothing!

In an OS, you solve this with locks. In distributed systems, you need:

Distributed Transactions: Two-Phase Commit (2PC), Paxos
Optimistic Concurrency: Version numbers, Compare-and-Swap (CAS)
Consensus Algorithms: Raft, Multi-Paxos

The Fundamental Challenges

1. Time and Ordering

In a single machine, you have a system clock. In distributed systems, there is no global clock. Each machine has its own clock, and they drift apart.

The Problem:
If Node A timestamps an event at 10:00:00.001 and Node B timestamps an event at 10:00:00.000, which happened first? You can't know without additional information!

Solutions:

Logical Clocks: Lamport timestamps - events get sequence numbers
Vector Clocks: Track causality - "A happened before B"
Physical Clocks: NTP, GPS, atomic clocks (but never perfect)

2. Consensus

How do independent nodes agree on a value when some might crash or send wrong messages?

                    The Consensus Problem:

                    All non-faulty nodes must agree on the same value. Sounds simple, but this is one of the hardest
                    problems in computer science!
                

Key Algorithms:

Paxos: Provably correct but complex (Leslie Lamport, 1989)
Raft: Easier to understand alternative (2013)
Byzantine Fault Tolerance: Works even with malicious nodes (blockchain)

3. Consistency Models

When data is replicated across nodes, what guarantees do you provide?

Model	Guarantee	Example
Strong Consistency	All nodes see the same data at the same time	Traditional databases
Eventual Consistency	All nodes will eventually see the same data	DynamoDB, Cassandra
Causal Consistency	Causally related operations are seen in order	Social media feeds
Read-Your-Writes	You always see your own updates	User profiles

4. The CAP Theorem

One of the most famous results in distributed systems:

CAP Theorem (Eric Brewer, 2000):

In the presence of a network Partition, you must choose between:

Consistency: All nodes see the same data
Availability: Every request gets a response

You cannot have both! Pick two.

Real-World Examples:

CP (Consistency + Partition Tolerance): MongoDB, HBase - Might refuse reads during partition
AP (Availability + Partition Tolerance): DynamoDB, Cassandra - Always available, might show stale data
CA (Consistency + Availability): Traditional RDBMS - Only works without partitions (single datacenter)

Replication: The Double-Edged Sword

Replication means storing the same data on multiple nodes. It's essential for:

Fault tolerance (if one node dies, data survives)
Performance (serve reads from nearby replicas)
Load distribution (spread requests across replicas)

Replication Strategies

Primary-Backup

One node is the leader. All writes go to leader, then replicate to followers. Simple but leader is a bottleneck.

Multi-Master

Multiple nodes accept writes. More available but requires conflict resolution (what if two masters update the same data?).

Quorum-Based

Write to W nodes, read from R nodes. If W + R > N (total nodes), you're guaranteed to see latest write.

State Machine Replication

All replicas execute the same operations in the same order. Requires consensus. Used in Raft, Paxos.

Partitioning (Sharding)

When data is too big for one machine, split it across multiple machines. Each machine stores a partition (shard) of the data.

Partitioning Strategies

Range-Based: Node 1 gets keys A-M, Node 2 gets N-Z. Simple but can have hot spots.
Hash-Based: Hash the key, assign to node. Balanced but range queries are hard.
Consistent Hashing: Minimizes data movement when nodes are added/removed (DynamoDB, Cassandra)

The Challenge: Queries that span partitions are expensive. Good partitioning requires understanding your access patterns!

Real-World Distributed Systems

Now that you understand the theory, here are systems you use every day:

Google File System (GFS)

Problem: Store petabytes of data
Solution: Split files into 64MB chunks, replicate 3x, use primary-backup replication

Amazon DynamoDB

Problem: High availability at massive scale
Solution: Consistent hashing, eventual consistency, quorum reads/writes

Apache Kafka

Problem: Stream billions of events/day
Solution: Log-structured storage, partitioning, leader-follower replication

Kubernetes

Problem: Orchestrate thousands of containers
Solution: Etcd (Raft consensus), declarative state, reconciliation loops

Summary

Distributed systems combine everything you know about networks and operating systems, then add new layers of complexity:

From networks: unreliable communication, latency, partitions
From OS: concurrency, resource management, scheduling
New challenges: consensus, time ordering, replication, partitioning

                    The Big Lesson:

                    There is no perfect distributed system. Every design is a tradeoff between consistency,
                    availability, performance, and complexity. Understanding these tradeoffs is what makes you a great
                    distributed systems engineer.
                

Coming Next: Research Papers

Now that you have the foundations, we'll dive deep into 5 seminal papers that shaped modern distributed systems:

The Google File System (GFS)
MapReduce: Simplified Data Processing
The Chubby Lock Service
Dynamo: Amazon's Highly Available Key-Value Store
Raft Consensus Algorithm