DISTRIBUTED SYSTEMS

Comprehensive Study Notes

Based on: Tanenbaum & Van Steen — Distributed Systems: Principles and Paradigms, 2nd Edition (2007)
 1. Process Migration — Need, Resource & Process
Bindings

1.1 Need for Process Migration

Traditionally, process migration meant moving an entire running process from one machine to another
(Milojicic et al., 2000). The primary motivation is performance improvement — processes are moved
from heavily-loaded to lightly-loaded machines. Load is commonly expressed as CPU queue length or
CPU utilization.

Additional reasons for process migration:

• Minimize communication — processing data close to where it resides avoids flooding the
network. E.g., shipping part of a client application to the database server to avoid transferring
large datasets.
• Flexibility — dynamically configure distributed systems at runtime instead of at compile time.
• Parallelism — mobile agents can be replicated and sent to different sites for near-linear speed-
up in search tasks.

1.2 Process Segments (Fuggetta et al., 1998)

A process consists of three segments:
Segment Description Example

Code Segment The set of instructions that make up the Binary executable
program being executed

Resource Segment References to external resources (files, File handles, TCP sockets,
printers, devices, other processes) printer references

Execution Segment Current execution state: private data, stack, Stack frames, PC register,
program counter local variables

1.3 Process-to-Resource Bindings (3 Types)

These describe how tightly a process is coupled to a particular resource:
Binding Type Description Example

By Identifier Process requires exactly that specific URL, FTP server IP address,
resource — nothing else will do TCP port number

By Value Only the content/value of the resource Standard C/Java libraries —

matters; another resource with the same their location may differ but
content is equally acceptable content is same

By Type Process only needs any resource of the A monitor, printer, or any local
specified type; exact instance is irrelevant device
1.4 Resource-to-Machine Bindings (3 Types)
These describe how movable a resource is from its current machine:
Binding Type Description Example

Unattached Easily moved between different machines Data files associated only with
without significant cost the migrating process

Fastened Moving is possible but only at relatively high Local databases, complete
cost Web sites

Fixed Intimately bound to a specific machine — Local devices, TCP

cannot be moved at all communication endpoints

1.5 The 3×3 Binding Matrix — Actions During Migration

📊 Tanenbaum Fig. 3-19 (Book p. 109) — Actions to be taken with respect to the references to local
resources when migrating code to another machine.

Combining 3 process-to-resource bindings × 3 resource-to-machine bindings gives 9 combinations:

Process binds by Unattached Resource Fastened Resource Fixed Resource

→

Identifier Move resource with Establish global Establish global

process (or establish reference (e.g., URL) reference — may be
global reference if prohibitively expensive
shared)

Value Copy/move resource; if Copy if small (libraries); Need distributed shared

shared, establish global global reference if huge memory — often
reference (dictionaries) infeasible

Type Rebind to locally Rebind to local resource Rebind to local resource

available resource of of same type of same type if available
same type
 2. Global Scheduling Algorithm & Distributed File System
Features

2.1 Desirable Features of a Global Scheduling Algorithm

A global (load distribution) scheduling algorithm assigns and redistributes tasks across nodes.
Desirable features:
• No single point of failure — must be distributed; no central coordinator that can crash and halt
everything
• Low overhead — cost of scheduling decisions must be minimal relative to gains from better load
distribution
• Scalability — must work efficiently as the number of nodes grows to hundreds or thousands
• Fairness — all processes should receive equitable access to processor resources
• Stability — must not oscillate (thrash) by moving processes back and forth between machines
needlessly
• Support for heterogeneity — must account for differences in processor speeds, memory, and
capabilities
• Transparency — migration must be invisible to the migrating process and its clients
• Performance-driven decisions — must be based on real load metrics: CPU queue length, CPU
utilization, or other indicators
• Demand-driven or periodic information gathering — must balance freshness of load information
against communication cost

2.2 Features of a Good Distributed File System

A DFS presents a unified file system across multiple machines. Key features:

Transparency (Multiple Levels)

• Access transparency — local and remote files accessed by identical operations
• Location transparency — files can be moved between servers without changing their names or
paths
• Migration transparency — file system itself can be relocated without disrupting clients
• Replication transparency — clients are unaware that files are replicated across multiple servers
• Concurrency transparency — multiple clients can share files without observing each other's
intermediate states

