Introduction to Distributed Systems
Open in the Padhaiko app1.1 Distributed Systems: Definition, Characteristics, Importance, and Applications
Distributed System
A distributed system is a collection of autonomous computing elements (nodes—either physical hardware or independent software processes) connected by a network that communicate and coordinate their actions solely by passing messages, and that appears to its users as a single coherent system.
- Tanenbaum & van Steen: Emphasize two aspects: (1) independent computing elements, and (2) the single-system image (middleware hides distribution).
- Coulouris et al.: Emphasize hardware or software components located on networked computers that communicate and coordinate only by message passing (no shared physical clock and no shared global memory).
Core Characteristics of Distributed Systems
- Concurrency of Components: Multiple nodes execute programs simultaneously and independently, sharing resources or collaborating on tasks.
- Lack of a Global Clock: Each machine maintains its own local hardware clock, which drifts relative to others. Coordination depends on message ordering rather than a universal physical time.
- Independent Failures: Individual nodes or network links can crash or drop packets while the rest of the system continues running (partial failure), unlike a single-machine crash where everything stops together.
- No Shared Physical Memory: Nodes cannot directly read each other's RAM; all state sharing happens explicitly over network messages.
- Autonomy and Heterogeneity: Nodes may run different hardware architectures, operating systems, and programming languages, yet collaborate through standardized protocols.
Importance and Applications
Why build distributed systems instead of a single giant machine?
- Resource Sharing: Expensive hardware (GPUs, storage arrays), databases, and services can be shared securely across geographically dispersed users.
- Scalability and Performance: Horizontal scaling adds commodity machines to handle growing load (web search, streaming) rather than hitting the physical limits of a single CPU.
- Fault Tolerance and High Availability: Replicating state across independent nodes ensures the service stays online when individual servers or data centers fail.
- Geographic Distribution: Applications such as banking, content delivery, and sensor networks are inherently distributed across physical locations.
| Domain | Real-World Examples | Why Distribution Is Essential |
|---|---|---|
| Web & Cloud Services | Search engines, e-commerce, cloud storage | Millions of concurrent users; low latency via regional replicas |
| Financial & Banking Systems | ATMs, SWIFT, UPI, stock exchanges | Geographically dispersed branches; strict consistency and availability |
| Big Data & Scientific Computing | Apache Spark, CERN LHC grid, weather modeling | Datasets and compute exceed any single machine's memory and CPU |
| Telecom & IoT Networks | 5G core, smart grids, autonomous fleets | Sensors and actuators are physically distributed and real-time |
| Content Delivery & Streaming | CDNs (Cloudflare, Akamai), Netflix, video calls | Caching near users minimizes round-trip latency and backbone load |
1.2 Types of Distributed Systems: High-Performance Computing, Information, and Pervasive Systems
Following Tanenbaum and van Steen's classification, distributed systems fall into three broad categories depending on their primary workload and environment.
1.2.1 Distributed High-Performance Computing (HPC) Systems
Designed to solve compute-intensive and data-intensive problems by harnessing many CPUs/GPUs in parallel:
- Cluster Computing: Homogeneous commodity workstations or servers connected by a high-speed LAN (e.g., InfiniBand or Ethernet), managed by a cluster middleware/scheduler (such as Slurm or Kubernetes) and sharing a common OS stack. Used for parallel simulations, MapReduce, and distributed ML training.
- Grid Computing: Heterogeneous, geographically dispersed organizations pool resources across administrative domains (virtual organizations) using open protocols (e.g., Globus Toolkit). Unlike clusters, nodes have different OSs, hardware, and local ownership policies.
- Cloud Computing (HPC on Demand): Elastic virtualized clusters offered over the internet as utility computing.
1.2.2 Distributed Information Systems
Focus on integrating enterprise applications, databases, and transactions reliably:
- Transaction Processing Systems (TPS): Coordinate multi-step operations across distributed databases using ACID guarantees (Atomicity, Consistency, Isolation, Durability) and Two-Phase Commit (2PC) protocols (via TP monitors).
- Enterprise Application Integration (EAI): Connect independent legacy applications (ERP, CRM, billing) without rewriting them, using RPC/RMI, Message-Oriented Middleware (MOM), and Enterprise Service Buses (ESB) or REST/gRPC APIs.
1.2.3 Distributed Pervasive (Ubiquitous) Systems
Small, embedded, battery-powered, and often mobile devices seamlessly integrated into the physical environment:
- Home and Consumer Networks: Smart TVs, thermostats, voice assistants, and media servers using zero-configuration discovery.
- Electronic Healthcare Systems (Body Area Networks): Wearable ECG/glucose sensors streaming telemetry to local gateways and cloud analytics with strict energy and privacy budgets.
- Sensor Networks and IoT: Hundreds or thousands of resource-constrained wireless nodes (limited CPU, memory, and battery) collaborating on environmental monitoring, smart agriculture, or industrial telemetry.
| Aspect | Cluster Computing | Grid Computing |
|---|---|---|
| Node Hardware & OS | Homogeneous commodity nodes, uniform OS | Heterogeneous hardware and multiple OSs |
| Administrative Control | Single organization, centralized administration | Multiple independent organizations (federated) |
| Network Interconnect | Dedicated high-speed LAN | Wide-area network (WAN) / Internet |
| Coupling & Scheduling | Tightly coordinated single scheduler | Loosely coupled, local site policies respected |
1.3 Properties and Design Goals: Transparency, Heterogeneity, Openness, Reliability, and Scalability
A well-engineered distributed system strives to satisfy five primary design goals.
1.3.1 Transparency
Distribution transparency is the goal of hiding the fact that processes and resources are physically distributed across multiple machines, presenting a single-system illusion.
| Transparency Type | What It Hides from the User / Developer | Practical Example |
|---|---|---|
| Access | Differences in data representation and how a resource is accessed | Big-endian vs. little-endian conversion in RPC; unified file APIs |
| Location | Where a resource physically resides | Opening https://example.com/file without knowing its IP or server rack |
| Migration | That a resource may move to another physical location | Live VM migration or mobile device roaming between cell towers |
| Relocation | That a resource moves while in use without breaking connections | Active TCP/container session migrating seamlessly across hosts |
| Replication | That multiple copies of a resource exist | DNS or database read replicas returning data as if only one copy exists |
| Concurrency | That multiple users share the same resource simultaneously | Distributed locks/transactions giving each user an isolated view |
| Failure | Failure and recovery of a resource | Automatic retry on a backup server without user-visible errors |
| Persistence | Whether a resource is in volatile RAM or on disk | Object databases transparently paging state to disk |
1.3.2 Heterogeneity, Openness, Reliability, and Scalability
- Heterogeneity: Systems must operate seamlessly across diverse networks, hardware (x86, ARM), operating systems (Linux, Windows), programming languages, and vendor implementations. Middleware bridges these differences via standardized data formats (JSON, Protocol Buffers) and protocols (HTTP, TCP/IP).
- Openness: The degree to which a system can be extended and re-implemented via published, standardized interfaces (IDLs and protocols). Key properties include interoperability (components from different vendors work together), portability (application runs unmodified across platforms), and extensibility (new modules plug in cleanly).
- Reliability (Dependability): Encompasses availability (readiness for correct service), reliability (continuity of correct service over time), safety (avoiding catastrophic failure), and maintainability (ease of repair).
- Scalability: Ability to handle growth gracefully along three dimensions:
- Size Scalability: Adding more users and resources without noticeable performance loss or administrative bottlenecks.
- Geographical Scalability: Maintaining responsiveness when nodes span continents (where speed-of-light WAN latency cannot be eliminated, making synchronous RPC expensive).
- Administrative Scalability: Staying manageable when spanning multiple independent organizations with conflicting security and billing policies.
Techniques for Achieving Scalability
- Hiding Communication Latency: Use asynchronous communication (non-blocking calls, event loops) and push validation/UI work to the client.
- Distribution (Partitioning / Sharding): Split data and workload across nodes (e.g., DNS hierarchy, database sharding by user ID hash).
- Replication and Caching: Place copies close to clients to reduce latency and balance read traffic (requiring a strategy to handle stale copies).
1.4 Architectural Models: Client-Server, Peer-to-Peer, Multi-Tier, and Event-Based
Architectural models define how responsibilities are assigned to software components and how those components are placed onto physical machines.
1.4.1 Client-Server and Multi-Tier Architectures
- Client-Server Model: Asymmetric roles—servers manage resources and wait passively for requests; clients actively send requests and wait for replies (request-reply pattern). Simple to manage and secure, but a single server creates a scalability bottleneck and single point of failure.
- Multi-Tier (Layered) Architecture: Separates concerns across logical layers and physical tiers:
- 2-Tier: Client handles UI + application logic; Server handles database.
- 3-Tier:
- Presentation Tier (User Interface): Browser or mobile app.
- Application / Logic Tier: Stateless web/API servers enforcing business rules.
- Data Tier: Database clusters and distributed storage.
- Advantage: Each tier scales independently and isolates security boundaries.
1.4.2 Peer-to-Peer (P2P) Architecture
All nodes (peers) have symmetric capabilities, acting simultaneously as both client and server.
- Unstructured P2P: Peers form an arbitrary overlay graph; lookups use flooding or random walks (simple, resilient to churn, high search overhead; e.g., early Gnutella).
- Structured P2P (DHT): Overlay topology follows a deterministic mathematical structure such as a Distributed Hash Table (Chord ring, Kademlia XOR metric), guaranteeing lookups in hops.
1.4.3 Event-Based (Publish-Subscribe) Architecture
Components are decoupled in space (do not know each other's identities or locations) and time (do not need to be online simultaneously):
- Producers (Publishers) emit structured events to an Event Bus / Broker.
- Consumers (Subscribers) register interest in topics or content filters and receive notifications asynchronously when matching events occur.
| Model | Coupling | Scalability Bottleneck | Fault Tolerance | Best Suited For |
|---|---|---|---|---|
| Client-Server | Tight (client knows server) | Server CPU / bandwidth | Needs server replication | Web apps, file/DB access |
| Multi-Tier | Modular across tiers | Data tier contention | Independent tier failover | Enterprise web & cloud apps |
| Peer-to-Peer (P2P) | Symmetric, decentralized | Overlay maintenance / churn | Very high (no central server) | File sharing, blockchain, IPFS |
| Event-Based | Loose (space & time decoupled) | Broker throughput / fan-out | High with persistent brokers | IoT telemetry, microservices, real-time feeds |
1.5 Fundamental Models: Interaction, Failure, and Security Models
Fundamental models capture the essential assumptions and threats common to all distributed architectures so engineers can reason formally about correctness.
1.5.1 Interaction Model
Describes how processes interact via message passing, characterized by latency, bandwidth, jitter, and clock drift. Two timing models exist:
| Aspect | Synchronous Distributed System | Asynchronous Distributed System |
|---|---|---|
| Execution Speed | Known upper and lower bounds on step execution time | Arbitrary execution delays; no upper bound |
| Message Transmission Delay | Bounded by a known constant | Unbounded (finite, but arbitrarily long) |
| Local Clock Drift Rate | Bounded within a known drift | No guarantees on clock drift rates |
| Practical Reality | Hard to guarantee over the Internet (only approximated in LAN/RT systems) | Accurately models the public Internet and cloud WANs |
1.5.2 Failure Model
Defines how components and communication links can misbehave:
- Omission Failures: A process crashes (fail-stop if detectable, crash if silent) or a channel drops messages (send-omission or receive-omission).
- Arbitrary (Byzantine) Failures: The worst possible failure—a node or channel deviates arbitrarily from its specification (sends corrupted, contradictory, or malicious messages).
- Timing Failures: Applicable only to synchronous systems; a response arrives outside its specified deadline (too early or too late).
1.5.3 Security Model
Protects processes, channels, and objects against active and passive adversaries:
- Enemy / Adversary: Capable of eavesdropping, replaying, tampering with, or forging messages on an untrusted network.
- Cryptography & Authentication: Encrypt messages (confidentiality), attach MACs/digital signatures (integrity & authentication), and include nonces/timestamps (freshness against replay attacks).
- Access Control: Verify principal identity and enforce authorization (ACLs or capability tokens) on objects, while guarding against Denial-of-Service (DoS).
1.6 Design Challenges, Fallacies of Distributed Computing, and Real-World Systems
Core Design Challenges
- Heterogeneity & Interoperability: Unifying diverse OSs, byte orders, and protocols.
- Partial Failures & Network Partitions: Handling nodes that vanish mid-transaction or links that split a cluster into two isolated halves (split-brain).
- Concurrency & Consistency: Coordinating parallel updates without deadlocks or stale reads (CAP trade-offs).
- Security & Trust Boundaries: Defending open network endpoints against spoofing, tampering, and DoS.
- Observability & Debugging: Tracing requests across dozens of asynchronous microservices without a single global clock.
The Eight Fallacies of Distributed Computing
Formulated by L. Peter Deutsch and colleagues at Sun Microsystems, these are false assumptions engineers commonly make when transitioning from single-machine programming to distributed systems:
| # | Fallacy | Reality in Production Systems |
|---|---|---|
| 1 | The network is reliable | Links fail, switches reboot, packets drop—use retries, timeouts, and idempotency |
| 2 | Latency is zero | WAN round-trips take ; batch calls and avoid chatty RPCs |
| 3 | Bandwidth is infinite | Serialization bloat and large payloads saturate links; compress and paginate |
| 4 | The network is secure | Assume hostile networks; enforce TLS, mTLS, authentication, and least privilege |
| 5 | Topology doesn't change | Routes flap, containers reschedule, IPs churn; use service discovery, not hardcoded IPs |
| 6 | There is one administrator | Cross-team and multi-cloud deployments require backward-compatible versioning |
| 7 | Transport cost is zero | Serialization, TLS handshakes, and cloud egress fees consume CPU and budget |
| 8 | The network is homogeneous | Heterogeneous clients, endianness, and versions demand standard open protocols |
Overview of Real-World Distributed Systems
- Google Search & Infrastructure: Built on distributed file systems (GFS/Colossus), distributed coordination (Chubby), and globally distributed SQL (Spanner).
- Domain Name System (DNS): A globally distributed, hierarchically partitioned, heavily cached naming directory serving billions of queries per day.
- Content Delivery Networks (CDNs) & Netflix: Geo-replicated edge caches and hundreds of fault-isolated microservices streaming petabytes globally.
- Bitcoin / Ethereum: Decentralized P2P networks tolerating Byzantine faults without a central authority.
Worked Out Examples
1.1
A distributed analytics job has of its execution time parallelizable across worker nodes, while the remaining is strictly sequential coordination on a single master node (ignoring network overhead). Using Amdahl's Law:
- Calculate the theoretical speedup and parallel efficiency when running on worker nodes.
- What is the maximum theoretical speedup as , and what distributed design lesson does this illustrate?
Applying Amdahl's Law (, , ):
Calculating Parallel Efficiency for :
Asymptotic Limit as :
Even with infinite servers, speedup cannot exceed . This illustrates why size scalability requires eliminating centralized sequential bottlenecks (such as single-master locks or synchronous coordination).
- Speedup , efficiency .
- Maximum speedup ; centralized sequential coordination caps horizontal scaling regardless of cluster size.
1.2
A software update file of size must be distributed from one origin server (upload bandwidth ) to identical client nodes. Each client has download bandwidth and upload bandwidth . Ignoring propagation and protocol overhead, calculate the minimum distribution time under:
- Client-Server Architecture
- Peer-to-Peer (P2P) Architecture
Client-Server Minimum Distribution Time: The server must upload a separate copy to each of the clients (), and each client needs at least to download its copy:
Peer-to-Peer (P2P) Minimum Distribution Time: In P2P, the server only needs to upload at least one full copy (), every peer must download at its bottleneck , and the aggregate upload capacity of the server plus all peers must transmit bits:
Taking the maximum of the three bounds gives (around faster than Client-Server).
- Client-Server: (severely bottlenecked by server upload capacity).
- Peer-to-Peer: (because peers contribute their upload bandwidth to redistribute chunks).
1.3
Exam-Style Design Analysis: A university deploys a nationwide online examination portal serving concurrent students across multiple campuses.
- Choose an appropriate architectural model and justify your choice.
- Identify one interaction, one failure, and one security consideration using the fundamental models.
- Explain which two distribution transparencies are most critical here and why full failure transparency can be dangerous.
1. Architectural Model Selection: A 3-Tier Client-Server Architecture (Presentation tier via browser/CDN stateless Application tier behind load balancers replicated Data tier) combined with an Event-Based queue for asynchronous answer-sheet submission and grading.
- Justification: Central authentication and exam integrity require client-server control (unlike P2P), while separating stateless web servers from the database allows horizontal scaling during exam start spikes.
2. Fundamental Models Analysis:
- Interaction Model: The system runs over the public Internet, which is asynchronous (unbounded latency and jitter); clients cannot rely on tight physical clock bounds, so exam timers must be enforced authoritatively by the server.
- Failure Model: Expect crash and omission failures (dropped Wi-Fi packets or a crashed app instance). Use idempotent submission tokens so retries never duplicate or corrupt answers.
- Security Model: Protect against eavesdropping and tampering by active adversaries using TLS (confidentiality/integrity), JWT/OAuth tokens (authentication), and rate limiting (DoS mitigation).
3. Transparencies and Limits:
- Location and Replication transparency are essential so students hit the nearest healthy regional replica via DNS/load balancing without changing URLs.
- Caution on Failure Transparency: Hiding a lost network connection indefinitely makes a student's browser appear frozen while the exam clock runs out; instead, the UI should surface an explicit "reconnecting / saved locally" status.
Use a 3-tier client-server + event-based architecture; model the Internet as asynchronous with crash/omission failures and TLS + token authentication; prioritize location and replication transparency while avoiding silent infinite retries for failure transparency.
Exercises
Practice Exercises — Introduction to Distributed Systems
Define a distributed system and state its four defining characteristics. Distinguish clearly between Cluster Computing, Grid Computing, and Pervasive Systems with one real-world example of each.
Definition and Characteristics: A distributed system is a collection of autonomous computing elements connected by a network that communicate solely via message passing and appear to users as a single coherent system. Its four core characteristics are: (1) concurrency of components, (2) lack of a global physical clock, (3) independent (partial) failures, and (4) no shared physical memory.
Comparison of Distributed System Types:
- Cluster Computing: Homogeneous commodity nodes on a high-speed LAN under single administration (e.g., an Apache Spark analytics cluster).
- Grid Computing: Heterogeneous resources federated across multiple administrative domains over a WAN (e.g., the CERN Worldwide LHC Computing Grid).
- Pervasive Systems: Resource-constrained, embedded, often wireless devices integrated into everyday environments (e.g., a wearable health-monitoring body area network).
A distributed system coordinates autonomous networked nodes via message passing to present a single-system image, characterized by concurrency, no global clock, independent failures, and no shared memory. Clusters are homogeneous/single-domain, Grids are heterogeneous/multi-organization, and Pervasive systems embed mobile/IoT nodes into physical spaces.
A distributed image-processing pipeline spends of its time in parallelizable worker tasks and in a non-parallelizable coordination phase.
- Compute the theoretical speedup and efficiency on nodes.
- Find the upper bound on speedup as .
Computing and via Amdahl's Law (, ):
Maximum Theoretical Speedup ():
- and .
- Maximum speedup .
A dataset is distributed from a single server () to peers, each having download bandwidth and upload bandwidth. Compute the minimum distribution time for (a) Client-Server and (b) Peer-to-Peer (P2P) distribution.
(a) Client-Server Time:
(b) Peer-to-Peer (P2P) Time:
(a) Client-Server: . (b) P2P: .
Explain distribution transparency and distinguish between Location, Migration, Relocation, and Replication transparency. Briefly describe the three dimensions of scalability and three techniques used to achieve it.
Four Transparency Types:
- Location: Hides where a resource physically resides (e.g., URLs independent of host IP).
- Migration: Hides that a resource may move from one location to another between uses.
- Relocation: Hides that a resource moves while actively in use without interrupting the client.
- Replication: Hides that multiple redundant copies of a resource exist.
Dimensions and Techniques of Scalability:
- Dimensions: (1) Size (more users/resources), (2) Geographical (wide-area latency), and (3) Administrative (multiple independent organizations).
- Techniques: (1) Hiding communication latency (asynchronous calls), (2) Distribution/Partitioning (sharding data across servers), and (3) Replication and caching (placing copies near clients).
Transparency conceals physical distribution (location, movement before use, movement during use, and multiple copies). Scalability spans size, geography, and administration, achieved via asynchrony, partitioning, and replication/caching.
Compare synchronous and asynchronous interaction models, list the three failure classes in the failure model, and explain any four fallacies of distributed computing with their engineering consequences.
Interaction and Failure Models:
- Synchronous vs. Asynchronous: Synchronous systems have known upper bounds on execution time, message delay, and clock drift; asynchronous systems have no upper bounds (modeling real WANs).
- Failure Classes: (1) Omission (process crash or dropped messages), (2) Timing (deadline violation in synchronous systems), and (3) Arbitrary/Byzantine (corrupted, contradictory, or malicious behavior).
Four Fallacies and Consequences:
- Network is reliable: Requires retries, timeouts, and idempotent operations.
- Latency is zero: Requires batching requests and caching rather than chatty RPCs.
- Topology doesn't change: Requires dynamic service discovery instead of hardcoded IPs.
- Network is secure: Requires TLS encryption, strong authentication, and authorization on every service boundary.
Synchronous models enforce strict timing bounds while asynchronous models assume unbounded delays; failures are omission, timing, or Byzantine. Respecting fallacies like unreliable networks, non-zero latency, changing topology, and insecure links drives timeouts, batching, service discovery, and TLS.