Algorithms and data structures

How Tin DDS and Retina work

Tin DDS is the C++ implementation; Retina is the Rust implementation. Both organize communication around participants, topics, writers, readers, and histories. Security and Teleoperation add their own responsibilities without making ordinary DDS applications depend on them. Start with the design below, then follow a chapter for the algorithm details.

From application to application

Design at a glance

1. Match: Discovery associates writers and readers by topic, type, and compatible QoS. It maintains those associations as endpoints join, leave, or expire; it is not a handshake per sample.
2. Publish: A writer assigns a sequence and applies its history and resource policies. Retention keeps data available for repair or late readers when the selected QoS requires it.
3. Transfer: The transport delivers bytes or a shared slot notification. Reliability tracks delivery independently of the application's decision to consume a sample.
4. Receive: The reader applies admission and history policies. The application reads or takes the resulting sample.

Network and shared memory transport

UDP: Writer → serialization and retention → RTPS framing → UDP → RTPS parsing and reader admission → deserialization → application.
Native SHM loans: Writer reserves and fills a shared slot → publishes a descriptor → reader validates and borrows the slot → releases its loan. Payload ownership replaces the network payload transfer; the slot stays live while owners still need it.

A descriptor identifies a slot within a shared segment; it is not a pointer into another process. Native SHM delivery does not need to wrap its notification in RTPS DATA and parse it back. It still checks segment identity, slot generation, size, ownership, and the applicable DDS policies. A benchmark that sends complete RTPS packets over SHM measures a different path from a native loan-and-notification benchmark.

A loan permits eligible data to be constructed or viewed in shared memory. An ordinary value-based write or take may still encode, decode, or copy the value. Same-host placement alone does not make every API zero-copy. Transport support also belongs to the chosen service: the C++ participant_service facade, for example, serves static UDP peers.

Objects and collaborations

Who owns what

Participant: Owns the application's domain identity and DDS entities. Discovery maintains peer knowledge; the transport service performs I/O.
Topic, publisher, subscriber: A topic names the data and its type. Publishers group writers; subscribers group readers and their presentation policy. They are not network connections.
Writer and history: The writer owns publication sequence and offered QoS. Its history owns retained samples; reliability decides which matched readers still need repair.
Reader and history: The reader owns requested QoS and sample admission. Its history owns the samples available to read or take, including keyed-instance and lifecycle state.
Discovery and matching: Own peer announcements and endpoint associations. A locator tells routing where a peer can be reached; it does not by itself establish a compatible match.
Transport service: Owns sockets, receive storage, progress, and shutdown. A SHM daemon owns shared segments; process-local loans account for who may still use a slot.
Security session: Owns authenticated peer state, keys, and replay state. Permissions decide allowed operations; message protection verifies incoming data before it reaches the consumer.
Robot control session: Owns one robot's operator lease, command permits, and accepted sequence. Security supplies authenticated identity; the application supplies sensor observations and actuator behavior.

These are responsibilities, not a promise of identical class layouts. C++ and Rust use different ownership and storage types to implement the same DDS contracts. Each implementation needs its own verification.

Composition

Security and Teleoperation are optional modules

DDS: Discovery, QoS, histories, transport, and delivery. Neither robot command semantics nor security credentials are required by the unsecured core.
DDS + Security: Add peer authentication, permissions, message protection, and replay rejection without robot-specific policy.
DDS + Teleoperation: Add command freshness, duplicate rejection, and control authority. These checks alone do not authenticate a remote operator.
DDS + both modules: Authenticate and authorize the peer, then apply robot command policy. UDP and SHM commands enter the same robot control session so changing transport cannot reset its decisions.

Module composition is not a deployment safety decision. A product must select its security policy, timing limits, and response to communication loss. DDS reliability acknowledges data; a robot receipt reports command admission; actuator feedback reports what actually happened. Robot-owned command deadlines explain where that admission decision is made.

Definitions

The DDS words used in this series

DDS uses familiar words in precise ways. These definitions are enough to follow the algorithms; each part introduces its more specialized terms where they are needed.

Domain: A logical communication scope identified by a domain ID. It is not a host, process, subnet, or transport.
DomainParticipant: One application's presence in a domain. It owns that application's DDS entities and discovery identity.
Topic: A named, typed subject. Writers and readers correspond when the topic, type, and requested and offered behavior are compatible.
DataWriter and DataReader: The publishing and subscribing endpoints for a topic. Applications write through a DataWriter and read or take from a DataReader.
Sample: One topic value plus DDS metadata: who wrote it, its sequence and timestamps, and its instance state. A lifecycle sample can carry metadata without a value.
Instance and key: An instance is one logical object in a keyed topic, such as one robot or sensor. Its key stays the same while successive samples describe its state.
History: Samples retained by a writer or reader. Reader history feeds the application; writer history supports repair and can serve late readers.
Quality of Service (QoS): Policies for delivery, retention, timing, ownership, and resources. Matching compares what a reader requests with what a writer offers.
DDSI-RTPS: The interoperable protocol that carries DDS discovery, serialized data, endpoint identity, sequence state, and reliability control.
CDR and XCDR: The binary representations that turn a typed value into portable bytes and reconstruct it at the reader.
Discovery: The control-plane exchange that announces participants and then their endpoints. It establishes associations; it is not repeated for every publication.
Reliable repair: The RTPS exchange that identifies missing sequence numbers or fragments and retransmits only what is needed. DDS reliability is not a TCP stream.
Shared-memory transport: A same-host path that keeps the DDS API and delivery behavior while placing eligible payloads in shared memory and notifying local readers.

