Distributed Operating Systems

A distributed operating system (DOS) manages a group of independent computers and makes them appear to users as a single, coherent system. Unlike network operating systems where each node is aware of the others but operates autonomously, a distributed system fundamentally abstracts the physical locations of resources and processing power.

Architectures and Models

Distributed systems architecture describes how nodes collaborate and share computational responsibilities:

1. Client-Server Model: A centralized server provides resources or services to multiple client nodes. This model is common but inherently creates a single point of failure and bottleneck (e.g., DNS, simple web architectures).
2. Peer-to-Peer (P2P) Model: All nodes (peers) have equal status and capabilities. They share resources directly without relying on a centralized server. This model enhances fault tolerance and scalability but complicates resource discovery and consistency (e.g., BitTorrent, blockchain networks).
3. Tiered Architectures (N-Tier): Systems are divided into logical layers, typically presentation, application logic, and data storage. Each tier can operate on separate hardware, allowing independent scaling and management.

An example of a Remote Procedure Call (RPC) interface definition in Go, showing how client-server communication is structured:

// Example Go RPC service definition representing client-server message exchange
package main

type Args struct {
    Key string
}

type Reply struct {
    Value string
}

type KVStore struct {
    data map[string]string
}

// Get retrieves the value associated with the given key
func (t *KVStore) Get(args *Args, reply *Reply) error {
    reply.Value = t.data[args.Key]
    return nil
}

Key Challenges in Distributed Systems

Designing a distributed OS involves solving complex problems that do not exist in single-node systems.

Time and Clock Synchronization

In a distributed system, each node has its own physical clock. Because network delays are unpredictable and clocks drift at different rates, determining the absolute global order of events is impossible.

Systems use logical clocks (like Lamport timestamps or Vector clocks) to define a partial ordering of events based on causality (“happened-before” relationships) rather than absolute physical time. For closer physical time synchronization, protocols like the Network Time Protocol (NTP) or Precision Time Protocol (PTP) are utilized.

An example of updating a Lamport Logical Clock during message transfer:

// Updating a Lamport Logical Clock upon receiving a message
#define MAX(a, b) ((a) > (b) ? (a) : (b))

unsigned int local_clock = 0;

// Triggered when a local event occurs
void on_local_event() {
    local_clock += 1;
}

// Triggered when sending a message
void on_send_message(unsigned int *msg_timestamp) {
    local_clock += 1;
    *msg_timestamp = local_clock;
}

// Triggered when receiving a message
void on_receive_message(unsigned int msg_timestamp) {
    local_clock = MAX(local_clock, msg_timestamp) + 1;
}

Consistency and Replication

To ensure high availability and fault tolerance, data is often replicated across multiple nodes. This introduces the challenge of data consistency.

• Strong Consistency: Any read operation immediately returns the result of the most recent write operation, regardless of which node is accessed. This often requires complex locking and consensus protocols, severely impacting performance and availability during network partitions.
• Eventual Consistency: Replicas may temporarily hold divergent data, but the system guarantees that, given enough time without new updates, all replicas will eventually converge to the same state. This model prioritizes high availability and low latency (e.g., DNS, social media feeds).

Consensus Protocols

When nodes must agree on a single value or state (e.g., electing a master node, committing a distributed transaction), they use consensus algorithms.

• Paxos: A foundational, mathematically rigorous algorithm for achieving consensus in a network of unreliable processors. It is notoriously complex to implement correctly.
• Raft: Designed as a more understandable alternative to Paxos, Raft achieves the same goals by separating the consensus problem into relatively independent subproblems: leader election, log replication, and safety.

Go structs representing Raft RPC payloads for leader election show the structured data passed to establish consensus:

// Go structs representing Raft consensus RPC payloads for leader election
type RequestVoteArgs struct {
    Term         int // Candidate's current term
    CandidateId  int // Candidate ID requesting the vote
    LastLogIndex int // Index of candidate's last log entry
    LastLogTerm  int // Term of candidate's last log entry
}

type RequestVoteReply struct {
    Term        int  // Current term, for candidate to update itself
    VoteGranted bool // True means candidate received the vote
}

Example: The CAP Theorem

The CAP Theorem (Brewer’s Theorem) states that a distributed data store can provide at most two of the following three guarantees simultaneously:

1. Consistency (C): Every read receives the most recent write or an error.
2. Availability (A): Every request receives a (non-error) response, without the guarantee that it contains the most recent write.
3. Partition Tolerance (P): The system continues to operate despite an arbitrary number of messages being dropped (or delayed) by the network between nodes.

Because network partitions (P) are inevitable in distributed systems, designers must choose between emphasizing Consistency (CP systems, like banking databases) or Availability (AP systems, like shopping carts or caching layers).

Exercise: Understanding the CAP Theorem

References & Further Reading

• Distributed operating system (CC-BY-SA 4.0)
• Client-Server Model (CC-BY-SA 4.0)
• Tanenbaum, A. S., & Van Steen, M. (2007). Distributed Systems: Principles and Paradigms (2nd ed.). Prentice Hall.
• Lamport, L. (1978). Time, clocks, and the ordering of events in a distributed system. Communications of the ACM, 21(7), 558-565.
• Ongaro, D., & Ousterhout, J. (2014). In search of an understandable consensus algorithm. USENIX Annual Technical Conference, 305-320.