Distributed Systems in Operating Systems: Worked Examples for GATE and Interviews

Distributed systems become difficult because processes lack shared memory and a common clock, messages may be delayed or duplicated, and one node can fail while others continue. Sockets and RPC move requests between private memories; logical clocks order events without a shared clock; coordination protocols count messages; quorums govern replicated reads and writes; recovery must tolerate partial failure. Distributed Systems in Operating Systems explains the broad relationships among those mechanisms. To turn them into calculations, trace an RPC retry, compute Lamport and vector clocks, count coordination messages, and test quorum overlaps. Check the official syllabus for current GATE coverage, and reason from stated assumptions rather than slogans.

1. What makes a system distributed

A distributed system contains autonomous nodes with private memory and local clocks. They coordinate by sending messages. A multicore machine is different because its processors can use shared memory. In a network operating system, separate machines remain visible; a distributed operating system instead tries to present a single-system image.

Goals include resource sharing, concurrency, scalability, and availability. Transparency can hide resource access, location, replication, migration, or component failure, but no design hides every failure.

Assume N1 is in Delhi, N2 in Mumbai, and N3 in Bengaluru. Measured one-way path delays are 20 ms, 45 ms, and 80 ms. A user opens /notes/os.pdf through one namespace even when N2 is unavailable. These are hypothetical teaching values, not measurements of KnowledgeGate infrastructure.

2. Architectures, RPC, and delivery semantics

Client-server places a service behind clients; multi-tier separates presentation, application, and data. Peer-to-peer nodes act as clients and servers, while a cluster coordinates machines for one service. Synchronous reasoning assumes timing bounds; asynchronous networks have none.

Sockets carry messages; remote procedure call (RPC) adds marshalling, request IDs, replies, and timeouts. Suppose client C sends increment(5) with opId=83 to server S and starts a 200 ms timeout. S commits at 230 ms, so C retries at 200 ms before the first reply arrives. Starting from 40, one application gives 40 + 5 = 45; applying the retry again gives 45 + 5 = 50. With a durable idempotency table keyed by opId=83, S stores and returns 45, then answers the retry with the same result without changing state again.

At-least-once delivery may duplicate requests. At-most-once processing may lose an operation if no retry succeeds. Exactly-once application effects require durable deduplication; networks do not promise literal exactly-once delivery.

3. Worked example: Lamport clocks and vector clocks

Happened-before follows local program order, message send before receive, and transitivity. Drifting physical clocks cannot safely recover causality.

Start every logical clock at zero. The full trace is:

On a receive, Lamport time becomes one more than the larger local or message value. A vector receive takes the component-wise maximum, then increments the receiver's own component. Events a and b are concurrent because [1,0,0] and [0,1,0] are incomparable. Also remember the one-way implication: if x happened before y, then L(x) < L(y). Seeing L(x) < L(y) alone does not prove that x caused y.

4. Coordination, election, and consensus boundaries

A local mutex cannot coordinate separate machines. A central coordinator is simple but creates a dependency. Ricart-Agrawala exchanges timestamped permissions without a central lock manager. A token ring limits entry to the token holder, but lost tokens and failed members require recovery. Revise the shared-memory contrast through Operating Systems process synchronization MCQs.

For N=4, assume one critical-section entry, no failure, and count one-way messages. A central coordinator uses three: request, grant, release. Ricart-Agrawala uses 2(N-1) = 2(4-1) = 6, comprising three requests and three replies. If the requester already holds the ring token, it sends no request broadcast; otherwise it may wait for up to three token hops in a four-node ring.

Leader election chooses a coordinator. Consensus makes nodes agree on one value despite allowed failures. A timeout creates suspicion, not proof of a crash, and any consensus guarantee depends on its timing and failure assumptions.

5. Consistency, replication, failures, and distributed files

Linearizable consistency makes each operation appear atomic and respects real-time order. Sequential consistency preserves a common order but need not match wall-clock order. Eventual consistency allows temporary divergence but expects convergence after updates stop. Consistency differs from availability. Replicas help only when reads, writes, versions, and conflicts follow an explicit rule.

Take replicas A, B, C with N=3, W=2, and R=2. All start at v6. A write of v7 reaches A and B while C is offline, so C remains at v6. A later read from B and C returns v7 and v6; the stored-version rule selects v7. The overlap checks are R+W = 2+2 = 4 > 3 and W+W = 2+2 = 4 > 3. These inequalities are useful conditions, not a complete protocol, and they do not resolve every partition or conflicting write.

For a distributed file, split 12 MiB into three 4 MiB blocks, B1, B2, and B3, then store two replicas per block on different nodes. If N2 fails, a surviving copy keeps affected blocks readable while a worker creates replacements. Heartbeats report liveness, timeouts trigger suspicion, checksums detect corruption, retries repeat attempts, idempotence prevents repeated effects, and re-replication restores the target copy count.

6. Common traps and their corrective tests

• Trap: L(x) < L(y) proves causality. Test: look for a happened-before path; use vector comparability when vectors are available.

• Trap: a timeout proves a crash. Test: delayed messages and partitions can produce the same observation.

• Trap: a duplicate request must change state twice. Test: check the operation ID and stored result.

• Trap: eventual consistency means an immediate latest read. Test: ask when and under what conditions replicas converge.

• Trap: more replicas automatically improve correctness. Test: state the read, write, version, and conflict rules.

• Trap: a semaphore works unchanged across machines. Test: identify the distributed protocol and its failure handling.

• Exam checklist: state N, count one-way messages consistently, and never call a quorum safe without its version and conflict rules.

7. GATE-style questions and technical interviews

Likely tasks include computing clocks, comparing vectors, counting messages, classifying consistency, tracing retries, and reasoning about a failed replica. Check the official syllabus for current coverage of these patterns.

Three quick checks:

1. Ricart-Agrawala at N=5 uses 2(5-1) = 8 messages.

2. With N=5, R=3, and W=3, both R+W = 3+3 = 6 > 5 and W+W = 3+3 = 6 > 5 hold.

3. Vectors [2,1,0] and [1,2,0] are incomparable, so the events are concurrent.

In an interview, return to opId=83. Explain why the 200 ms retry can duplicate the operation, then propose a durable idempotency key and stored result. If S crashes after committing 45 but before replying, the recovered server must still find that record. For broader preparation, use the GATE CS exam preparation category, and confirm any current exam-specific detail on the organising institute's official source.

8. The short version and the next practice step

Remember six moves: model the nodes and failures, define message semantics, establish causal order, choose a coordination rule, name the consistency guarantee, then test retry and partial failure. GATE-focused readers can use GATE Guidance by Sanchit Sir for structured preparation. Placement-focused readers can use CS Fundamentals for Placements by Sanchit Sir, which includes Operating Systems in a placement-oriented course.

Now reproduce the P1-P2-P3 clock table without looking, solve the three quick checks, then attempt about 20 available Distributed Systems practice questions across basics, communication and protocols, and reliability and distributed file systems. Review every error by concept, not answer letter.