DISTRIBUTED COMPUTING

Exam-Ready Answers (Modules 4, 5, 6)

Question and Answer Format Only

MODULE 4 - RESOURCE AND PROCESS

MANAGEMENT

Q1. Explain desirable features of global scheduling algorithm.

Answer:

A global scheduling algorithm must ensure:

1. Load Balancing to distribute work evenly across nodes

2. Scalability to handle growth in nodes and tasks

3. Fault Tolerance for automatic recovery from failures

4. Low Communication Overhead to prevent network congestion

5. Transparency to hide the distributed nature from users

6. Adaptability to respond to dynamic system conditions

Example: Google's scheduler balances millions of tasks across data centers efficiently while maintaining
transparency for users.

Diagram:

Global Scheduling Requirements:

Load Balance ──┐

Scalability ──┼─→ Efficient Scheduling
Fault Tolerant──┤
Low Overhead ──┤
Transparent ──┤
Adaptive ──┘
Q2. Explain different load estimation and process transfer policies used by load
balancing algorithms. [V IMP]
Answer:

Load balancing uses two types of policies:

A) Load Estimation Policies:

1. Queue Length - Counts waiting processes in CPU queue

2. CPU Utilization - Measures percentage of CPU busy time

3. Resource-based - Checks memory, I/O, and network usage

4. Hybrid - Combines all metrics for accurate measurement

B) Process Transfer Policies:

1. Threshold Policy - Uses high/low limits (Load > 10 → send, Load < 3 → receive)

2. Selection Policy - Chooses which overloaded node sends tasks and which process to migrate

3. Information Policy - Decides when to collect load data (periodic/on-demand/state-change)

4. Transfer Policy - Ensures benefit exceeds cost before migrating

Example: Modern cloud systems use hybrid estimation with threshold-based transfer to balance loads
automatically.

Diagram:

LOAD BALANCING
|
┌─────────┴─────────┐
| |
ESTIMATION TRANSFER
| |
┌───┼───┬───┬───┐ ┌────┼────┬────┬────┐
| | | | | | | | |
Queue CPU Res Hybrid Thresh Select Info Trans
Policy Policy

Q3. Explain code migration & its techniques OR Describe code migration issues in
details.
Answer:

Code migration moves programs between machines for load balancing or resource access.
Techniques:

1. Weak Migration - Only code + data move; execution restarts from beginning
Example: Java applets

2. Strong Migration - Code + data + execution state move; continues seamlessly

Example: VM live migration

3. Sender-Initiated - Overloaded node sends process away

4. Receiver-Initiated - Idle node requests tasks

Issues:

1. Resource Binding - Process may need specific resources (identifier/value/type)

2. Execution State - Transferring stack and registers is complex

3. Heterogeneity - Different OS/CPU architectures may not support execution

4. Security - Must protect host from malicious code and code from malicious host

5. Performance Overhead - Migration cost must not exceed benefit

Example: Strong migration in checkpointing systems allows seamless process continuation, but heterogeneity
requires platform-independent bytecode like Java.

Diagram:

CODE MIGRATION
|
┌──────┴──────┐
| |
TECHNIQUES ISSUES
| |
Weak/Strong Resources
Sender/Receiver Heterogeneity
Security
Performance

Q4. Discuss the need for process migration and the role of resource to process and
process to resource binding in process migration.
Answer:

Need for Process Migration:

Process migration is needed for: (1) Load balancing - moving tasks from overloaded to idle nodes, (2) Faster
execution - utilizing powerful hardware, (3) Data locality - reducing network traffic by moving computation to
data, (4) Fault tolerance - evacuating failing nodes, (5) Resource sharing - accessing specialized devices.

Role of Bindings:

Resource → Process Binding:

By Identifier - Specific resource required (e.g., /dev/usb1) → Hard to migrate

By Value - Copyable data (e.g., config files) → Easy to migrate, just copy

By Type - Any resource of that type (e.g., any printer) → Can rebind at destination

Process → Resource Binding:

Weak - Occasional use → Easy to migrate

Medium - Regular use → Migration possible, reconnection needed

Strong - Continuous use (e.g., open files) → Very hard, may need remote access

Example: A process with weak binding by value (configuration files) is easy to migrate, while strong binding by
identifier (specific USB device) makes migration impractical.

Diagram:

PROCESS MIGRATION
|
┌──────┴──────────┐
| |
NEEDS BINDINGS
| |
Load Balance Resource→Process:
Faster Exec - Identifier (hard)
Data Locality - Value (easy)
Fault Tolerant - Type (rebind)
Resource Share
Process→Resource:
- Weak (easy)
- Medium (moderate)
- Strong (hard)

