PadhaikoAll subjects

Introduction to Distributed Systems

Distributed and Cloud Computing (ENCT 411)

Open in the Padhaiko app

1.1 Distributed Systems: Definition, Characteristics, Importance, and Applications

Definition

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.

Core Characteristics of Distributed Systems

  1. Concurrency of Components: Multiple nodes execute programs simultaneously and independently, sharing resources or collaborating on tasks.
  2. 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.
  3. 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.
  4. No Shared Physical Memory: Nodes cannot directly read each other's RAM; all state sharing happens explicitly over network messages.
  5. 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?

Major Application Domains of Distributed Systems
DomainReal-World ExamplesWhy Distribution Is Essential
Web & Cloud ServicesSearch engines, e-commerce, cloud storageMillions of concurrent users; low latency via regional replicas
Financial & Banking SystemsATMs, SWIFT, UPI, stock exchangesGeographically dispersed branches; strict consistency and availability
Big Data & Scientific ComputingApache Spark, CERN LHC grid, weather modelingDatasets and compute exceed any single machine's memory and CPU
Telecom & IoT Networks5G core, smart grids, autonomous fleetsSensors and actuators are physically distributed and real-time
Content Delivery & StreamingCDNs (Cloudflare, Akamai), Netflix, video callsCaching 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:

1.2.2 Distributed Information Systems

Focus on integrating enterprise applications, databases, and transactions reliably:

1.2.3 Distributed Pervasive (Ubiquitous) Systems

Small, embedded, battery-powered, and often mobile devices seamlessly integrated into the physical environment:

AspectCluster ComputingGrid Computing
Node Hardware & OSHomogeneous commodity nodes, uniform OSHeterogeneous hardware and multiple OSs
Administrative ControlSingle organization, centralized administrationMultiple independent organizations (federated)
Network InterconnectDedicated high-speed LANWide-area network (WAN) / Internet
Coupling & SchedulingTightly coordinated single schedulerLoosely 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.

Eight Forms of Distribution Transparency (ISO ODP)
Transparency TypeWhat It Hides from the User / DeveloperPractical Example
AccessDifferences in data representation and how a resource is accessedBig-endian vs. little-endian conversion in RPC; unified file APIs
LocationWhere a resource physically residesOpening https://example.com/file without knowing its IP or server rack
MigrationThat a resource may move to another physical locationLive VM migration or mobile device roaming between cell towers
RelocationThat a resource moves while in use without breaking connectionsActive TCP/container session migrating seamlessly across hosts
ReplicationThat multiple copies of a resource existDNS or database read replicas returning data as if only one copy exists
ConcurrencyThat multiple users share the same resource simultaneouslyDistributed locks/transactions giving each user an isolated view
FailureFailure and recovery of a resourceAutomatic retry on a backup server without user-visible errors
PersistenceWhether a resource is in volatile RAM or on diskObject databases transparently paging state to disk

1.3.2 Heterogeneity, Openness, Reliability, and Scalability

Techniques for Achieving Scalability

  1. Hiding Communication Latency: Use asynchronous communication (non-blocking calls, event loops) and push validation/UI work to the client.
  2. Distribution (Partitioning / Sharding): Split data and workload across nodes (e.g., DNS hierarchy, database sharding by user ID hash).
  3. 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

1.4.2 Peer-to-Peer (P2P) Architecture

All nodes (peers) have symmetric capabilities, acting simultaneously as both client and server.

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):

Comparison of Distributed Architectural Models
ModelCouplingScalability BottleneckFault ToleranceBest Suited For
Client-ServerTight (client knows server)Server CPU / bandwidthNeeds server replicationWeb apps, file/DB access
Multi-TierModular across tiersData tier contentionIndependent tier failoverEnterprise web & cloud apps
Peer-to-Peer (P2P)Symmetric, decentralizedOverlay maintenance / churnVery high (no central server)File sharing, blockchain, IPFS
Event-BasedLoose (space & time decoupled)Broker throughput / fan-outHigh with persistent brokersIoT 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:

