SD9.1 · LESSON 1 OF 6

Failure detection

Explain consensus, logical ordering, leases and fencing under stated failure and timing assumptions.

THE IDEA

Failure detection

A distributed system cannot see failures directly; it only sees that something it expected did not arrive. A timeout means a response was not observed within a deadline. It does not prove the other process stopped: it may be paused, slow or cut off, and may act again later. A lease turns this into a time-bounded permission, but the client holding it still believes it is valid until it checks the clock, which a long pause can leave stale.

now (s)14monitor timeout (s)3process paused until (s)15

monitor: 14 − 10 = 4 s since the last heartbeat; timeout 3 → SUSPECTED the process was only paused until 15 s: it is alive and will act again: a false suspicion lease granted at 100, ttl 10: valid at 109 (true), at 110 (false); a paused client still BELIEVES it holds the lease when it wakes

A timeout says only that no response was observed in time. It does not prove the remote process stopped, so it may still act later. Treat suspicion and lease expiry as inputs to a protocol, not as facts.

Move "now" and the end of the process's pause.

Predict first. Can a paused client resume after its lease expired?

Chapter context

Coordination lets multiple processes agree on selected shared decisions even though messages can be delayed or lost and participants can stop. Agreement is achieved by a protocol, not by adding a shared timestamp or an informal majority rule.

TRY IT YOURSELF

Part 1. Do it hands-on

Judge suspicion and lease validity by hand, then write the detector and a safe takeover rule.

now (s)14monitor timeout (s)3process paused until (s)15

suspected at 13? (yes/no) at 14? lease valid at 109? valid at 110? paused client may resume and act? (yes/no)

To do: A process sends a heartbeat every second; the monitor suspects it when more than 3 s pass without one. Last heartbeat at t = 10. At t = 13, suspected? Type yes or no
To do: At t = 14?
To do: A lock lease is granted at t = 100 with a 10 s time-to-live. Is it valid at t = 109? Type yes or no
To do: At t = 110?
To do: Can a paused client resume after its lease expired and still act? Type yes or no

Part 2. Do it in code

suspect(last_heartbeat, now, timeout): True if more than `timeout` has passed since the last heartbeat (strictly greater).
lease_valid(granted_at, now, ttl): True while now < granted_at + ttl.
false_suspicion(last_heartbeat, now, timeout, paused_until): the monitor suspects the process (suspect is True) although the process is merely paused and will resume at paused_until >= now. Return True in that case.
can_still_act(client_believes_valid_until, now, actually_valid): True if the client would still go ahead with an action: it does so whenever its own belief (now < client_believes_valid_until) holds, whatever the lease's real state.
safe_to_take_over(last_heartbeat, now, timeout, lease_granted_at, ttl): a new owner may only take over once the old lease has EXPIRED (not merely when the monitor suspects the old owner).

def suspect(last_heartbeat, now, timeout):
    pass

def lease_valid(granted_at, now, ttl):
    pass

def false_suspicion(last_heartbeat, now, timeout, paused_until):
    pass

def can_still_act(client_believes_valid_until, now, actually_valid):
    pass

def safe_to_take_over(last_heartbeat, now, timeout, lease_granted_at, ttl):
    pass

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

Can a paused client resume after its lease expired?

ANoBYes

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

For a fixed n-member majority group, quorum size is $\lfloor n/2\rfloor+1$ . A 2f+1-member group can lose f members while retaining a majority, provided the remaining participants can communicate and the protocol's other assumptions hold. Fencing requires monotonically ordered tokens and enforcement at the resource.

Worked example

Five members require three votes, allowing two unavailable members while a communicating majority remains. Separately, a resource has already accepted token 8 from a new owner. An old owner's delayed operation bearing token 7 must be rejected, regardless of whether the old process still believes it owns the lease.

Reference code

The following example uses the Python standard library and does not call a remote service.

members=5
quorum=members//2+1
assert quorum == 3 and members-quorum == 2
highest=8
def accept(token):
    global highest
    if token < highest: return False
    highest=token
    return True
assert not accept(7)
assert accept(8)
assert accept(9)

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

A timeout cannot establish a remote process's state. Quorums require full protocol rules. Fencing is ineffective if the resource accepts stale tokens or an attacker can invent authorized tokens.