Performance
Access time for remote files should approach local file access times. GFS achieves this by directing
clients straight to chunk servers after one metadata lookup.

Scalability
Should scale to thousands of nodes. Google File System (described in Tanenbaum Chapter 11)
handles this by separating metadata management (single master) from actual data serving (many
chunk servers).
Fault Tolerance
Failures should be handled gracefully. GFS replicates each 64 MB chunk across multiple chunk servers
using a primary-backup scheme.

Consistency
Clients should see consistent data. NFS v2/v3 used stateless servers for simplicity; NFS v4 switched to
stateful servers for better cache consistency over wide-area networks.

Security & Heterogeneity

Should support access control, authentication (NFS v4 supports Kerberos), and work across different
OS and hardware platforms.
 3. Issues in the Global Scheduling Algorithm

Global scheduling raises several fundamental problems. Tanenbaum identifies these issues in the
context of load-sharing and load-balancing systems:

Issue Explanation

Transfer Policy When should a process be migrated? Common approach: threshold-based

— migrate if load exceeds an upper threshold; accept work if load is below
a lower threshold.

Selection Policy Which process to migrate? Newly created processes are preferred over
running ones — they are easier to move (no execution state to transfer) and
disrupt nothing.
Location Policy Which target machine to migrate to? Options: random probing, polling a set
of machines, or using a central directory service. Each trades accuracy for
overhead.

Information Policy When to gather load information? Options: (1) demand-driven — query
when a migration decision is needed; (2) periodic — broadcast at fixed
intervals; (3) state-change — broadcast when load crosses a threshold.

Stability If too many machines simultaneously try to offload work, they may all send
processes to the same idle machines and cause those to become
overloaded. The algorithm then oscillates — a well-known hazard.

Communication Gathering load info and broadcasting decisions consumes network and
Overhead CPU. If too frequent, the overhead can outweigh any performance
improvement from migration.

Scalability Centralized algorithms create a bottleneck and single point of failure.

Distributed algorithms are harder to design correctly and may produce
suboptimal decisions.

Heterogeneity Different machines have different speeds and capabilities. A process that
runs fast on Machine A may be slow on Machine B. Comparing loads
across heterogeneous machines is non-trivial.

Migration Cost Moving a running process is expensive — code, execution state, and
resource bindings must all transfer. The benefit of migration must outweigh
this cost. For this reason, newly-arriving processes are preferred migration
candidates.
 4. Singhal's Heuristic & Raynal's Tree-Based Algorithm

4.1 Singhal's Heuristic Algorithm (Distributed Mutual Exclusion)

Singhal's algorithm is a heuristic-based approach to distributed mutual exclusion that reduces the
number of messages required compared to Ricart-Agrawala. The key insight is that a process does not
need to request permission from all N-1 processes every time — only from those that might currently be
interested in the critical section (CS).

How It Works
• Each process maintains a local estimate of every other process's state: whether it is currently in
the CS, requesting the CS, or in its remainder section.
• When a process wants to enter the CS, it sends REQUEST only to processes it believes might
be competing — not to all processes.
• When processes exchange messages (REQUESTs, REPLYs), they piggyback state information
to update each other's knowledge about the system.
• Over time, each process's knowledge of others improves, reducing unnecessary messages.
• Worst-case message complexity remains O(N), but in practice (with good heuristics) it is
significantly less.

Why 'Heuristic'?
It uses learned/historical information about process states rather than a deterministic rule.
The algorithm makes educated guesses about who is competing, reducing message count on average.
This is called a heuristic because correctness (safety + liveness) is maintained, but optimality is
approximated.

4.2 Raynal's Tree-Based Algorithm (Distributed Mutual Exclusion)

Raynal's algorithm organizes the processes as nodes in a logical tree and uses a token-passing
mechanism to grant access to the critical section. (Raynal and Singhal, 1996 — referenced in
Tanenbaum Chapter 6 context).

Key Features
• Processes are arranged in a static logical tree structure. No single coordinator — responsibility
is distributed across the tree.
• A token circulates in the tree. The holder of the token is allowed to enter the critical section.
• A process wanting to enter the CS sends a REQUEST message up toward the root of the tree.
• The token travels back down toward the requesting node, passing through intermediate nodes.
• Requests are queued at each intermediate node in FIFO order, ensuring fairness — starvation
is prevented.
• In a balanced tree, message complexity is O(log N), making it more efficient than Ricart-
Agrawala for large systems.
Algorithm Message Complexity Key Property

