Membership & Failure Detection

A missing heartbeat is an observation about communication. It does not reveal whether a remote process crashed, paused, or became unreachable. The three tasks separate version reconciliation, suspicion scoring, and membership transitions. Start by comparing integer tuples and tracing a state machine in input order.

Reconcile freshness before making decisions

GossipDigestDelta compares (Incarnation, Heartbeat) lexicographically. Incarnation identifies a newer lifetime; heartbeat orders updates within it.

Member	Local candidates	Remote	Delta
a	(4,99), then (5,1)	(4,200)	send a
b	(2,8), then (2,3)	(2,9)	request b
c	absent	(1,0)	request c

Deduplicate by maximum freshness, not last input position. The later (2,3) for b cannot erase (2,8). Output is send=[a], request=[b,c], sorted for repeatability. A send/request list says which update is missing; it is not a vote that a node is dead. The exercise's absent version is (-1,-1).

Derive the suspicion score

The exercise chooses an exponential waiting-time model. If positive heartbeat intervals have mean mu, its survival probability is exp(-elapsed/mu). Taking -log10 gives phi = elapsed / (mu * ln(10)). This is one model for a score, not a universal formula for every phi-accrual detector and not a measured probability that the process has crashed.

For timestamps [100,200,200,150,350], retain positive differences between adjacent input entries, without sorting:

Adjacent pair	Gap	Keep?
100 to 200	100	yes
200 to 200	0	no
200 to 150	-50	no
150 to 350	200	yes

Samples=2, mean=150, last accepted endpoint=350. At now=650, elapsed=300 and phi=2/ln(10), about 0.869. Threshold 1 does not suspect; threshold 0.8 does. With minSamples=3, keep the mean but return phi=0 and Suspect=false. Sorting first would produce a different estimator and violate the contract. The last accepted endpoint is the end of the last positive adjacent interval in input order, not necessarily the greatest timestamp.

Compare timestamps before subtracting at integer extremes. A positive mathematical int64 difference may require uint64; accumulate converted gaps in floating point so their sum cannot overflow int64. Preserve a one-unit gap even near MaxInt64 by subtracting integers before converting to float64. Clamp negative elapsed to zero. No samples means no evidence for suspicion.

Trace the course membership machine

SwimSuspectRound is a deterministic SWIM-inspired quorum simulator. Real SWIM separates probing from dissemination and uses suspicion timeouts and incarnation refutation; this task does not implement that full protocol. Its equal-incarnation alive reset and explicit reporter thresholds are course rules.

Start n alive at incarnation 5, counters zero, suspectQuorum=2, deadQuorum=2:

Report	State after	Suspect votes	Confirm votes	Reason
a suspects 5	alive	1	0	first suspect reporter
a suspects 5	alive	1	0	duplicate
b suspects 5	suspect	2	0	threshold reached
a confirms 5	suspect	2	1	separate confirm history
a confirms 5	suspect	2	1	duplicate confirm
c confirms 5	dead	2	2	confirmation threshold
alive 5	dead	2	2	same incarnation cannot revive dead
alive 6	alive	0	0	adopt new incarnation, clear histories
b suspects 5	alive	0	0	stale incarnation

Reporter sets are separate by phase: a may count once as suspect reporter and once as confirm reporter. A confirm arriving while alive is ignored, not saved for later. A suspect arriving while suspect or dead is ignored. Preserve the input member ordering in the result; unknown targets and kinds do nothing.

Resetting evidence changes future behavior

In this simulator, an equal-incarnation alive report resets a non-dead member, including counters and both reporter sets. Thus a reporter can count again after reset. A higher-incarnation alive can also revive dead members. Merely setting State="alive" while leaving the sets populated loses future evidence.

Initial vote counters are accepted as summary state, but reporter identities are not passed into this API. Deduplication covers reports within this call since the last reset. To implement a multi-round service, extend the persisted state to include reporter history or use a different protocol; repeatedly calling this stateless planner cannot deduplicate reporters across calls.

Predict before implementing

Restart the trace at alive/5, zero votes. Process: a-suspect/5, alive/5, a-suspect/5, b-suspect/5, c-confirm/4. Predict state and counters.

Check the transition trace

Alive/5 resets the first vote and its reporter history. The later a and b reports reach suspect with SuspectVotes=2. The incarnation-4 confirmation is ignored, so ConfirmVotes=0. Failing to clear history would incorrectly keep the member alive with only one counted vote.

Implement digest sync, then phi, then transitions. Independently explain how a long process pause can make all three computations internally correct while the external conclusion "the node crashed" is false. Membership suspicion must feed a recovery policy; it must not silently rewrite a consensus quorum.