Distributed Systems

What Makes a System Distributed

A distributed system is a collection of independent computers that appear as a single system to users.

Characteristics

Distributed System Properties:

1. Multiple Components:
   - Running on different machines
   - Connected via network

2. Single View:
   - Appears as one system
   - Transparent to users

3. Autonomous:
   - Components run independently
   - Concurrent execution

4. No Shared Memory:
   - Communication via messages
   - No global clock

Examples

System	Distribution
Web Application	Multiple servers behind load balancer
Database Cluster	Multiple nodes replicating data
Microservices	Independent services communicating
CDN	Edge servers worldwide
Blockchains	Distributed ledger across nodes

Components

Distributed System Components:

┌─────────┐     ┌─────────┐     ┌─────────┐
│ Node A  │────→│ Node B  │────→│ Node C  │
└─────────┘     └─────────┘     └─────────┘
     ↑               ↑               ↑
     └───────────────┴───────────────┘
            Network (unreliable)

Building Blocks

• Nodes: Individual computers
• Network: Communication medium
• Processes: Running programs
• Data: Distributed storage
• Time: Logical/physical clocks

Distributed Systems Challenges

Core Challenges

1. Network Unreliability:
   - Messages can be lost
   - Messages can be delayed
   - Messages can be duplicated
   - Network can partition

2. Partial Failure:
   - Some nodes fail, others work
   - Hard to detect failures
   - Recovery is complex

3. Concurrency:
   - Multiple operations simultaneously
   - Race conditions
   - Ordering issues

4. No Global Clock:
   - Hard to coordinate time
   - Event ordering is complex
   - Clock skew exists

Failure Modes

Failure Type	Description	Difficulty
Crash-fail	Node stops responding	Easy
Byzantine	Node behaves arbitrarily	Hard
Network Partition	Network splits into islands	Very Hard
Clock Skew	Nodes disagree on time	Medium

The Eight Fallacies

1. The network is reliable
2. Latency is zero
3. Bandwidth is infinite
4. The network is secure
5. Topology doesn't change
6. There is one administrator
7. Transport cost is zero
8. The network is homogeneous

Challenges in Practice

# Example: Distributed counter
class DistributedCounter:
    def __init__(self):
        self.counters = {}  # node_id -> count
    
    def increment(self):
        # Challenge: Which node incremented?
        # Challenge: Network delay
        # Challenge: Node failure during increment
        pass
    
    def get_count(self):
        # Challenge: Inconsistent view
        # Challenge: Stale data
        pass

CAP Theorem Review

The Three Properties

CAP Theorem (Brewer's Theorem):

Consistency (C):
- All nodes see same data at same time
- Strong consistency

Availability (A):
- Every request gets a response
- No timeouts/errors

Partition Tolerance (P):
- System works despite network partitions
- Network splits are handled

Pick TWO out of THREE!

CAP Combinations

CA (No Partition Tolerance):
- Single node or synchronous replication
- Strong consistency + availability
- Example: Traditional RDBMS

CP (No Availability):
- Consistent but may reject requests
- Example: ZooKeeper, etcd

AP (No Consistency):
- Available but eventual consistency
- Example: DynamoDB, Cassandra

Visual

         Consistency
            /\
           /  \
          / CA \
         /      \
        /________\
       /    CP    \
      /            \
     /      AP      \
    /                \
   Availability --- Partition
                    Tolerance

PACELC Theorem

PACELC Extension of CAP:

If Partition (P):
  Choose Availability (A) or Consistency (C)
Else (E - normal operation):
  Choose Latency (L) or Consistency (C)

DynamoDB: PA/EL (prefer availability, low latency)
ZooKeeper: PC/EC (prefer consistency, consistency)

Practical Implications

System	CAP Choice	Trade-off
Single DB	CA	No partition tolerance
HBase	CP	May reject writes
Cassandra	AP	Eventual consistency
DynamoDB	AP	Configurable consistency

Consistency Models

Strong Consistency:
- Read returns most recent write
- Linearizable
- Example: Traditional RDBMS

Eventual Consistency:
- Read returns some recent write
- Eventually consistent
- Example: DNS, Cassandra

Causal Consistency:
- Causally related ops in order
- Concurrent ops may be unordered
- Example: MongoDB |