Centralized (Ch. 6.3.2) 3 messages per CS entry Simple; single coordinator is

bottleneck & SPOF

Ricart-Agrawala (Dist.) 2(N-1) messages per CS entry Fully distributed; expensive

Singhal Heuristic < 2(N-1) on average Reduces messages using

learned state estimates

Raynal Tree-Based O(log N) in balanced tree Efficient, fair, no SPOF; token

travels tree

Token Ring (Ch. 6.3.5) 1 to N messages per CS entry Token circulates ring; wasteful
when no contention
 5. Data-Centric vs. Client-Centric Consistency Models

5.1 Distinction
Aspect Data-Centric Client-Centric

Focus System-wide consistent view of the Consistency from a single client's

entire shared data store perspective only

Assumption Multiple concurrent processes Mostly reads; updates are rare or

simultaneously update data single-writer

Examples Sequential, Causal, Entry Monotonic Reads, Monotonic

Consistency Writes, Read Your Writes, Writes
Follow Reads

Goal All processes see the same globally A single client never sees
consistent view inconsistencies in its own operations

Cost Expensive with concurrent writes Cheaper — guarantees only for one
client at a time

5.2 Data-Centric Model: Sequential Consistency (Lamport, 1979)

📊 Tanenbaum Fig. 7-4 (Book p. 282) — Behavior of two processes operating on the same data item —
propagation delay is acceptable.
📊 Tanenbaum Fig. 7-5 (Book p. 283) — (a) A sequentially consistent data store. (b) A data store that is
NOT sequentially consistent.

Definition (Lamport, 1979)

The result of any execution is the same as if the read and write operations by all
processes on the data store were executed in some sequential order, and the
operations of each individual process appear in this sequence in the order
specified by its program.

Key Points
• No reference to real time or wall-clock order — only program order must be preserved per
process.
• All processes must see the SAME interleaving of operations, even if that interleaving differs
from real-time ordering.
• A data store is sequentially consistent if any process's write is eventually visible to all others in
the same order.
Example (Fig. 7-5 from Tanenbaum, p. 283)
P1 writes x=a, P2 writes x=b. Both P3 and P4 read b first, then a. This is VALID — P2's write appears
to precede P1's for all processes, even though P1 wrote first in real time. It is only invalid if P3 sees (b,
then a) while P4 sees (a, then b) — different orderings violate sequential consistency.

5.3 Client-Centric Model: Monotonic Reads

📊 Tanenbaum Fig. 7-12 (Book p. 292) — The read operations performed by a single process P at two
different local copies. (a) Monotonic-read consistent. (b) Does NOT provide monotonic reads.

Definition
If a process reads the value of a data item x, any successive read operation on x
by that process will always return that same value or a more recent value.
A client never 'goes back in time'.

Example
A user reads his email in San Francisco and sees messages M1, M2, M3. He travels to New York and
connects to a different replica. Monotonic-read consistency guarantees the New York replica shows at
least M1, M2, M3 — he will never see a state where those messages have disappeared.
Notation: WS(x1; x2) — the write set at L1 must be a subset of the write set at L2 before the second
read.
 6. Process Resilience and Recovery

6.1 The Need for Process Resilience

A distributed system must continue operating even when some processes fail. Process resilience is
achieved by replicating processes into groups. The key property: when a message is sent to the group,
all members receive it — if one process fails, another takes over (Guerraoui and Schiper, 1997).

6.2 Dependability Properties (Kopetz and Verissimo, 1993)

Property Definition
Availability System is ready to be used immediately — probability it is working correctly at
any given instant.

Reliability System runs continuously without failure over a time interval. A system down
for 1ms every hour is 99.9999% available but still unreliable.

Safety When a system temporarily fails, nothing catastrophic happens. Critical for
nuclear plant controllers and spacecraft.

Maintainability How easily a failed system can be repaired. Highly maintainable systems
recover fast, boosting availability.

6.3 Fault Classification

• Transient faults — occur once and disappear. E.g., a bird flying through a microwave beam
causes lost bits; retransmission succeeds.
• Intermittent faults — come and go unpredictably. E.g., a loose connector. Hardest to diagnose
because the fault may disappear when a technician arrives.
• Permanent faults — continue until the component is replaced. E.g., burnt-out chips, software
bugs, disk head crashes.

