Epidemic Broadcast Trees
Documentation of the EBT replication mechanism.
The goal of the EBT mechanism is to provide a more efficient replication mechanism which could serve as a replacement of the
There exists a reference implementation of this mechanism however no official documentation is available. This is an attempt at documenting the observed behaviour of this mechanism.
- Epidemic Broadcast Trees
For each Secure Scuttlebutt peer connection we can differentiate two actors:
- a client which initiates the connection
- a server which accepts the connection
Those two sides of every Secure Scuttlebutt peer connection will be referred to as client and server respectively.
For each Secure Scuttlebutt RPC stream we can differentiate two actors:
- a requestor which sends the initial request opening the stream
- a responder which receives the initial request to open the stream
Those two sides of every RPC request exchange will be referred to as requestor and responder respectively. Note that in the case of duplex streams both requestor and responder freely exchange messages after an RPC stream is established.
Creating an EBT session
An EBT session is a duplex RPC stream which is established between two peers after they successfuly connect. The EBT session is established by sending an
["ebt", "replicate"] request between the two peers. Since this is a duplex stream only one of those streams is needed for each connection.
After a connection between two peers is established the client is responsible for opening an EBT session by sending an
["ebt", "replicate"] request to the server:
Therefore the client acts as a requestor and the server acts as a responder in this scenario.
The requestor sets the
version argument to
3 and the
format argument to
"classic". The responder validates the arguments ensuring that the
version argument is set to
3 and the
format argument is set to
"classic". If the arguments are incorrect the
responder terminates the stream with an error.
format argument serves a purpose as a separate EBT session is presumably established for each feed format. For now we are just documenting the behaviour for the default Secure Scuttlebutt feed format.
The peers can now exchange messages over a duplex RPC stream. The EBT session has been created.
Two kinds of messages are sent by both peers during an EBT session:
- control messages known as notes
- feed messages
When receiving a message a peer needs to identify which message was received through some heuristics (eg. checking if a received message conforms to the specified JSON format). There is no explicit way of determining what message was received.
Peers send so called notes to each other. Each note is a JSON object containing one or more name/value pairs.
Each name is a JSON string which represents a feed in the
@ character notation. The validity of this string should be confirmed when a note is received. Receiving a note with a malformed feed identifier should terminate the EBT session with an error.
Each value is a JSON number. The number presumably doesn’t have the fractional element which comes after the decimal point as its meaning would be unknown. The number can be negative, positive or a zero. Receiving a note with a malformed value should terminate the EBT session with an error.
If the value is negative (usually
-1) it means that the peer doesn’t want to receive messages for this feed. Lets refer to this scenario as replicate flag being set to
If the value isn’t negative then it should be interpreted as follows. First, the JSON number should be parsed and converted to a signed integer. Then, the rightmost (lowest order) bit of the number should be interpreted as a binary flag with
0 equal to
1 equal to
false. This flag is referred to as the receive flag. Next, a “sign-extending right shift” (also called “arithmetic right shift”) by 1 bit should be performed on the binary number therefore discarding the rightmost (lowest order) bit. This number should then be interpreted as a sequence number for the feed specified in the name field of this name/value pair. Lets simply call this number sequence.
To encode a note a reverse of this process should be performed. If the replicate flag is set to false then the value can simply be set as
-1. Otherwise, the number should be stored as a signed integer and “left shift” should be performed. The rightmost (lowest order) bit should then be set according to the replicate flag as described previously.
Note: I believe when encoding this value it is irrelevant whether this is a signed or an unsigned integer as the value will always be positive, the type of a bit shift shouldn’t matter either.
Example note values
|Note value||Decoded note|
| || |
| || |
| || |
| || |
| || |
Feed messages are sent verbatim in RPC responses. Each response may contain one feed message. Therefore for the default Secure Scuttlebutt feed format a message like this can be sent or received:
Those messages are sent after the peer is instructed to send them by receiving a certain control message. When this message is received it should presumably be validated and persisted by the receiving peer if it is interested in it. The messages should presumably be sent ordered by the ascending sequence number so that they can be validated.
Initializing an EBT session
Work in progress…
Not all peers support the EBT mechanism. In that situation
createHistoryStream replication should be used instead. Two general recommendations listed below should most likely be followed. Additional scenarios are listed below as well but most likely don’t need to be supported.
A general recommendation for the server is to fall back to
createHistoryStream replication if:
- at least one
createHistoryStreamis opened by the client or no EBT session is opened by the client for a certain amount of time (Scenario 2, Scenario 3)
A general recommendation for the client is to fall back to
createHistoryStream replication if:
- server terminates the EBT session opened by the client with an error (Scenario 1)
If a requestor attempts to open an EBT session but the session is terminated with an error by the responder then the EBT mechanism is most likely not supported and
createHistoryStream replication should be used by the requestor instead.
If the client immediately attempts to use the
createHistoryStream replication then most likely the EBT mechanism is not supported by the client and
createHistoryStream replication should be used by the server as well. In this situation there is most likely no reason to attempt to follow Scenario 4.
If the client doesn’t create an EBT session for a certain amount of time then most likely the EBT mechanism is not supported by the client and
createHistoryStream replication should be used by the server.
If the local node acts as a server and the client connecting to it doesn’t create an RPC session for a certain amount of time then the server can attempt to establish an RPC session instead and act as a requestor. This will likely fail as the EBT mechanism clearly designates the client as the requestor.
- ECMA-404, the JSON data interchange syntax
- Epidemic Broadcast Trees, 2007