MODULE 5 - REPLICATION, CONSISTENCY AND

FAULT TOLERANCE
Q1. Discuss and differentiate various client consistency models.
Answer:

Client consistency models define how and when replicas make writes visible to readers.

Models:

1. Strong (Linearizability) - Every read returns the most recent write; global real-time order
Example: Bank balance updates

2. Sequential - All processes see operations in same order (not necessarily real-time)
Example: Replicated database logs

3. Causal - If A causes B, everyone sees A before B; concurrent ops in any order

Example: Social media - comment reply appears after original post

4. Read-Your-Writes - Client always sees its own previous writes

Example: After posting a tweet, you see it in your timeline

5. Monotonic Reads - Client never sees older data after seeing newer data
Example: After reading document v5, never see v3

6. Eventual - All replicas converge eventually without ordering guarantees

Example: DNS records propagate and eventually become consistent

Key Differences: Strong/Sequential/Causal control operation ordering. Read-Your-Writes and Monotonic

Reads are per-client session guarantees. Eventual provides only convergence without ordering.

Diagram:

Consistency Strength:

Strong → Sequential → Causal → RYW/Monotonic → Eventual

(Strictest) (Weakest)

Classification:
- Ordering: Strong, Sequential, Causal
- Session: Read-Your-Writes, Monotonic Reads
- Lazy: Eventual

Q2. Explain how Monotonic read consistency model is different than Read your
Write consistency model.
Answer:
Read-Your-Writes Consistency: A client always sees its own previous writes. Guarantees that YOUR updates
are visible to YOU.

Example: You update your profile picture → you immediately see the new picture

Focus: Your OWN writes

Monotonic Reads Consistency: A client never sees older data after seeing newer data. Time never goes
backward.

Example: After reading email message #50, you never see only messages #1-49