6.4 Failure Masking by Redundancy

📊 Tanenbaum Fig. 8-2 (Book p. 327) — Triple Modular Redundancy (TMR) — each device is replicated
three times, with voters at each stage.

1. Information redundancy — extra bits added to allow recovery from garbled bits. E.g., Hamming
codes added to transmitted data to recover from noise.
2. Time redundancy — an action is performed and, if it fails, performed again. Used in
transactions: if a transaction aborts, it can be redone with no harm.
3. Physical redundancy — extra equipment or processes are added. E.g., Triple Modular
Redundancy (TMR) uses three copies of each device plus voters to mask any single failure.
6.5 Process Groups — Design Issues
📊 Tanenbaum Fig. 8-3 (Book p. 329) — (a) Communication in a flat group. (b) Communication in a simple
hierarchical group.

Flat Groups
• All processes are equal — no single coordinator.
• No single point of failure: if one process crashes, the group continues (just smaller).
• Disadvantage: collective decision-making is complex — votes must be taken, incurring delay
and overhead.

Hierarchical Groups
• One process is the coordinator; others are workers.
• Coordinator makes decisions efficiently without consulting everyone.
• Disadvantage: loss of coordinator halts the entire group — a single point of failure.

6.6 Recovery
Checkpointing (Backward Error Recovery)
• The system periodically saves its state to stable storage.
• On failure, the system rolls back to the last consistent checkpoint — called a recovery line.
• Messages sent after the checkpoint must be replayed using message logging.
• Problem: finding a globally consistent checkpoint (recovery line) across all processes is non-
trivial due to messages in transit at the time of the checkpoint.
• The domino effect: if checkpoints are not properly coordinated, rolling back one process may
force others to also roll back, cascading to the start.

Message Logging
• Logs all messages to stable storage. On failure, replay logged messages to reach the pre-
failure state.
• Optimistic logging: log messages asynchronously (faster, but orphan messages may appear
after recovery).
• Pessimistic logging: flush logs synchronously before proceeding (slower, but guarantees
consistency).
 7. Sequential and Release Consistency Models with
Examples

7.1 Sequential Consistency (Detailed Example)

Consider three concurrently executing processes P1, P2, P3 (Dubois et al., 1988 — cited in
Tanenbaum p. 283). All variables x, y, z initialized to 0:

P1 P2 P3

x=1 y=1 z=1

print(y, z) print(x, z) print(x, y)

