There are three types of total order broadcast sequencers that I’ve observed in the finance industry:
- Unicast-Broadcast Sequencer
- Broadcast-Broadcast Sequencer
- Unicast-Unicast-Broadcast Sequencer
Unicast-Broadcast Sequencer
The sending process is as follows:
- Sender submits message to the sequencer
- Sequencer orders the message, assigns a sequence, and broadcasts on to destination processes
Broadcast-Broadcast Sequencer
The sending process is as follows:
- Sender broadcasts an un-sequenced message; all processes receive it
- Sequencer orders the message, assigns a sequence, and broadcasts it to all processes again.
Virtual Synchrony/ISIS
The Virtual Synchrony/ISIS protocol operates at two levels. At the lower level, there is a FIFO protocol to ensure that sender messages are always received by pairs of destinations (e.g. the sender and sequencer or sequencer and destination) in the order that they were sent. NAK messages are sent by recipients in order to replace any missing messages in the FIFO order. On top of the lower level protocol, ISIS introduces a sequencer to provide total ordering across multiple processes.
The protocol is approximately as follows:
- Sender broadcasts a message to the destinations & sequencer
- Destinations receive message, note it is not sequenced, and ignore it
- Sequencer receives the message, orders and attaches a sequence number and then rebroadcasts
- Destinations receive message
- If a gap is noticed in the sequence, the destination(s) impacted will request the sequencer to resend any missing messages.
Visually:
ISIS has been fairly common in financial exchanges over the years, with users including the New York Stock Exchange and Swiss Stock Exchange. Note that this is an oversimplification of Virtual Synchrony, focused on the sequencer approach. There are many additional protocols used within Virtual Synchrony, and it’s worth studying directly.
Unicast-Unicast-Broadcast Sequencer
The sending process is as follows:
- Sender sends an un-sequenced message to the sequencer
- Sequencer responds to the sender with a sequence number, or a permission to send, for the message
- Sender then broadcasts the sequenced message.
Tandem Global Update Protocol
The Tandem Global Update Protocol (circa 1985) introduced a Locker component that would grant permission for a sender to broadcast a message. At first, the sender reaches out to the Locker, requests permission to send, and then only once granted does it broadcast to other processes. Note that communications are blocked while awaiting permission from the Locker, so there is no need for sequence numbers.
The protocol is approximately as follows:
- Sender requests permission from Locker to broadcast
- Locker grants permission when not locked
- Sender broadcasts to destinations
- Destinations ack
- If destinations do not ack before timeout, sender resends
- Once all senders have acknowledged, Sender informs Locker, and the Locker is free to grant a new send.
Visually:
Tandem later (circa 1994) updated this protocol to make use of the Unicast-broadcast variant that made use of sequences and allowed concurrent broadcasts.