Focus: ANY reads (including others' writes)

Key Difference: Read-Your-Writes ensures you see YOUR updates immediately. Monotonic Reads ensures you
never go backward in time for ANY data. RYW is about write visibility; Monotonic is about read progression.

Diagram:

Read-Your-Writes:
Write(X=5) → Read(X) → Must see 5 or newer
(Your write must be visible to you)

Monotonic Reads:
Read(X=v5) → Read(X) → Must see v5, v6, v7... never v3
(Time never goes backward)

Difference:
RYW → "See MY writes"
MR → "Never go back in time"

Q3. What are different data centric consistency models with example data stores? [V
IMP]
Answer:

Data-centric consistency models define how updates are viewed across all replicas.

Models (Strongest → Weakest):

1. Strict Consistency - Every read returns most recent real-time write

Example: If X=10 at 1:00 PM, any read after shows 10

2. Linearizability - Operations appear in real-time order; all replicas see same value
Example: Banking systems - ATM shows updated balance immediately

3. Sequential Consistency - All processes see operations in same order (not real-time)
 Example: If writes are W1, W2 → all replicas apply W1→W2

4. Causal Consistency - Operations with cause-effect relationship maintain order

Example: Comment reply must not appear before original comment

5. FIFO (PRAM) Consistency - Each process's writes seen in its own order
Example: Process P1 writes A then B → everyone sees A before B

6. Eventual Consistency - All replicas converge eventually without immediate ordering

Example: DNS updates take time to propagate but eventually consistent

These differ in strictness of write ordering, from Strict (strongest - banking) to Eventual (weakest - DNS).

Diagram:

Strict → Linearizable → Sequential → Causal → FIFO → Eventual

(Most strict) (Least strict)

Use Cases:
Strict/Linear → Banking, Trading
Sequential → Replicated DBs
Causal → Social Media
FIFO → Message Queues
Eventual → DNS, CDN, NoSQL

Q4. What is fault tolerance? Explain failure models.

Answer:

Fault Tolerance: The ability of a distributed system to continue operating correctly even when components fail,
ensuring no service interruption, data safety, and continuous availability.

Example: If one server crashes, another replica automatically serves requests.

Failure Models:

1. Crash Failure - Process stops unexpectedly and doesn't recover

Example: Server suddenly powers off

2. Omission Failure - Message/request is lost (send/receive omission)

Example: Network packet dropped

3. Timing Failure - Response arrives too late or too early

Example: Real-time system exceeding deadline

4. Byzantine Failure - Component behaves arbitrarily; sends wrong/malicious responses

 Example: Faulty node giving incorrect results to different processes

5. Network/Communication Failure - Delays, partitions, or message corruption

Example: Regional outage causing nodes to become unreachable

Systems use replication and redundancy to handle these failures.

Diagram:

FAILURE MODELS
|
┌─────┼────┬──────┬────┬─────┐
| | | | |
Crash Omit Timing Byz Network
| | | | |
Stop Lost Delay Wrong Partition
Msg Response

Q5. Replication and Types of Replication (Extra)

Answer:

Replication: Keeping multiple copies of data across different servers to provide high availability, fault
tolerance, and better performance.

Types:

1. Active Replication - All replicas run same operation in parallel; vote on output
Example: All servers process every request

2. Passive (Primary-Backup) - Only primary processes requests; backups take over if primary fails
Example: Master-slave database systems

3. Semi-Active - Primary decides order; backups execute in parallel (hybrid approach)

4. Synchronous Replication - Write confirmed only when all replicas update (strong consistency, slower)

5. Asynchronous Replication - Primary updates first, replicas update later (eventual consistency, faster)

Example: Banking uses synchronous replication for consistency; social media uses asynchronous for
performance.

Diagram:
 REPLICATION
|
┌────┴────┬────────┐
| | |
ACTIVE PASSIVE SYNC/ASYNC
| | |
All do Primary When update
same +Backup propagates

MODULE 6 - DISTRIBUTED FILE SYSTEMS

Q1. Distributed File System and Desirable features of Good distributed File System.
[V IMP]
Answer:

Distributed File System (DFS): A file system where files are stored across multiple networked machines but
appear to users as if stored on a single local system, providing location transparency, easy sharing, fault
tolerance, and high performance.

Examples: Google File System (GFS), Hadoop HDFS, NFS

Desirable Features:

1. Transparency - Hides distributed nature; file access appears local

Example: HDFS users don't know which DataNode stores their file

2. Reliability & Availability - Continues working despite machine failures

Example: GFS/HDFS keep 3 replicas of each file block

3. Scalability - Supports large number of files, users, and storage nodes

Example: HDFS scales to petabytes by adding DataNodes

4. Fault Tolerance - Automatic recovery from failures

Example: If one replica fails, read from another

5. Security - Access control, authentication, secure communication

Example: Kerberos authentication in HDFS

6. Consistency - All replicas show same data after updates

Example: GFS versioning ensures consistent reads
 7. High Performance - Fast access using caching and replication

Diagram:

CLIENT
|
(File Access)
|
--------------
| | |
Node1 Node2 Node3
(Replicas of same file)

Features: T-R-S-F-S-C-P
(Transparency, Reliability,
Scalability, Fault Tolerance,
Security, Consistency, Performance)

Q2. Explain file caching schemes. [V IMP]

Answer:

File caching stores frequently accessed file data at client or server to reduce access time and network load.

Types:

1. Client-Side Caching - Data cached at client machine (RAM/disk)

Example: NFS client stores file blocks locally

Advantage: Faster access, fewer server requests

2. Server-Side Caching - Server keeps recently accessed blocks in memory

Advantage: Multiple clients benefit

3. Cache Granularity - Block-level, file-level, or record-level caching

4. Write Policies:
Write-Through - Immediately send writes to server (strong consistency, slower)

Write-Back - Cache locally, send later (high performance, inconsistency risk)

5. Consistency Mechanisms:
Client Validation (NFS) - Check with server before using cache

Callback (AFS) - Server notifies clients when file changes

Example: NFS uses client-side caching with validation; AFS uses callback-based caching for better
performance.
Diagram:

FILE SERVER
(Cache + Files)
|
Network
|
--------------
| | |
Client1 Client2 Client3
(Cache) (Cache) (Cache)

Write Policies:
Write-Through → Server ← Immediate
Write-Back → Cache ← Later flush

Consistency:
NFS → Validate before use
AFS → Callback on change

Q3. List desirable features of distributed File systems. How are modifications
propagated in file caching schemes?
Answer:

Desirable Features: Transparency, Reliability, Scalability, Fault Tolerance, Security, Consistency, and High
Performance (same as Q1).

Modification Propagation:

Modifications are propagated using:

1. Write-Through Policy
Every write immediately sent to server

Ensures strong consistency but slower

Example: Banking systems requiring accurate writes

2. Write-Back Policy
Changes stored in client cache first, sent later

Improves performance but may cause inconsistency if client crashes

Example: AFS with callback-based consistency

3. Cache Consistency Protocols: a) Client Validation (NFS)

 Before using cached data, client checks with server if file changed

