Part 1 of 14
Discovery and matching
Two programs start up on a network knowing nothing about each other. Before a single sample can move, they have to announce themselves, keep what they hear without running out of memory, and work out which of their writers should be sending to which of the other's readers.
Matching is the expensive one. Every time an endpoint appears it has to be compared against everything already known, and a single comparison is not cheap, so most of the design goes into doing fewer of them.
Matching
Matching a new endpoint
an endpoint is created locally, or one is announced by a peer
Once per endpoint that appears. Control plane — never on the path that publishes a sample.
A participant holds a set of endpoints — the writers and readers it knows about, both its own and those it has heard announced. When a new writer appears, it must be paired with every reader it is compatible with.
Two endpoints are compatible only if they name the same topic, agree on the type, and have quality-of-service settings that fit together. A reader asking for reliable delivery cannot be paired with a writer that only offers best-effort. Checking that last part is the expensive step, because it compares a dozen separate policies, and partitions are compared with wildcard patterns.
The obvious approach is to compare the new writer against every known endpoint. That is correct but wasteful: nearly all of those endpoints are on some other topic, and the policy comparison runs anyway before the topic mismatch is noticed.
So the endpoints are kept in an array — which keeps iteration order the same on every machine and keeps storage compact — and hash tables are kept beside the array rather than replacing it. One maps an endpoint identifier to its position, one maps its GUID to its position, one maps a participant's GUID prefix to its position. A hash set records which pairs are already matched, so a pair is never matched twice. Two more tables record the matches themselves in both directions: the readers of a writer, and the writers of a reader.
An endpoint that contradicts itself
One cheap test runs before any of this. An endpoint whose own settings contradict each other — a history depth larger than the resource limit it also declares — can never match anything, so it is rejected on the spot and never enters the scan at all.
Match-Writer(G, w)
G the discovery graph — the endpoint array and the hash tables beside it · w the writer being added
- if not Consistent(w)
- return error // depth contradicts resource limits
- Index-Insert(G, w) // append to array, add to the three hash tables
- for each endpoint r in G.endpoints
- if r.kind == reader and r.topic == w.topic and r.type == w.type
- if r.hash ≠ 0 and r.hash == w.hash
- if (w.id, r.id) not in G.matched
- if Qos-Compatible(w, r)
- Insert(G.matched, (w.id, r.id))
- Append(G.readers-of[w.id], r.id)
- Append(G.writers-of[r.id], w.id)
Line 3 comes before the loop, so the writer is in the index by the time anything looks for it. Line 7 is what keeps a pair from being matched twice when the same announcement arrives again, which on a lossy network it usually does. Lines 10 and 11 record the match in both directions, so that sending to a writer's readers, or asking a reader for its writers, is a single lookup later on rather than a search.
Cost
Inserting one endpoint is O(E) in the number of endpoints, and the quality-of-service comparison runs only on the pairs that share a topic and type. Removal is the expensive direction: taking an endpoint out of the array moves the ones after it, which invalidates every stored position, so the indexes are rebuilt — O(E + M) for M existing matches. When a remote participant goes silent, all of its endpoints go at once: the expired prefixes go into a hash set first, and one pass over the array removes them together rather than paying the rebuild once per endpoint.
Matching
Comparing partitions
a candidate pair has already been found to share a topic and type
Once per candidate pair, inside the matching scan above.
Partitions are a way of splitting one topic into separate namespaces:
endpoints match only if their partition lists overlap. Each side holds a
list of names, and a name may be a pattern containing
* or ?. An overlap anywhere is enough.
An endpoint that names no partition is not unrestricted — it is in the default partition, written as the empty name, and it matches the other side only if the other side is also in the default partition or has a pattern that covers it.
Partitions-Match(P, Q)
P, Q the two endpoints' partition-name lists, either of which may hold patterns
- if P is empty
- P = ⟨""⟩ // the default partition
- if Q is empty
- Q = ⟨""⟩
- for each p in P
- for each q in Q
- if Pattern-Match(p, q)
- return true
- return false
Worked example
A writer offers ⟨"robot/*", "diagnostics"⟩. Four
readers ask for different things.
| Reader requests | Result | Why |
|---|---|---|
⟨"robot/arm"⟩ | match | robot/* covers robot/arm |
⟨"telemetry", "diagnostics"⟩ | match | diagnostics is in both lists |
⟨"robot"⟩ | no match | robot/* requires the slash and something after it |
⟨⟩ | no match | an empty list is the default partition, which neither offered name covers |
The last row is the one worth remembering. Naming no partition does not mean accepting any. It asks for one specific partition — the default — and this writer is not in it.
Cost
O(P · Q · L) for lists of P and Q names of length at most L. All three are bounded by configuration, which is what keeps this acceptable inside the matching loop — it runs once per candidate pair, not once per endpoint.
Admission
Admitting a discovery record
any discovery announcement arrives, from any sender
Once per announcement received — and announcements repeat, so this is the most frequently executed discovery step.
Discovery accepts identities chosen by whoever is on the network. If every announcement heard were stored, a deployment's memory use would depend on strangers. So each table has a capacity fixed by configuration: local endpoints, local matches, remote participants, remote writers, remote readers.
When the table is full
A full table cannot simply reject everything. A peer that is already known needs to be able to refresh its description — its addresses change, its lease is renewed — and refusing that would drop a peer that is behaving correctly. The distinction is between adding a key and replacing one.
When the table has room but the match table does not
Admitting an endpoint is not free even when its own table has room: a new endpoint creates matches, and matches are stored too. So the number of matches it would create is counted before anything is written.
Every check happens before any change, so a rejection has nothing to undo.
Admit-Record(T, k, v)
T the table being inserted into, with its capacity and current occupancy · k the identity the peer announced · v the record describing it
- if k in T
- T[k] = v // replace in the slot it already holds
- return ok
- if T.count == T.capacity
- return error // nothing has been written
- m = Count-New-Matches(T, v)
- if T.matches + m > T.match-capacity
- return error
- v.id = Fresh-Id() // an identity is spent only once admission is certain
- T[k] = v
- T.count = T.count + 1
- Update-Indexes(T, v)
- return ok
Line 9 is easy to miss and matters: identifiers are handed out only after both capacity checks pass. If they were handed out first, a stream of rejected announcements would still consume them.
Cost
The table operations are O(1) on average. Counting the matches a new local endpoint would create is the same scan as matching itself, so O(E). Occupancy never exceeds capacity, and a rejected insertion changes nothing — which is what makes the memory ceiling hold no matter what arrives.
Announcement
Announcing what a participant has
the participant starts, and then on a timer
Built once. Resent every announcement period for the life of the participant, whether or not anything changed.
A participant describes itself in two kinds of message. One describes the participant — its addresses, its name, how long its announcements should be trusted before it is presumed gone. The others describe one endpoint each: topic, type, and the policies that endpoint offers or requests.
Why the same bytes are sent again
These are sent periodically rather than once, because there is no acknowledgement for them and a listener may have started late. That makes the cost of building them worth attention: rebuilding the same bytes every cycle would allocate on a fixed timer forever.
They are built once and resent unchanged. Because the bytes are immutable, the repeating part cannot introduce an endpoint that is not local, and cannot alter a policy.
Build-Announcements(p)
p the local participant, with its handles, addresses, and endpoints
- for each handle h in p.local-handles
- if h.owner ≠ p
- return error // never describe an endpoint that is not ours
- p.participant-record = Encode(p.discovery-locator, p.user-locator,
- p.lease, p.name, p.shared-memory)
- for each endpoint e in p.local-endpoints
- p.record[e] = Encode(e.guid, e.topic, e.type, e.hash,
- e.reliability, e.durability, e.partitions,
- e.presentation, e.lifespan)
- return ok
Announce-Cycle(p)
p the same participant, now holding the encoded bytes
- Send(p.participant-record)
- for each endpoint e in p.local-endpoints
- Send(p.record[e])
Lines 7 to 9 of the first procedure copy the endpoint's own policies. Writing a default in place of a policy the endpoint actually holds does not fail loudly. The record still encodes, still decodes, and still matches — against the wrong set of peers. Two endpoints that should have matched appear incompatible, and the fault shows up as silence.
A policy that is absent, and one that is wrong
The receiving side has the mirror-image rule. A policy that is absent from a record means the specification's default for that policy. A policy that is present but holds a value outside its allowed range is not treated as a default — the whole record is rejected.
Cost
Building costs O(B + P) once, for B bytes of announcement and P partition names, and the same again in storage. Each cycle after that is O(B) of transport work with no allocation. None of this runs on the path that publishes or reads a sample.
Convergence
Converging on a match
a peer is first seen and is not yet matched
Repeats until the match completes, then stops.
Rules about what a participant must not do — match too early, store too much, describe someone else's endpoint — say nothing about whether two participants ever succeed in matching. Both sides can stay perfectly correct forever while every announcement they send is dropped.
Matching goes through four steps in each direction, and both directions have to complete. A participant learns the other exists, then learns about its endpoints, and only then can a pair be matched.
Converge(a, b)
a, b two participants; the steps describe a learning about b, and the mirror image runs at the same time
- while b not in a.participants
- Offer-Participant-Record(b → a) // may be dropped
- while b.endpoints not in a.graph
- Offer-Endpoint-Records(b → a) // may be dropped
- if a knows b and b knows a
- Match(a, b)
When every announcement is dropped
This terminates only under two assumptions, which are not the same strength. The first is that an announcement that has not been observed keeps being offered — the loops never give up. The second is that a message which is offered infinitely often is eventually delivered. The second is the stronger assumption: it is not enough that delivery is possible now and then, because a network can keep interrupting it. It has to be that repeated offers cannot all fail.
Under those two assumptions, every pair of live participants eventually matches. The two safety rules — knowing endpoints implies having first known the participant, and matching implies both sides know each other — are what stop the loops from declaring success early.
What this does and does not establish
The argument is about the model, checked exhaustively over a finite number of participants. It says the design contains no execution that gets stuck. It does not say a particular network satisfies the delivery assumption. That is what a long-running test across real machines measures, and it measures it — it does not prove it.
Addressing
Choosing an address
a peer's addresses are learned, or the send policy changes
Once per change. The ordered result is kept and reused for fanout rather than recomputed per message.
A machine usually has more than one address, and a peer usually announces more than one. Something has to decide which to use, and two machines running the same configuration should decide the same way — otherwise behaviour changes between runs and cannot be tested.
The policy is two lists of address prefixes, one allowed and one denied, plus switches for loopback, wildcard, and multicast addresses. Deny wins over allow. An empty allow list does not mean nothing is allowed; it means everything that is not denied and passes the switches.
Why the order is fixed
Determinism comes from sorting rather than from the order things happened to arrive. Addresses learned from the peer sort ahead of fallbacks written into configuration, then by priority, then by address, then by port. Duplicates are removed after the sort with a hash set, so removing them does not become a quadratic scan when a writer has many readers or a host has many interfaces.
Select-Locators(C, policy)
C the candidate addresses · policy the allow and deny prefix lists and the loopback, wildcard, and multicast switches
- S = ⟨⟩
- for each candidate c in C
- if Denied(c, policy) // deny is checked first and wins
- continue
- if not Gates-Pass(c, policy) // loopback, wildcard, multicast
- continue
- if policy.allow is empty or Matches-Allow(c, policy)
- Append(S, c)
- Sort(S) by (learned before fallback, priority, address, port)
- return Dedup(S) // hash set over the sorted list
Cost
Testing one address against the prefix lists is O(A + D), so filtering N candidates is O(N (A + D)), and the sort adds O(N log N). The same procedure is used for advertised addresses, configured fallbacks, direct sends, and fanout to matched readers, which is why they cannot disagree.
Addressing
Where to send, once matched
a match completes, and before every send on it
Resolved once per match; one comparison and one address copy per send.
The address a peer was first contacted on is enough to start discovery. It is not necessarily where its endpoints want traffic. An endpoint can advertise its own address, and if it does, that is where its traffic goes; if it does not, the participant's default applies.
The part worth stating slowly is which endpoint's address is used for which direction, because the obvious reading is backwards.
Worked example
| Sending | Uses the address of | Not |
|---|---|---|
| Samples, and the writer's announcements | the remote reader | the remote writer |
| Requests and acknowledgements | the remote writer | the remote reader |
Traffic goes to whoever receives it, not to whoever it is about. A writer sending a sample is sending it to a reader, so the reader's address applies; a reader asking for a repair is asking the writer, so the writer's address applies. Reaching for the locator of the endpoint whose name is on the record sends every sample back at the writer that produced it.
Resolve-Route(p, w, r)
p the remote participant, with its default user address · w, r the matched remote writer and reader, each with an optional address of its own
- if w.prefix ≠ p.prefix or r.prefix ≠ p.prefix
- return error // an endpoint of some other participant
- to-reader = r.locator if present else p.default
- to-writer = w.locator if present else p.default
- return (To-Socket(to-reader), To-Socket(to-writer))
Line 1 refuses endpoints whose identifier does not belong to the participant being associated with. Announcements from elsewhere can still enter the discovery graph of the first section — that is a global view — but they cannot complete this association, which would otherwise let one participant direct another's traffic.
Line 5 converts both addresses once and stores the result. Every later send compares the endpoint it is sending to against the stored route and copies the address, rather than looking anything up in a discovery table on the sending path.
Cost
O(1) at match time, and O(1) per send: one comparison and one address copy, with no allocation, no hashing, and no discovery lookup. All seven record kinds — samples, fragments, both announcements, irrelevance declarations, and both request forms — take the same directional rule, so none of them can disagree about where to go.
Next: serialization and framing
A sample in memory has to become bytes another program, built by another compiler, can read back.
These descriptions follow the implementations in Tin DDS and Retina. Evaluation access and the full algorithm notes are available from engineering@tinverse.com.