AspectSynchronous Distributed SystemAsynchronous Distributed System
Execution SpeedKnown upper and lower bounds on step execution timeArbitrary execution delays; no upper bound
Message Transmission DelayBounded by a known constant Unbounded (finite, but arbitrarily long)
Local Clock Drift RateBounded within a known drift No guarantees on clock drift rates
Practical RealityHard 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:

  1. Omission Failures: A process crashes (fail-stop if detectable, crash if silent) or a channel drops messages (send-omission or receive-omission).
  2. Arbitrary (Byzantine) Failures: The worst possible failure—a node or channel deviates arbitrarily from its specification (sends corrupted, contradictory, or malicious messages).
  3. 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:


1.6 Design Challenges, Fallacies of Distributed Computing, and Real-World Systems

Core Design Challenges

  1. Heterogeneity & Interoperability: Unifying diverse OSs, byte orders, and protocols.
  2. Partial Failures & Network Partitions: Handling nodes that vanish mid-transaction or links that split a cluster into two isolated halves (split-brain).
  3. Concurrency & Consistency: Coordinating parallel updates without deadlocks or stale reads (CAP trade-offs).
  4. Security & Trust Boundaries: Defending open network endpoints against spoofing, tampering, and DoS.
  5. 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:

The Eight Fallacies of Distributed Computing
#FallacyReality in Production Systems
1The network is reliableLinks fail, switches reboot, packets drop—use retries, timeouts, and idempotency
2Latency is zeroWAN round-trips take ; batch calls and avoid chatty RPCs
3Bandwidth is infiniteSerialization bloat and large payloads saturate links; compress and paginate
4The network is secureAssume hostile networks; enforce TLS, mTLS, authentication, and least privilege
5Topology doesn't changeRoutes flap, containers reschedule, IPs churn; use service discovery, not hardcoded IPs
6There is one administratorCross-team and multi-cloud deployments require backward-compatible versioning
7Transport cost is zeroSerialization, TLS handshakes, and cloud egress fees consume CPU and budget
8The network is homogeneousHeterogeneous clients, endianness, and versions demand standard open protocols

Overview of Real-World Distributed Systems


Worked Out Examples

Example 1.1

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:

  1. Calculate the theoretical speedup and parallel efficiency when running on worker nodes.
  2. 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).

Answer:
  1. Speedup , efficiency .
  2. Maximum speedup ; centralized sequential coordination caps horizontal scaling regardless of cluster size.
Example 1.2

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:

  1. Client-Server Architecture
  2. 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).

Answer:
  1. Client-Server: (severely bottlenecked by server upload capacity).
  2. Peer-to-Peer: (because peers contribute their upload bandwidth to redistribute chunks).
Example 1.3

1.3

Exam-Style Design Analysis: A university deploys a nationwide online examination portal serving concurrent students across multiple campuses.

  1. Choose an appropriate architectural model and justify your choice.
  2. Identify one interaction, one failure, and one security consideration using the fundamental models.
  3. 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.
Answer:

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

Question 1

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).
Answer:

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.

Question 2

A distributed image-processing pipeline spends of its time in parallelizable worker tasks and in a non-parallelizable coordination phase.

  1. Compute the theoretical speedup and efficiency on nodes.
  2. Find the upper bound on speedup as .

Computing and via Amdahl's Law (, ):

Maximum Theoretical Speedup ():

Answer:
  1. and .
  2. Maximum speedup .
Question 3

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:

Answer:

(a) Client-Server: . (b) P2P: .

Question 4

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).
Answer:

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.

Question 5

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:

  1. Network is reliable: Requires retries, timeouts, and idempotent operations.
  2. Latency is zero: Requires batching requests and caching rather than chatty RPCs.
  3. Topology doesn't change: Requires dynamic service discovery instead of hardcoded IPs.
  4. Network is secure: Requires TLS encryption, strong authentication, and authorization on every service boundary.
Answer:

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.

Communication in Distributed Systems →