Pioneered by Birrell and Nelson (1984), Remote Procedure Call (RPC) allows programs running on one multicomputer node to invoke subroutines executing on another node transparently. While local function calls pass arguments via CPU registers or stack frames within a shared address space, RPCs must cross an unreliable network where messages can be dropped, delayed, duplicated, or reordered.
1. The 5 Fault Modes of RPC
Failure Mode
Impact
Recovery Strategy
Client Cannot Locate Server
Binding fails; server endpoint down or unregistered.
Return explicit error code or raise language runtime exception.
Lost Request Message
Server never receives the call; client blocks indefinitely.
Client starts a retransmission timer; resends request upon timeout.
Lost Reply Message
Server executed the routine, but client never received result.
Client retransmits. Server must detect duplicates via sequence numbers.
Server Crash After Execution
Server completed call but rebooted before sending reply.
Distinguish between At-Least-Once and At-Most-Once semantics.
Client Crash (Orphan Tasks)
Server continues computing for a client that no longer exists.
Orphan elimination: extermination, reincarnation epochs, or timeouts.
2. Invocation Semantics & Idempotency
At-Least-Once Semantics: The client retransmits requests until an acknowledgment arrives. Guarantees that the procedure executes at least once, but may execute multiple times if replies are dropped. This is safe only for idempotent operations (e.g., reading block 4 of a file, or overwriting a balance with an exact value: X = 500).
At-Most-Once Semantics: The server tracks request sequence IDs and suppresses duplicate executions. Guarantees the routine executes either exactly once or not at all if the server crashes permanently. Required for non-idempotent operations (e.g., transferring funds: balance = balance + 100).
Guided Walkthrough: The Complete RPC LifecycleStage 1 of 5
Concept Overview: This walkthrough visually tracks an RPC invocation of compute_hash(data_block) from the client application stack down to network serialization, across the wire, and through server worker execution.
While multicomputers offer superior physical scalability and lower hardware costs compared to large symmetric multiprocessors, programming them requires message-passing primitives (MPI, sockets) rather than direct variable references. Distributed Shared Memory (DSM) bridges this architectural divide by emulating a single, globally shared virtual address space across independent, physically disjoint multicomputer nodes.
1. Page-Based DSM Emulation (The Kai Li / Ivy Model)
Rather than building specialized hardware, software page-based DSM leverages the CPU's existing Memory Management Unit (MMU) and standard virtual memory page tables:
Read Replication (Shared State): When Node 1 attempts to read address space on a page currently owned exclusively by Node 0, the MMU triggers a page fault. The OS trap routine intercepts this fault, halts the thread, and transmits a network request to Node 0. Node 0 sends a copy of the page over the wire. Both nodes then set their local page table entry to Read-Only. Subsequent concurrent reads on both nodes run at full local memory speed with zero network traffic.
Write Invalidation & Exclusive Ownership: If Node 0 subsequently attempts to write to that replicated page, an MMU write-protection fault occurs. To preserve coherence, Node 0 broadcasts an invalidation message across the network, forcing Node 1 to mark its page table entry as Invalid. Node 0 then upgrades its own mapping to Read/Write, becoming the sole owner of the page.
The False Sharing Pathology: Because virtual memory page sizes are coarse (typically 4 KB or 64 KB), two completely independent threads running on different nodes may write to distinct variables that happen to reside within the same physical page (e.g., Node 0 writes array[0] while Node 1 writes array[100]). The DSM runtime cannot distinguish variable boundaries from page boundaries, causing the entire 4 KB page to bounce furiously between nodes on every write, saturating the network.
2. Memory Consistency Models: From Sequential to Release
Consistency Model
Contract & Synchronization Invariant
Network Overhead
Strict Consistency
Any read to memory location x returns the value stored by the most recent write to x in absolute physical time.
Physically impossible in distributed systems without instantaneous zero-latency communication.
Sequential Consistency
All memory operations appear to execute in some sequential order that is consistent across all nodes, and operations of each individual process appear in program order.
Extremely high. Every write must synchronously invalidate or update all peer copies globally before progressing.
Causal Consistency
Writes that are potentially causally related must be seen by every node in the same order. Concurrent writes may be observed in different orders.
Moderate. Uses vector clocks to track causal dependencies across nodes.
Release Consistency
Ordinary reads and writes are strictly local and batched. Coherence messages are restricted entirely to synchronization boundaries: Acquire() and Release().
Minimal. Eliminates false sharing and ping-pong bouncing by sending compressed diffs only at synchronization points.
The Release Consistency Invariant (Munin / TreadMarks):
Acquire(): Tells the DSM runtime that a critical section is beginning. The local node pulls invalidation notices or updates from the lock's previous owner, refreshing stale pages before user code reads them.
Ordinary Stores: Memory writes inside the critical section modify local memory directly. No network messages are sent during the critical section.
Release(): Tells the DSM runtime that the critical section has ended. The local node computes binary diffs of modified pages and broadcasts them to subsequent acquirers.
Concept Overview: This walkthrough visually tracks how operating systems emulate shared memory across message-passing hardware. Observe how MMU page faults trigger network page transfers, how write faults enforce single-writer ownership via invalidation, and how Release Consistency eliminates network ping-ponging.
Initially, Page P1 resides only on Node 0. Watch Node 1 attempt a read on P1. The MMU generates a page fault, prompting the DSM runtime to fetch P1 across the network and map it as Read-Only on both nodes.
Node 0 Page Rights: Read/Write (Exclusive)
Node 1 Page Rights: Invalid (Fault on Access)
Consistency Policy: Sequential (Strict Faults)
False Sharing Status: None
-- DSM environment initialized. Page P1 is owned exclusively by Node 0. Click button above to step --
In a multicomputer, arrival rates across independent nodes fluctuate over time. Dynamic load balancing transfers runnable tasks from heavily loaded machines to lightly loaded machines to minimize average turnaround time.
Sender-Initiated vs. Receiver-Initiated Probing
Characteristic
Sender-Initiated Probing
Receiver-Initiated Probing
Initiator
Heavily loaded node with excess tasks.
Underloaded or idle node seeking work.
Low System Load
Optimal: Probing node immediately finds an idle target.
Wasteful: Many idle nodes flood network seeking rare busy nodes.
High System Load
Probe Storms: Busy nodes spam probes, finding zero idle targets.
Optimal: Idle node immediately finds a heavily loaded node to offload.
Guided Walkthrough: Dynamic Cluster Load BalancingStage 1 of 3
Concept Overview: This walkthrough models task migration across a 4-node cluster. Observe how burst arrivals create extreme load imbalances, how Sender-Initiated push offloads work, and how Receiver-Initiated work stealing maintains equilibrium under high load.