Three Types of Sequencers

NoteDecember 19, 2020 - budding Distributed Systems, Sequencers

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

Unicast-Broadcast Sequencer

The sending 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

Broadcast-Broadcast Sequencer

Broadcast-Broadcast Sequencer

The sending 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:

Virtual Synchrony/ISIS

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

Unicast-Unicast-Broadcast Sequencer

The sending process is as follows:

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

Virtual Synchrony/ISIS

Tandem later (circa 1994) updated this protocol to make use of the Unicast-broadcast variant that made use of sequences and allowed concurrent broadcasts.


References and Further Reading

  • Ken Birman, 2009(?): A History of the Virtual Synchrony Replication Model
  • 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 doi: 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

The colors used in the diagrams in this post are sourced from Zion National Park, Utah, USA.