Distributed Algorithms | Semester 8 BTech CSE Core Notes
Semester 8 - Page 1: Distributed Algorithms. 25 numbered topics, highlighted rules, worked cases, answered exam questions, diagrams, comparison tables and three complete Python demos. General common-core guide, not an official syllabus. Confirm exact protocol variants and required proofs with your course outline.
Topic map
- Distributed model and local knowledge
- Synchrony, asynchrony and partial synchrony
- Failure models and channels
- Safety, liveness and invariants
- Happened-before and causal relation
- Lamport scalar clocks
- Vector clocks and concurrency
- Physical clocks and synchronization limits
- Consistent cuts and global snapshots
- FIFO, causal and total-order broadcast
- Leader election goals and assumptions
- Ring-election teaching trace
- Bully election and timeout caveats
- Centralized mutual exclusion
- Permission-based and token mutual exclusion
- Deadlock and distributed waits
- Consensus agreement, validity and termination
- FLP impossibility and its scope
- Quorums and intersection
- Raft terms, leaders and replicated logs
- Consistency and operation histories
- Network partitions and availability tradeoffs
- Retries, idempotence and durable recovery
- Simulation, testing and failure injection
- Exam synthesis and protocol checklist
1. Distributed model and local knowledge
Distributed processes coordinate through messages under stated channel, timing, identity and fault assumptions. No process automatically sees one perfect global state.
Answer: No. Message delay and failures limit knowledge.
2. Synchrony, asynchrony and partial synchrony
Synchronous models assume known timing bounds; asynchronous models do not. Partial synchrony introduces bounds that hold under stated conditions without assuming perfect timing always.
Answer: No. Its interpretation depends on assumptions.
3. Failure models and channels
Crash-stop, crash-recovery, omission and Byzantine faults differ. State durable state, message reliability/order and identity/authentication assumptions.
Answer: No. The fault model changes the requirements.
4. Safety, liveness and invariants
Safety excludes bad states; liveness promises eventual progress under assumptions. An invariant should hold across every modeled transition.
Answer: No. A safe system may stop making progress.
5. Happened-before and causal relation
Happened-before includes local process order, send-before-corresponding-receive and transitivity. Events with neither causal direction are concurrent.
Answer: No. Timestamps are not causal evidence by themselves.
6. Lamport scalar clocks
Increment for each event; receive updates to max(local, received)+1. Happened-before implies increasing Lamport values, but increasing values do not prove happened-before.
Answer: No. The implication is only the other direction.
P1: local1 -> send2
| message m1
P2: receive3 -> local4 -> send5
| m2
P3: receive6Fixed Lamport send/receive trace
clock = {"P1":0,"P2":0,"P3":0}
def local(process):
clock[process] += 1
return clock[process]
def receive(process, stamp):
clock[process] = max(clock[process], stamp)+1
return clock[process]
trace = [local("P1")]
m1 = local("P1"); trace.append(m1)
trace.append(receive("P2", m1))
trace.append(local("P2"))
m2 = local("P2"); trace.append(m2)
trace.append(receive("P3", m2))
assert trace == [1,2,3,4,5,6]
print("fixed causal trace:", trace)
print("receive stamp5/local9:", max(9,5)+1)
print("Finite trace only; a smaller scalar clock does not establish causality.")
Checked output:
fixed causal trace: [1, 2, 3, 4, 5, 6] receive stamp5/local9: 10 Finite trace only; a smaller scalar clock does not establish causality.
7. Vector clocks and concurrency
Under the stated fixed-process vector model, increment own component and merge componentwise maxima on receive before incrementing. Component comparison records causal knowledge.
Answer: No. They grow with modeled process identities and assumptions.
Vector comparison and one merge under a fixed process model
def before(a,b):
return all(x<=y for x,y in zip(a,b)) and any(x<y for x,y in zip(a,b))
a,b = [1,0,0],[0,1,0]
send = [2,0,0]
received = [max(x,y) for x,y in zip(send,b)]
received[1] += 1
assert not before(a,b) and not before(b,a)
assert received == [2,2,0] and before(send,received)
print("independent a/b concurrent:", not before(a,b) and not before(b,a))
print("receive vector:", received)
print("send before receive:", before(send,received))
print("Fixed equal-length vectors; no dynamic-membership or network protocol implementation.")
Checked output:
independent a/b concurrent: True receive vector: [2, 2, 0] send before receive: True Fixed equal-length vectors; no dynamic-membership or network protocol implementation.
8. Physical clocks and synchronization limits
Physical-clock synchronization has uncertainty and drift; timestamps need bound/context before driving ordering guarantees. Logical clocks solve a different task.
Answer: No. Clock accuracy and causal order differ.
9. Consistent cuts and global snapshots
A consistent cut cannot include receipt of a message while excluding its send. Snapshot algorithms need channel/process assumptions and in-transit-message handling.
Answer: No. The combined cut can violate causality.
10. FIFO, causal and total-order broadcast
FIFO preserves one sender's order; causal order preserves causal dependencies; total order agrees on delivery sequence under its defined guarantees..
Answer: No. Communication, membership and failure handling are needed.
11. Leader election goals and assumptions
Election chooses a coordinator under a membership/identity/failure model. Unique leader safety and eventual leader progress need separate reasoning.
Answer: No. Nodes must coordinate and handle failures/messages.
Election: choose coordinator Mutual exclusion: at most one entrant Consensus: agree on valid value Each needs its own model and protocol.
12. Ring-election teaching trace
A directed reliable ring with unique participating IDs can forward higher candidates and discard lower ones under a specified max-ID variant. Precise message cost depends on the algorithm.
Answer: No. Specify the actual algorithm and assumptions.
13. Bully election and timeout caveats
A bully-style election uses higher-ID requests/replies and timeout assumptions to favor the highest live eligible process. Delays/recovery require careful handling.
Answer: No. Failure suspicion can be wrong.
14. Centralized mutual exclusion
A lock coordinator can serialize grants but introduces availability/recovery concerns. Requests, releases and duplicate handling must be defined.
Answer: No. It relocates coordination and recovery concerns.
15. Permission-based and token mutual exclusion
Permission protocols collect ordered approvals; token protocols rely on controlled token ownership. Message loss, duplicate tokens and membership changes affect guarantees.
Answer: No. A delayed existing token could create duplicates.
16. Deadlock and distributed waits
A wait-for cycle may indicate deadlock under the modeled resource/request assumptions. Delayed observations can produce stale or phantom conclusions.
Answer: No. Verify the model and current state.
17. Consensus agreement, validity and termination
Consensus requires agreement, suitable validity and termination under a named model. A one-round majority preference count is not a complete consensus protocol.
Answer: No. They solve different coordination tasks.
18. FLP impossibility and its scope
In a fully asynchronous message-passing model with even one possible crash, deterministic consensus cannot guarantee termination in all executions. This does not say no practical system can ever decide.
Answer: No. Its assumptions and guaranteed-termination scope matter.
19. Quorums and intersection
Majority quorums intersect in a fixed membership, supporting particular coordination proofs. Intersection alone does not implement consensus or every consistency property.
Answer: No. Protocol rules, durable state and membership matter.
All majority quorum pairs in five-node fixed membership
from itertools import combinations
nodes = range(5)
quorums = [set(q) for q in combinations(nodes,3)]
pairs = list(combinations(quorums,2))
assert all(a & b for a,b in pairs)
print("three-node quorums:", len(quorums))
print("distinct pairs checked:", len(pairs))
print("minimum intersection:", min(len(a&b) for a,b in pairs))
print("Set intersection check only, not a consensus/Raft implementation or liveness proof.")
Checked output:
three-node quorums: 10 distinct pairs checked: 45 minimum intersection: 1 Set intersection check only, not a consensus/Raft implementation or liveness proof.
20. Raft terms, leaders and replicated logs
Raft separates leader election, log replication and safety with terms and durable state rules. Study actual election/commit restrictions, not only majority counting.
Answer: No. It verifies only set arithmetic.
21. Consistency and operation histories
Linearizability respects a single-operation order consistent with real-time precedence; eventual convergence is a different guarantee. State the actual operation/model.
Answer: No. Its convergence assumptions and timing differ.
22. Network partitions and availability tradeoffs
Partition-tolerance discussions concern lost/delayed communication. CAP-style availability and consistency have formal scopes, not generic marketing meanings.
Answer: No. The partition scenario and definitions matter.
23. Retries, idempotence and durable recovery
An uncertain response does not prove an operation failed. Stable request IDs and durable deduplication/reconciliation can prevent repeated effects under scoped assumptions.
Answer: No. Reconcile outcome and apply an idempotency policy.
Request -> possible effect -> response lost
-> authoritative reconciliation
-> scoped duplicate/idempotency rule24. Simulation, testing and failure injection
A local trace can verify a rule, not real network fault tolerance. Test permitted runtime failures and invariants with reproducible schedules/limitations.
Answer: No. Invariants/model reasoning and broader tests are needed.
25. Exam synthesis and protocol checklist
For each algorithm state nodes/channels/faults/timing, transition rules, invariant, progress assumptions and complexity for that variant. Keep selection/counting separate from live protocol evidence.
Answer: A precise model, correct trace, safety/liveness distinction and explicit limits.
Timing and fault assumptions
| Model | Important distinction |
|---|---|
| Synchronous | Known bounds support timeout reasoning |
| Asynchronous | Unbounded delay prevents perfect crash inference |
| Crash-stop/recovery | Recovery and durable state differ |
| Byzantine | Arbitrary/inconsistent behavior, not only crashes |
| Fixed/dynamic membership | Quorum/identity assumptions change |
Order and coordination
| Concept | Claim | Limit |
|---|---|---|
| Lamport clock | Causality implies increasing scalar | Reverse implication false |
| Vector clock | Component comparison under model | Metadata/membership assumptions |
| FIFO | Per-sender order | Not all causal/total order |
| Quorum intersection | Any two strict majorities overlap | Not a protocol by itself |
| Raft | Named replicated-log protocol | Precise durable/election/commit rules needed |
Safety versus progress
| Task | Safety example | Progress caveat |
|---|---|---|
| Mutual exclusion | At most one entrant | Token/coordinator/permission recovery |
| Election | No conflicting eligible leader under specification | Timing/membership/fault assumptions |
| Consensus | Agreement and suitable validity | FLP scope or added assumptions |
| Retries | Avoid repeated unwanted effects | Unknown outcomes require reconciliation |
Revision checklist
Write model, faults, channel order and timing first. Trace scalar/vector rules exactly. Distinguish election, mutual exclusion and consensus; state FLP scope and quorum limits. Do not mistake a local sort/count/simulation for a fault-tolerant distributed protocol.
Resources and sources
Original hub link is preserved. Primary protocol and university sources support causal clocks, impossibility scope and actual consensus study.
Comments
Post a Comment