Sequential consistency allows 90 valid orderings (any interleaving that preserves each process's
program order). Example valid signatures (concatenation of each process's print output):
• 111111 — P1 fully executes, then P2, then P3. Output: P1 prints (1,1), P2 prints (1,1), P3 prints
(1,1). Signature: 111111.
• 100110 — one valid interleaving where P1 sees y=0, z=0 (prints 00), etc.
Signature 001001 is INVALID — it would require P1 to print before P2/P3 start, but also P3 to complete
before P1 starts, which is contradictory.
The contract: all processes must accept any of the 90 valid results as correct program behavior.

7.2 Release Consistency

Release consistency (and its more specific form, Entry Consistency — Tanenbaum Chapter 7/10) is a
relaxed model designed for performance. The key observation is that accesses to shared data are
normally bracketed by synchronization operations (acquire/release for critical sections).

📊 Tanenbaum Fig. 7-10 (Book p. 287) — A valid event sequence for entry consistency — P1 acquires x
then y; P2 acquires x only; P3 acquires y only.

Core Rules
4. Acquire rule — before a process completes an ACQUIRE, all remotely performed updates to the
guarded shared data must be made visible. No acquire may complete until all pending writes
from others have propagated.
5. Exclusive release rule — before another process can ACQUIRE a variable in exclusive mode,
no other process may hold it (even in non-exclusive mode).
6. Non-exclusive acquire rule — a process wanting to acquire in non-exclusive mode must first
check with the owner for the most recent copy of the guarded data.
Example (Fig. 7-10, Tanenbaum p. 287)
• P1 does acquire(x), writes x=a, then acquire(y), writes y=b, then release both.
• P2 does acquire(x) — sees x=a (correct, because P1 released x). P2 does NOT acquire y, so it
may see y=NIL. This is correct behavior under release/entry consistency.
• P3 does acquire(y) — sees y=b (correct, because P1 released y before P3 acquired it).
The key advantage: P2 does not need to see y's update because it never acquired the lock for y. This
eliminates unnecessary synchronization overhead compared to sequential consistency.
 8. Types of Failures and K-Fault Tolerance

8.1 Types of Failures

📊 Tanenbaum Fig. 8-1 (Book p. 325) — Different types of failures — classification scheme based on
Cristian (1991) and Hadzilacos & Toueg (1993).

Failure Type Description Example

Crash (Fail-Stop) Server halts prematurely and was working OS kernel panic
correctly until it stopped. Nothing heard from it requiring reboot
afterward.

Omission — Receive Server never receives the incoming request (no No listener on socket
thread listening). Server state is unaffected.

Omission — Send Server did the work but fails to send the reply Buffer overflow on
(e.g., send buffer overflow). response

Timing (Performance) Server responds but outside the specified time Isochronous stream
interval — too slow or too fast. buffer overflow

Response — Value Server provides a wrong reply to a request. Search engine returns
irrelevant results

Response — State Server reacts unexpectedly to an incoming Unhandled message

Trans. message it cannot recognize — takes wrong triggers wrong default
default action.

Arbitrary (Byzantine) Most severe. Server produces output it should Malicious collusion
never have produced, which cannot be detected between faulty nodes
as wrong. May even collude with other faulty
servers to produce wrong answers.

Additional categories:
• Fail-silent — server stops but doesn't announce it; others may mistake it for being slow.
• Fail-safe — server produces obviously wrong output (recognizable as junk) — a benign form of
arbitrary failure.

8.2 K-Fault Tolerance

📊 Tanenbaum Fig. 8-4 (Book p. 333) — Circumstances under which distributed agreement can be reached
— showing the nontrivial nature of agreement when processes may fail.

Definition
A system is said to be k fault tolerant if it can survive faults in k components
and still meet its specifications (Tanenbaum, p. 331).
 Failure Model Replicas Required Reasoning

Fail-silent (Crash) k + 1 replicas If k crash silently, the remaining

1 correct one answers.

Byzantine (Arbitrary) 2k + 1 replicas minimum (3k + 1 k faulty processes might send

total) the same wrong answer. k+1
correct ones outvote them.
Lamport et al. (1982):
agreement requires > 2/3
correct processes.

Precondition: All requests must arrive at all replicas in the same order — this is the atomic multicast
problem, discussed in Section 8.2.2.
 9. Google File System (GFS) — Cluster-Based Distributed
File System

Tanenbaum Chapter 11 covers GFS as the primary example of a cluster-based DFS. HDFS (Hadoop
Distributed File System) is architected on the same principles. The GFS design is described in
Ghemawat et al. (2003).

📊 Tanenbaum Fig. 11-5 (Book p. 498) — The organization of a Google cluster of servers — single master
with multiple chunk servers.

9.1 Context and Design Assumptions

• Google files are very large — commonly multiple gigabytes — where each file contains many
smaller objects.
• Updates occur mostly by appending data rather than overwriting parts of files.
• Server failures are the norm rather than the exception — the design must assume failures will
happen regularly.
• Traditional DFS assumptions (rare failures, small files, random writes) no longer hold at
Google's scale.

9.2 Architecture
Single GFS Master
• Manages all metadata: namespace (path names → inodes), file-to-chunk mappings, and chunk
locations.
• Maintains the entire namespace table in main memory for fast access.
• Does NOT maintain real-time accurate chunk locations — instead polls chunk servers
periodically (simplifies design enormously).
• Updates to the namespace are logged to persistent storage. When the log is too large, a
checkpoint is created for fast restart.

Multiple Chunk Servers

• Store actual data. Each GFS file is divided into 64 MB chunks, each with a unique identifier.
• Chunks are replicated across multiple chunk servers using a primary-backup scheme.
• Perform the bulk of actual data I/O — the master is rarely in the data path.

9.3 Data Access Flow

7. Client sends file name + chunk index to master.
8. Master returns the contact address (chunk server addresses) for that chunk.
9. Client communicates directly with the chunk server — master is completely out of the data path.
 10. For writes, client pushes data to the nearest chunk server → it propagates to others → client
contacts primary chunk server to assign a sequence number → primary passes the order to
backups.

9.4 Why GFS Scales

• Bulk of work (data I/O) is done by chunk servers — the single master is not a bottleneck.
• Entire namespace fits in master's RAM — no disk I/O for metadata lookups.
• Clients contact master only for metadata — for large files this is rare relative to data volume.
• Chunk servers self-report their contents to the master periodically — no need for master to track
every state change.

Relation to HDFS
HDFS mirrors GFS architecture:
GFS Master → HDFS NameNode
GFS Chunk Servers → HDFS DataNodes
GFS 64 MB chunks → HDFS 128 MB blocks (default)
Same principle: NameNode handles metadata, DataNodes handle data I/O.
 10. Transfer Policy (Sender-Initiated)

A transfer policy determines WHEN a process should be migrated. Tanenbaum discusses three main
policies:

10.1 Sender-Initiated Policy

The machine currently holding the process (the sender) initiates migration when it becomes
overloaded.

Mechanism
11. When a new process is created, the local machine checks its own load level.
12. If local load > upper threshold (overloaded): the machine probes randomly selected remote
machines.
13. If a probed machine's load < lower threshold: the new process is sent there.
14. If after N probes no suitable machine is found: the process runs locally.

Advantages
• Simple to implement — the overloaded machine takes initiative.
• Effective at distributing load away from hot-spot machines.

Disadvantages
• When many nodes are simultaneously overloaded, all of them probe the same set of lightly-
loaded machines, flooding them and causing the very overload they are trying to avoid —
oscillation/instability.
• Under high system-wide load, probing overhead itself becomes a significant burden.

10.2 Receiver-Initiated Policy

An underloaded machine advertises its availability and invites processes from overloaded machines.
• More stable under high load — only idle machines send probes, not every overloaded machine.
• Idle machines must continuously broadcast availability — wasteful when the system is mostly
lightly loaded.

10.3 Symmetric Policy

Both overloaded machines push processes AND underloaded machines pull processes. Provides
better overall stability than either pure approach. Most real systems use a form of symmetric policy.

Policy Stability Overhead

Sender-Initiated Poor under high load (oscillation Low when lightly loaded
risk)

Receiver-Initiated Good under high load High when lightly loaded (idle
nodes broadcast)

Symmetric Best overall stability Moderate — balanced probe

traffic
 11. Monotonic Reads, Monotonic Writes, Read Your
Writes

These are three of the four client-centric consistency models from Bayou (Terry et al., 1994), described
in Tanenbaum Chapter 7.3. They provide guarantees for a single client even when accessing different
replicas over time.

11.1 Monotonic Reads

📊 Tanenbaum Fig. 7-12 (Book p. 292) — The read operations by process P at two different local copies. (a)
Monotonic-read consistent. (b) Does NOT provide monotonic reads.

Definition (Tanenbaum p. 291)

If a process reads the value of a data item x, any successive read operation on x
by that process will always return that same value or a more recent value.

Guarantee: A client will never 'go back in time' — once it has seen a value of x, it will never see an
older version.
Notation: WS(x1; x2) — the write set at L1 must be a subset of the write set at L2 before the second
read.
Example: User reads email in San Francisco (sees M1, M2, M3). Travels to New York and connects to
a different replica. Monotonic reads guarantees he will see at least M1, M2, M3 — the New York replica
must have propagated those writes before serving the user.

11.2 Monotonic Writes

📊 Tanenbaum Fig. 7-13 (Book p. 293) — Write operations by a single process P at two different local
copies. (a) Monotonic-write consistent. (b) Does NOT provide monotonic-write consistency.

Definition (Tanenbaum p. 292)

A write operation by a process on a data item x is completed before any
successive write operation on x by the same process.

Guarantee: Writes by the same process are applied in the order they were issued, everywhere. A copy
of x may only receive write W2 after it has first received write W1.
Note: Resembles data-centric FIFO consistency, but applies to a single client rather than a collection of
concurrent processes.
Example: A software library is updated. Version 2 depends on Version 1. Monotonic-write consistency
ensures Version 2 is applied to a copy only after Version 1 has already been applied there. Without
this, Version 2 might overwrite a stale copy, producing a corrupted library.
11.3 Read Your Writes
📊 Tanenbaum Fig. 7-14 (Book p. 294) — (a) A data store that provides read-your-writes consistency. (b) A
data store that does NOT.

Definition (Tanenbaum p. 294)

The effect of a write operation by a process on data item x will always be seen
by a successive read operation on x by the same process.

Guarantee: A process always sees the effects of its own writes, no matter which replica it reads from
next.
Example 1 (Web page): A user edits and saves a Web page. When he refreshes his browser, he
should see the updated version — not a cached stale copy. Read-your-writes ensures the cache is
invalidated, so the updated file is always fetched.
Example 2 (Password change): A user changes their library password. Without read-your-writes, the
new password may not yet have propagated to the authentication server — the user gets locked out
temporarily. Read-your-writes ensures the new password takes effect immediately for that user.

11.4 Writes Follow Reads

📊 Tanenbaum Fig. 7-15 (Book p. 295) — (a) A writes-follow-reads consistent data store. (b) A data store
that does NOT.

Definition (Tanenbaum p. 295)

A write operation by a process on data item x following a previous read operation
on x by the same process is guaranteed to take place on the same or a more
recent value of x that was read.

Example: User reads article A in a newsgroup. Then posts response B. Writes-follow-reads ensures B
is stored at a copy only after A is also stored there — readers will always see the original article before
any responses to it.
 12. Design and Implementation Issues of DSM

Distributed Shared Memory (DSM) creates the illusion of a single shared address space across
physically distributed machines. Processes can use normal read/write operations without explicit
message passing. Tanenbaum references this as a foundational consistency topic.

12.1 Design Issues

Issue Explanation

Granularity DSM is typically implemented at the page level. The false sharing
problem: two processes access different variables on the same page —
every access causes a page transfer even though variables are
unrelated. Smaller granularity reduces false sharing but increases
overhead.

Consistency Model Which model to enforce? Sequential consistency is intuitive but

expensive. Entry consistency (as in Munin/TreadMarks) is popular —
associate each shared variable with a lock; synchronize data only at
acquire/release.

Replication & Caching Pages can be replicated for read performance. Challenge: keeping
replicas consistent. On a write, all other copies must be invalidated or
updated.

Page Ownership Fixed ownership: owner never changes — writes always go to owner
(simple but creates bottleneck). Dynamic ownership: ownership migrates
to the current writer (reduces bottleneck but complicates tracking).

Update vs. Invalidate Write-invalidate: all other copies are invalidated on a write — next read
triggers a fetch. Efficient for write-once-then-many-reads patterns. Write-
update: all copies receive the new value immediately — efficient when
multiple processes frequently read a written item.

False Sharing Two processes on different machines write to different variables on the
same page → constant page transfers and invalidations, even though
they don't actually share data. Solution: careful data layout, or multiple-
writer protocols (TreadMarks) that allow concurrent writers on one page
and merge diffs at synchronization points.

Thrashing A page is requested back and forth between two machines so rapidly that
the transfer overhead overwhelms any benefit from DSM. Requires
careful application design and possibly reducing sharing frequency.

12.2 Implementation Approaches

Software DSM (Page-Level)
• Implemented entirely in software using the OS virtual memory system.
• When a process accesses a remote page, a page fault is triggered and the OS fetches the page
from the owning machine.
 • Transparent to application code but suffers from large granularity and false sharing.

Entry Consistency (Lock-Based DSM)

• Each shared data object is associated with a synchronization variable (lock).
• Data is only synchronized when a process acquires or releases the associated lock.
• Dramatically reduces synchronization overhead vs. sequential consistency.
• Used in TreadMarks and Munin — industry-research DSM systems.
 13. Group Communication & Totally Ordered Multicasting

13.1 Group Communication

Group communication allows a process to send a message to a collection of processes (a group) as a
single abstract entity, without knowing who they are, how many there are, or where they are
(Tanenbaum Chapter 8.2).

Required Mechanisms
• Group creation and deletion
• Join/leave operations — must be synchronized with the message stream (a joining process
must receive all subsequent messages; a leaving process must stop receiving messages, and
others must stop receiving from it)
• Failure detection — crashed members do not announce departure; timeout-based detection is
required
• Group rebuild protocol — if too many members crash, some process must take initiative to
rebuild the group

Message Ordering Guarantees

Ordering Guarantee

Unordered Messages may arrive in any order at any receiver.

FIFO-Ordered Messages from the same sender arrive in the order they were sent.

Causally-Ordered Causally related messages are delivered in causal order (weaker than
total order).

Totally Ordered All messages are delivered to ALL processes in exactly the same
global order, regardless of sender or timing.

13.2 Totally Ordered Multicasting

📊 Tanenbaum Fig. 6-11 (Book p. 248) — Updating a replicated database and leaving it in an inconsistent
state — the classic motivation for totally ordered multicast.

The Problem
Without total ordering, replicated databases can become inconsistent:
• Customer deposits $100 (account: $1,000). Bank adds 1% interest. Both updates must go to
both replicas.
• San Francisco replica applies: deposit first ($1,100), then interest ($1,111).
• New York replica applies: interest first ($1,010), then deposit ($1,110).
• Result: $1,111 vs $1,110 — two different values for the same account. Inconsistency!
The solution: both updates must be applied in the same order at all replicas. Which order does not
matter for consistency — only that the order is identical.

Implementation Using Lamport Clocks (Tanenbaum p. 248)

15. Each message is timestamped with the sender's Lamport logical clock value.
16. When a process multicasts a message, it conceptually sends it to itself as well.
17. Messages from the same sender are received in the order they were sent (no reordering).
18. Each receiver places incoming messages in a local priority queue ordered by timestamp.
19. The receiver multicasts an ACKNOWLEDGMENT to all others. (Ack timestamp > message
timestamp, per Lamport's rules.)
20. A message is delivered to the application ONLY when: (a) it is at the HEAD of the queue (lowest
timestamp), AND (b) it has been acknowledged by EVERY other process.
21. Since all processes maintain the same copy of the queue, all messages are delivered in the
same order everywhere — totally-ordered multicast achieved.

State Machine Replication (Schneider, 1990)

Totally-ordered multicasting is the basis for state machine replication.
Replicas follow the same transitions in the same finite state machine.
This is the fundamental technique for keeping replicated services consistent.
 14. Load Balancing vs. Task Assignment Schemes

14.1 Task Assignment Approach (Static)

Task assignment is a static approach used primarily in compute-intensive systems (e.g., distributed
computing clusters, parallel processing). Decisions are made at compile time or job-submission time.

Key Characteristics
• System knows (or estimates) task characteristics — computation time, data requirements,
communication patterns — before execution.
• Tasks are assigned to processors to minimize total execution time or maximize CPU utilization.
• Considers task dependencies, communication costs, and processor capabilities.
• No runtime migration — tasks stay where assigned.

Example
A parallel weather simulation is divided into sub-problems based on geographic regions. Each sub-
problem is pre-assigned to a specific node based on data locality. No runtime redistribution occurs.

Limitations
• Fails when actual task workloads differ significantly from estimates.
• Cannot adapt to runtime events: node failures, unexpected load spikes, variable task lengths.

14.2 Load Balancing / Load Sharing Approach (Dynamic)

Load balancing monitors actual system load at runtime and redistributes processes accordingly.
Tanenbaum identifies four key sub-policies:

Policy Question Answered Example Approach

Transfer Policy When to migrate a process? Threshold-based: migrate if load >

T_high; accept if load < T_low

Selection Policy Which process to migrate? Newly created processes —

lightweight (no execution state to
transfer)

Location Policy Which machine to migrate to? Random probing; polling; central
directory service

Information Policy When to gather load information? Demand-driven; periodic broadcast;

state-change triggered
14.3 Comprehensive Comparison
Aspect Task Assignment (Static) Load Balancing (Dynamic)

Decision Time Before runtime (compile or submit During runtime, continuously

time)

Overhead One-time, low Ongoing monitoring cost

Adaptability Poor — fixed assignment Good — adjusts to actual load

Use Case Predictable, compute-intensive, Interactive, unpredictable, long-

batch jobs running services

Migration None after initial placement Possible — process migration is

core mechanism

Scalability Good — no runtime coordination Harder — distributed consensus

needed needed at scale

Optimality Can be mathematically optimal if Heuristic — exact optimum is NP-

task graph is known hard; use approximations

Fault Handling Poor — does not react to node Good — can redistribute work on
failures failure detection

In Practice: Hybrid Approach

Most modern systems use a hybrid:
- Static initial assignment based on estimated load (task assignment for predictable components)
- Dynamic rebalancing triggered by threshold violations (load balancing for adaptation)
This combines the efficiency of static assignment with the adaptability of dynamic balancing.

Reference: All content sourced directly from Tanenbaum, A.S. & Van Steen, M. (2007). Distributed Systems:
Principles and Paradigms, 2nd Edition. Prentice Hall. Figure numbers and page numbers refer to this edition.