Part 6 of 14
Liveness, timing and status
An application needs to know more than which samples arrived. It needs to know whether the writer it depends on has gone quiet, whether it is falling behind, how many samples it has lost, and which of several writers it should believe.
None of that can use a timer per endpoint. A participant with a thousand endpoints would then own a thousand timers, and the answers would depend on when each fired. So everything here is computed from a stored instant at the moment somebody asks, and the arithmetic is arranged so that asking twice gives the same answer as asking once.
Pattern
Reporting a count that changes
an application polls any of the statuses on this page
Once per poll, at the application's own pace.
Five of the algorithms below share one shape, so it is worth doing once. Each reports two things: a total since the endpoint was created, and how much that total has moved since the application last looked.
The obvious implementation — keep a delta and zero it when read — makes reading destructive. Two parts of an application that both poll then each see a fraction of what happened, and neither can tell.
Instead the total is never reset, and a separate cursor records what the previous poll returned. The change is the difference between them.
Observe(e, now)
e the endpoint, holding a cumulative total and the total the last poll returned · now the current monotonic time
- t = Derive-Total(e, now) // computed, not accumulated by a timer
- change = t − e.reported
- e.reported = t // only the cursor moves
- return (t, change)
Line 1 derives the total rather than reading one that something else has been incrementing. For the time-based statuses that means dividing elapsed time by a period — no work happens between polls, and a period that passes while nobody is looking is still counted.
Line 3 is the only mutation. The total is untouched, so a poll cannot lose information for another caller, and the cumulative figure stays meaningful as an absolute measure.
Why the clock has to be monotonic
Every derivation here measures elapsed time from a stored instant. A clock that can be adjusted backwards would make that elapsed time negative, and a clock adjusted forwards would manufacture missed periods that never happened. The instants come from a clock that only moves forwards, so an administrator correcting the wall clock cannot create or erase a missed deadline.
Rate
Rate-limiting a reader
a sample reaches a reader that asked for a minimum interval
Once per sample per such reader.
A reader can ask not to be given samples faster than some interval — it wants a position every 100 milliseconds even if the writer publishes every millisecond. The interval applies separately to each instance, so a stream of updates about one robot must not suppress updates about another.
When storage fails after the test has passed
The state needed is one timestamp per instance: when its last accepted sample arrived. The subtlety is when to update it. Deciding to accept a sample and then failing to store it — the history is full, the shared memory queue is full — would leave the timestamp advanced for a sample that nobody will ever see, and the next sample would be rejected for being too close to one that does not exist.
So the decision and the state change are separated. The test returns a token naming the slot it would update and the value it would write, and the token is only redeemed once the sample is safely stored.
Rate-Test(reader, sample)
reader holding the requested interval and one timestamp per instance · sample the arriving sample and its reception time
- if sample is a lifecycle notice or reader.separation == 0
- return untracked // nothing to rate limit
- if sample.received == nil
- return untracked
- i = Find-Instance(reader, sample.key)
- if i ≠ nil
- if sample.received < i.last
- return rejected // arrived out of order
- if sample.received − i.last < reader.separation
- return rejected
- return token(i, sample.received)
- if reader.instances is full or reader.keys is full
- return rejected // neither collection was changed
- return token(new, sample.key, sample.received)
Rate-Commit(reader, token)
token the value returned by Rate-Test, naming the slot to update and the value to write
- if token == untracked
- return
- if token names a new instance
- i = Insert-Instance(reader, token.key)
- else
- i = token.instance
- i.last = token.received
Worked example
A reader asks for 100 ms between samples. Two robots publish on the same topic, so there are two instances.
| Arrives | Instance | Result |
|---|---|---|
| 0 ms | robot A | accepted — first sample for A |
| 10 ms | robot B | accepted — first for B, and A does not suppress it |
| 40 ms | robot A | rejected — 40 ms since A's last |
| 120 ms | robot A | accepted — 120 ms since A's last, which is still the one at 0 ms |
| 150 ms | robot B | accepted — 140 ms since B's last |
The fourth row is measured from 0 ms, not from the rejected sample at 40 ms. A rejected sample never reaches Rate-Commit, so it leaves no trace to measure from — if it did, a fast publisher would keep pushing the frontier forward and the reader would receive nothing at all.
Line 12 of the test checks that a new instance would fit before returning a token, so a reader that has reached its instance limit rejects the sample without having half-inserted a key.
Cost
Instances are held in a flat table with the key bytes in one preallocated arena, so a keyed lookup is O(I · K) for I instances and key length K. That is a deliberate trade: a hash table would look up faster but would allocate a node per key, and both I and K are fixed when the reader is created. Committing is O(1), plus a K-byte copy the first time a key is seen.
Expiry
Expiring a sample by lifespan
the application reads or takes, and a lifespan is in force
Once per sample examined during the call — not on arrival, because a sample expires while it waits.
A sample can be given a lifespan: after that long, it is no longer worth having. A position from four seconds ago is not a useful position. The sample was valid when it was queued and is stale by the time anybody looks at it, so expiry cannot be decided on arrival.
Both sides can state a lifespan, and the shorter one wins. Only if both say unlimited is expiry switched off.
Effective-Lifespan(requested, offered)
requested the reader's lifespan · offered the writer's; either may be unlimited
- if requested == unlimited and offered == unlimited
- return none
- return min(requested, offered)
Expired(s, now)
s a queued sample with the lifespan captured beside it · now the observation time, read once for the whole call
- if s.lifespan == none
- return false
- base = s.source-time
- if base == nil
- base = s.reception-time
- if base == nil
- return false // no baseline is not the same as expired
- if now < base
- return false // the clock moved backwards
- return now − base ≥ s.lifespan
No timestamp, or a clock that moved backwards
Lines 6 to 9 are both refusals to guess. A sample with no timestamp to measure from has no age, and a clock reading earlier than the sample's own baseline would produce a negative age; neither is evidence that the sample is stale, so neither is treated as expiry.
Where reading and taking differ
Reading and taking differ in what they do about an expired sample. Reading leaves the history alone, so it steps over expired samples and returns the first live match. Taking removes what it returns, so it removes the expired ones it walked past as well — leaving them would mean walking them again on every subsequent call, forever.
Take(reader, now, selector)
selector what the caller asked for — a particular instance, or a correlation with an earlier request
- while reader.history is not empty
- s = Next-Match(reader.history, selector)
- if s == nil
- return nil
- Remove(reader.history, s)
- if not Expired(s, now)
- return s
- // expired: release its shared-memory reference and keep going
- return nil
The observation time is read once, before the loop, and the same value is used for every sample examined. Reading the clock per sample would let a batch return samples judged against different moments, so two samples could be returned in an order that contradicts their ages.
The lifespan in force is also copied next to the sample when it is queued, rather than looked up when it is read. A writer can disappear between those two moments, and its samples should not change their meaning when it does.
Timing
Counting missed deadlines
a sample is successfully published or admitted, and when the status is polled
Once per successful sample, plus once per poll.
An endpoint can state that a sample is expected at least every P — a writer promising to publish that often, a reader expecting to receive that often. Every complete period that passes with no qualifying activity is a miss, and the application wants to know how many.
Rather than a timer that fires each period, the endpoint stores when activity last happened and counts the complete periods since.
Total-Missed(e, now)
e the endpoint, holding period P, the instant of last activity, and the misses already folded in · now the current monotonic time
- if e.period == 0 or now ≤ e.since
- return e.folded // no complete period has elapsed
- return e.folded + ⌊(now − e.since) / e.period⌋
On-Activity(e, now)
e the endpoint · now the instant of the successful publication or admission
- e.folded = Total-Missed(e, now) // bank what elapsed first
- e.since = now // then restart the clock from here
The order in the second procedure is the whole algorithm. Moving the instant before banking the elapsed periods erases them — a writer that misses four deadlines and then publishes would report none. Banking first means activity restarts the count without forgiving what already happened.
What counts as activity for a reader
A sample arriving is not enough. A sample that was filtered out, was suppressed by the rate limit, had expired, was refused by a full history, or belongs to a group that is not yet complete has not been delivered to the application — and the deadline is a promise to the application. So only a sample that actually enters visible history resets it.
This is the one place on this page where getting the condition wrong is invisible in testing: a reader whose filter rejects almost everything would report no missed deadlines at all while delivering nothing.
Cost
Four scalars per endpoint that declared a finite period. Every operation is one integer division and a comparison. No timer, no worker, no allocation. An endpoint with no finite period stores nothing and costs one branch where activity would have been recorded.
Liveness
A writer's liveliness lease
a writer publishes or asserts itself, and when the status is polled
Once per publication, plus once per poll.
A writer can promise to show it is alive at least every L, either by publishing or by saying so explicitly. If it does neither, the promise lapses.
The distinction from a deadline matters. A deadline counts every period that passes without activity, so a writer silent for ten periods has missed ten. A lease lapses once: a writer that has stopped is not more stopped ten periods later. Polling repeatedly while it stays dead must not keep counting.
Apply-Expiry(l, now)
l the lease — duration, instant of last activity, an alive flag, and cumulative losses · now the current monotonic time
- if not l.alive
- return // already lapsed; do not count it again
- if l.duration == 0 or now < l.since
- return
- if now − l.since < l.duration
- return // still within the promise
- l.alive = false
- l.losses = l.losses + 1 // exactly once per lapse
On-Assert(l, now)
l the lease · now the instant of the publication or explicit assertion
- Apply-Expiry(l, now) // a lapse that already happened still counts
- l.alive = true
- l.since = now
Lines 1 and 2 of the first procedure are what makes polling non-destructive: the alive flag records that this lapse has been counted, so a thousand polls of a dead writer report one loss.
Line 1 of the second is the counterpart. A writer that goes quiet past its lease and then publishes again has genuinely lapsed, and the application needs to know — it may have acted on the assumption that nobody was driving. Reviving without first applying expiry would hide the gap completely.
Liveness
Liveliness across many writers
a writer matches or unmatches, a sample enters history, or the status is polled
Once per admitted sample for its own writer; a full walk only on poll.
A reader matched to many writers reports how many are currently alive and how many are not, plus how those two numbers have moved. Each writer's lease runs independently, on the duration that writer offered.
Two events look similar and must not be conflated. A writer whose lease lapses is a writer that failed its promise, and that is a loss the application should see. A writer that leaves the system through discovery did not fail — it shut down, or its participant went away. Counting the second as a lease loss reports a fault where there was an orderly exit.
Reconcile(r, matched)
r the reader's sorted array of peer entries · matched the writers discovery currently reports as matched
- for each peer p in r.peers
- p.mark = false
- for each writer w in matched
- i = Binary-Search(r.peers, w.guid)
- if i ≠ nil
- r.peers[i].lease-duration = w.offered
- r.peers[i].mark = true
- else
- Insert-At(r.peers, w, marked) // keeps the array sorted
- for each peer p in r.peers
- if not p.mark
- Remove(r.peers, p) // gone from discovery, not a lease loss
The mark-and-sweep on lines 1, 7 and 11 is how a departure is recognised without discovery having to notify this code. Anything not seen during the walk is no longer matched, and it simply leaves — reducing the current count without touching the loss count.
The array is kept sorted by writer identifier so line 4 is a binary search. That matters because this walk happens on every poll: an application polling at video rate against a hundred writers would otherwise do ten thousand comparisons per second for an answer that rarely changes.
Observe-Liveliness(r, now)
r the reader with its reconciled peers and the two counts the last poll returned · now the current monotonic time
- alive = 0; dead = 0
- for each peer p in r.peers
- if p.lease-duration == infinite
- alive = alive + 1 // no promise to break
- else
- Apply-Expiry(p.lease, now)
- if p.lease.alive then alive = alive + 1 else dead = dead + 1
- change = (alive − r.reported-alive, dead − r.reported-dead)
- r.reported-alive = alive; r.reported-dead = dead
- return (alive, dead, change)
A sample refreshes only its own writer's lease, and only once it has entered visible history — the same condition as the deadline. A sample that was filtered out proves the writer is alive, but the reader is reporting on what the application can see, and the two must not disagree.
Cost
The peer array is sized when the reader is created, so a writer that would exceed it is refused rather than growing the array. Refreshing one writer is a binary search, O(log P). Reconciling and polling walk all P peers. Nothing allocates after registration.
Status
Counting matched endpoints
an application polls how many compatible peers an endpoint has
Once per poll. Publication and delivery do no match-status work at all.
An endpoint reports how many compatible peers it currently has, the signed change since the last poll, and a cumulative count of transitions — which counts both arrivals and departures, so a peer that comes and goes contributes two.
The count is derived by walking the match lists Part 1 already maintains, not by keeping a separate counter that publication would have to update. That keeps the cost entirely on the polling side.
Observe-Matches(e)
e the endpoint, holding the count the last changed poll reported and a cumulative transition total
- c = Count(e.local-matches) + Count(e.remote-matches)
- if c == e.reported
- return none // an unchanged graph is silent
- delta = c − e.reported
- e.transitions = e.transitions + |delta|
- e.reported = c
- return (c, e.transitions, delta)
Line 3 returns nothing rather than a status with a zero change. An application that installs a callback for this wants to be woken when something happened, and a poll that reports "nothing happened" through the same path as "something happened" makes every listener check.
Line 5 adds the absolute value. Two writers arriving and two leaving between polls nets to zero, and the current count is right — but four transitions occurred, and the cumulative figure exists precisely to show the churn that the net figure hides.
Reporting why a peer did not match
The counterpart question is which policy prevented a match. Answering it means scanning the opposite-role endpoints, skipping any on a different topic or type — those are unrelated, not incompatible — and for each remaining one applying the policies in a fixed order and reporting the first that fails.
The order has to be fixed for the answer to be stable, and the endpoints have to be scanned in a fixed order for the last reported policy to mean anything. Since the tables behind them are hashed, a separate index preserves the discovery order for exactly this purpose.
Cost
A poll is O(L + R) over the local and remote match lists, with constant extra storage and no copying of endpoint records. The incompatibility query is O(E + R) and yields each reason from the discovery iterator rather than collecting them.
Status
Lost and rejected samples
a sample is admitted to reader history, and when either status is polled
Once per admitted sample.
Part 13 covers what a full history does. What the application sees of it is two separate numbers, and the distinction between them is the useful part.
A sample displaced because the reader asked to keep only the newest is lost. A sample refused because the reader asked to keep everything and everything is full is lost and rejected. Both mean data did not reach the application; only the second means the reader is not keeping up with a promise it made.
Worked example
| Admission result | lost | rejected | available |
|---|---|---|---|
| Stored — there was room | — | — | +1 |
| Replaced — keep-last displaced an older one | +1 | — | +1 |
| Rejected — keep-all was full | +1 | +1 | — |
| Withheld — in a group not yet released | — | — | — |
The second row is the one that reads oddly and is right: a sample was successfully stored and a sample was lost, because storing it is what pushed the other one out. The third row increments both counters for one event, which is why they are separate counters rather than one with a reason attached.
The fourth row is a sample that has arrived and is being held because its group is incomplete. Nothing has been lost and nothing is yet available; it will move to one of the first two rows when the group is released.
Each of the three counters carries its own cursor, so polling one does not consume the change reported by another. An application that watches only rejections still sees the full history of losses when it later asks.
Arbitration
One writer per instance
a writer matches an exclusive reader, or a sample arrives for one
Once per sample for a reader that asked for exclusive ownership.
A reader may be matched to several writers on one topic — a primary and a standby, or two sensors covering the same area. It can ask that only one of them be believed at a time, so it never sees two answers to the same question interleaved.
Which one is decided by a strength each writer declares. Strength alone is not enough to decide, because two writers can declare the same one and the reader must still pick deterministically — and both ends of the system must pick the same one. So ties break on the writer's identifier, which is unique and which both sides already have.
Stronger(a, b)
a, b two matched writers, each with a declared strength and an identifier
- if a.strength ≠ b.strength
- return a.strength > b.strength
- return a.guid < b.guid // deterministic, and the same on both sides
Admit-Exclusive(r, sample)
r the reader and its selected owner, per instance for a keyed type · sample the arriving sample, its writer, and its instance key
- if r.ownership == shared
- return admit // no state is reserved or changed
- owner = Selected-For(r, sample.key)
- if owner == nil or Stronger(sample.writer, owner)
- Set-Selected(r, sample.key, sample.writer)
- return admit
- if sample.writer == owner
- return admit
- return withhold // a weaker writer, for this key only
Line 3 looks the owner up per key. A keyed topic carrying ten robots has ten independent decisions, and a strong writer for one robot must not take ownership of the other nine — it may not even publish about them.
Line 4 lets a stronger writer take over immediately, on the sample that proves it exists, rather than waiting for the current owner to fail. That is what makes a standby promotion take effect at the first sample rather than after a lease has lapsed.
Cost
A shared reader takes the first branch and pays one comparison. An exclusive reader pays one lookup per sample and stores one selection per key, within the instance limit from Part 13.
Next: shared-memory transport
On one machine the payload need not be copied, which means processes writing one structure with no lock.
These descriptions follow the implementations in Tin DDS and Retina. Evaluation access and the full algorithm notes are available from engineering@tinverse.com.