Sequencers

Overview of three types of fixed total order broadcast sequencers

Three types of total order broadcast sequencers that I've observed in the finance industry:

These are all classed as fixed sequencers by Defago, Schiper, and Urban - whom also provide the names used below.

Broadcast-broadcast Sequencers

Marked A in the diagram. Process is as follows:

  1. Sender broadcasts an un-sequenced message; all processes receive it
  2. 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:

  1. Sender broadcasts a message to the destinations & sequencer
  2. Destinations receive message, note it is not sequenced, and ignore it
  3. Sequencer receives the message, orders and attaches a sequence number and then rebroadcasts
  4. Destinations receive message
  5. 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 Sequencers

Marked B in the diagram. Process is as follows:

  1. Sender sends an un-sequenced message to the sequencer
  2. Sequencer responds to the sender with a sequence number for the message
  3. 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:

  1. Sender requests permission from Locker to broadcast
  2. Locker grants permission when not locked
  3. Sender broadcasts to destinations
  4. Destinations ack
  5. If destinations do not ack before timeout, sender resends
  6. 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.

Unicast-broadcast Sequencers

Marked C in the diagram. Process is as follows:

  1. Sender submits message to the sequencer
  2. Sequencer orders the message, assigns a sequence, and broadcasts on to destination processes

References

Xavier Défago, André Schiper, and Péter Urbán. 2004. Total order broadcast and multicast algorithms: Taxonomy and survey. ACM Comput. Surv. 36, 4 (December 2004), 372–421. 10.1145/1041680.1041682
F. Cristian, R. Beijer, and S. Mishra, “Comparing How Well Asynchronous Atomic Broadcast Protocols Perform,” in Responsive Computer Systems: Steps Toward Fault-Tolerant Real-Time Systems, D. S. Fussell and M. Malek, Eds. Boston, MA: Springer US, 1995, pp. 103–122. doi: 10.1007/978-1-4615-2271-3_6
J. Bartlett, J. Gray, and B. Horst, “Fault Tolerance in Tandem Computer Systems,” in The Evolution of Fault-Tolerant Computing, vol. 1, A. Avižienis, H. Kopetz, and J.-C. Laprie, Eds. Vienna: Springer Vienna, 1987, pp. 55–76. doi: 10.1007/978-3-7091-8871-2_3
K. Birman and T. Joseph. 1987. Exploiting virtual synchrony in distributed systems. SIGOPS Oper. Syst. Rev. 21, 5 (Nov. 1987), 123–138. doi: 10.1145/37499.37515
Kenneth Birman, André Schiper, and Pat Stephenson. 1991. Lightweight causal and atomic group multicast. ACM Trans. Comput. Syst. 9, 3 (Aug. 1991), 272–314. doi: 10.1145/128738.128742
Kenneth P. Birman. 1993. The process group approach to reliable distributed computing. Commun. ACM 36, 12 (Dec. 1993), 37–53. doi: 10.1145/163298.163303

Change log

  • Added 19 December 2020
  • Updated 20 December 2020 with notes on Tandem Global Update Protocol & Virtual Synchrony
Metadata
🌿
reading time
1 min read
published
2020-12-19
last updated
2020-12-20
importance
low
review policy
continuous
Topics
Distributed Systems
--- Views

© 2009-2021 Shaun Laurens. All Rights Reserved.