This post describes details of message delivery for the Distributed Publish/Subscribe Protocol and how this can be implemented with mailboxes, and serves as an example of using mailboxes.
Message delivery
Subscribers of pub/sub topics deliver messages locally in causal order, buffering messages with missing dependencies.
It is independent of the dissemination protocol that forwards messages without buffering.
A message synchronization protocol ensures that missing dependencies eventually arrive.
Once a missing message arrives, it triggers delivery of deliverable buffered messages.
Causal delivery maintains the causal order according to the message DAG, which is the result of a topological sort of the DAG.
Causal delivery with mailboxes
A mailbox responsible for causal delivery buffers all messages
which contain any dependency that has not been delivered yet.
Since message dependencies are referenced by a signed message content hash, the mailbox needs to keep track of message hashes that it has delivered so far.
In case of a pub/sub topic, epochs are used to limit causal history, where relays and subscribers only need to maintain history for the current epoch.
Subscribers of the pub/sub have different roles, a node may have one or more roles:
- publisher: publishes messages
- subscriber: delivers messages locally
- relay: forwards messages to other relays
- broker: a relay with remote subscribers
Let’s take a look at an example of a relay with local subscribers.
The implementation consists of two engines responsible for handling pub/sub messages:
- Topic Relay: responsible for message forwarding between remote relays (Topic 1 in the figure)
- Local Broker: responsible for causal delivery to local subscribers (Local Topic 1 in the figure)
The Topic Relay receives messages from remote relays, stores them in Local Storage in order to be able to serve message requests from other nodes, then forwards them to the Local Broker and other remote relays. It uses FIFO delivery without buffering with a validity predicate that checks whether the message signature comes from a valid publisher.
The Local Broker delivers messages to local subscriber engines in causal order with the help of a mailbox.
The mailbox uses the Local Storage for message buffering, but since the Topic Relay already stores all messages there, it only needs to keep track the set of buffered message hashes, and when they become deliverable retrieve them from Local Storage and forward them to the Local Broker.
The mailbox has a validity predicate that perform further checks, such as further permissions and validity of the payload.
The two layers of validation checks allows filtering out messages by non-publishers to avoid spam and message amplification attacks, and ensures that all messages with a valid signature are disseminated even if their contents are malicious or invalid, which serves as a proof of misbehaviour for Byzantine nodes. On the second layer the delivery predicate ensures only valid messages are delivered.
Message type
type TopicMsg := mkTopicMsg {
publisher : PublisherID;
deps : Set TopicMsgID;
tags : Set String;
content : TopicMsgContent;
hsig : Signature;
};
type TopicMsgID := mkTopicMsgID {
publisher : PublisherID;
hash : Digest;
hsig : Signature;
};
cc @jonathan