If modified → fetch new version

If not → use cached copy

b) Callback/Token-Based (AFS)
Server gives client callback promise (permission)

If another client modifies file → server revokes callbacks and sends new data

Ensures all clients eventually see latest version

Example: NFS validates on each access for consistency; AFS uses callbacks to reduce server load while
maintaining consistency.

Diagram:

Propagation Methods:

Write-Through:
Client → Write → Server (immediate)

Write-Back:
Client → Write → Cache → Server (delayed)

Consistency:

NFS (Validation):
Client → Check → Server → OK/Fetch New

AFS (Callback):
Server → Callback → Client
Revoke when modified

Q4. Discuss Google file system (GFS) as a scalable distributed file system.
Answer:

GFS is a highly scalable, fault-tolerant distributed file system designed by Google to handle huge datasets.

Key Scalability Features:

1. Chunk-Based Storage (64 MB chunks)

Files divided into large fixed-size chunks across many servers

Reduces metadata load, faster sequential reads/writes

 Supports TB-PB datasets

2. Master-Chunkserver Architecture
Master stores metadata (namespace, chunk locations)

Chunkservers store actual chunks

Easy scaling: add more chunkservers

3. Replication for Fault Tolerance

Each chunk has 3 replicas on different machines/racks

Ensures high availability and quick recovery

4. Automatic Rebalancing & Recovery

When servers join/fail, Master automatically re-replicates chunks

System redistributes load for uninterrupted scalability

5. Optimized for Large Files & Batch Processing

Designed for Google Search, ML training, MapReduce

High throughput, append-only writes

6. Efficient Metadata Management

Master keeps metadata in RAM → extremely fast lookups

Checkpointing ensures persistence

Simple, scalable namespace

Example: GFS powers Google's search indexing and analytics, handling petabytes of data across thousands of
servers with automatic fault recovery.

Diagram:
 MASTER
(Metadata in RAM)
|
--------+--------
| | |
ChunkServer1 CS2 CS3
(64MB chunks) (Replicas)
| | |
Chunk1 Chunk1 Chunk2
Chunk3 Chunk2 Chunk1
(3 replicas each)
|
--------+--------
| | |
Client1 Client2 Client3

Features:
- 64MB chunks
- 3-way replication
- Master-chunkserver
- Auto-rebalancing
- Petabyte-scale

Q5. Network File System (NFS) - Extra

Answer:

Network File System (NFS): A client-server distributed file system that allows users to access remote files as if
they are local.

Key Features:

1. Client-Side Caching - Stores recently accessed data locally for fast access

2. Stateless Servers - Server doesn't maintain client state; improves fault tolerance

3. RPC Protocol - Uses Remote Procedure Call for communication

4. Transparent Access - Remote files appear as local files

5. Client Validation - Before using cache, checks with server if file changed

Example: UNIX/Linux systems use NFS mounts to share files across networks transparently.

Diagram:
 NFS ARCHITECTURE

NFS Server
(Shared Files)
|
RPC Protocol
|
-------------
| | |
Client1 Client2 Client3
(Mount) (Mount) (Mount)
/nfs/share appears local

Caching:
Client → Cache → Validate → Server
(on access)

QUICK REFERENCE GUIDE

Module 4 Key Points:
Global Scheduling: Load balance, scalability, fault tolerance, low overhead, transparency, adaptability

Load Estimation: Queue, CPU, Resource, Hybrid

Process Transfer: Threshold, Selection, Information, Transfer

Code Migration: Weak (restart), Strong (continue), Sender/Receiver initiated

Migration Issues: Resource binding (IVT), Heterogeneity, Security, Performance

Module 5 Key Points:

Client Consistency: Strong → Sequential → Causal → RYW/Monotonic → Eventual

Data-Centric: Strict → Linearizable → Sequential → Causal → FIFO → Eventual

Failure Models: Crash, Omission, Timing, Byzantine, Network

Replication: Active, Passive, Sync, Async

Module 6 Key Points:

DFS Features: Transparency, Reliability, Scalability, Fault tolerance, Security, Consistency, Performance

Caching: Client/Server-side, Write-through/Write-back, Validation/Callback

 GFS: 64MB chunks, Master-Chunkserver, 3 replicas, auto-rebalancing, petabyte-scale

END OF DOCUMENT

All answers are exam-ready and can be written directly in your answer sheet.