Contents

1. Discovery and matching

Two programs start up knowing nothing about each other. They announce themselves, decide which announcements to keep, and work out which writers should send to which readers.

Covers. Indexed endpoint matching, partition comparison, admission into a full table, repeated announcement, convergence, address selection.

2. Serialization and framing

A sample in memory has to become bytes another program, built by another compiler, can read back — including when the two disagree about what the type contains.

Covers. Alignment and padding, wide strings, sequences and arrays, members found by number, message framing and context.

3. Reliability and fragmentation

Networks drop packets and refuse large messages. Samples are held until acknowledged, gaps are reported compactly, and split samples are put back together in place.

Covers. Acknowledgement, receipt and gap tracking, control and data framing, reassembly, arena ownership, selective repair.

4. Content filtering

A reader subscribes with a condition attached. That condition has to mean the same thing as announced text, as a compiled predicate, and at any writer that understands it.

Covers. Announcing a filter, compiling an expression, composing predicates, admission, replacement over queued samples, writer-side egress.

5. History, durability and instances

Where a sample is stored, what a notification carrying no value means, and what a reader that starts an hour later — or after a restart — receives.

Covers. Storage, instance lifecycle, read against take, coherent sets both ways, per-writer logs, service retention, retirement, request-reply.

6. Liveness, timing and status

Whether the writer has gone quiet, whether the reader is falling behind, how much it has lost, and which of several writers it should believe.

Covers. Rate limiting, lifespan, missed deadlines, liveliness leases and aggregation, match counts, loss accounting, exclusive ownership.

7. Shared-memory transport

On one machine an eligible payload can stay in a shared slot. Readers receive a descriptor and hold a loan until they finish using it.

Covers. Lock-free slot reservation, the ABA problem, multi-reader notification, attachment, reclaiming after a process dies.

8. Identity and permissions

An announcement is not proof of identity. In a secured domain, peers authenticate and permissions determine what each is allowed to do.

Covers. Admitting an advertisement, plugin agreement, the handshake, splitting a credential, permissions, endpoint data tags.

9. Key material

Authenticated participants derive session keys and distribute the required key material through protected messages.

Covers. Handshake derivation, generation, the material record, session keys, transactional installation, participant and endpoint activation.

10. Protecting messages

What a protected message looks like, and what has to be true before its bytes are trusted. Caller-provided storage helps keep allocation out of the message path.

Covers. Header, ciphertext framing, tags, the cipher call, payload protection, the submessage envelope, key selection, nonce uniqueness, replay.

11. Key distribution

Every key had to reach the other side. The channel carrying them is encrypted and reliable — a small protocol inside an envelope, holding secrets on a clock.

Covers. Token wrapping and addressing, retention until acknowledged, protected transmission and control, receipt, secure discovery.

12. Teleoperation

A robot rejects commands that are late, repeated, or outside the operator's authority. The network cannot guarantee that a command arrives in time.

Covers. Resource profiles and pre-allocated buffers, fair UDP and shared-memory receive turns, one admission state across transports, duplicate suppression, control authority.

13. Resource limits

Every part above bounds something by configuration. This one collects those bounds, says what happens at each, and covers what a full history can be asked to do.

Covers. The complete limit table, transactional rejection, keep-last against keep-all, port selection, how the limits are demonstrated.

14. ROS 2 adaptation

ROS hands over type information at run time, as data rather than as types. Three parts of the mapping onto DDS stop being mechanical because of it.

Covers. A serialization plan built once per type, request and reply correlation across many clients, filters compiled to normal form.

Notation

Reading the pseudocode

Procedure names are in small capitals. Assignment is = and comparison is ==. Indentation shows block structure; there is no closing keyword. A field of a structure is x.field, and NIL means no value.

Every procedure lists what its arguments are before its steps, and the letters used for sizes are defined with the procedure that uses them rather than once for the whole series. The same letter can mean different things in different parts — F is a count of fragments in one and a count of declared fields in another — so the local definition is the one that applies.

Start with discovery

Nothing else can happen until two programs have found each other and agreed that they should be talking.

Part 1 · Finding each other →

These descriptions follow the implementations in Tin DDS and Retina. Evaluation access and the full algorithm notes are available from engineering@tinverse.com.