A Scalable Fault-Tolerant Limit Order Book

Relevant applications to systems research are those which demand rapid turnaround time, ACID semantics, and scalability. One such application is a central limit-order book. Briefly, a limit-order book is an abstract table containing the buy and sell orders for some good. From a systems perspective, constructing a limit order book applicatin for financial market goods, such as stocks, foreign exchange, and bonds, is very interesting because they represents the greatest challenge to computer systems designers. This class of applications demands the following properties which are all quite difficult to provide:

Table 1 shows a sample set of incoming orders, and table 2 shows the resulting limit-order book. A limit-order is an order for a good at a fixed price or better. For example, an order to buy 100 shares of IBM at 125 or better is a limit order. The order will only execute if another trader is willing to sell IBM at 125 or less. The same idea can be applied to any good, for example, a foreign exchange order might be to sell 1M yen at 100 ¥/$ or more. Limit-orders are in contrast to market orders, which leave the price open, "e.g. Buy 100 shares of IBM at the market", means to buy 100 shares at whatever the "best possible price" is at the time the order is submitted 1.

Arrival Time

Trader

Order Type

Size

Price

1:00

ERKA

buy

300

25

1:01

RPMP

sell

400

25 ¼

1:02

ACKL

buy

200

25

1:06

BRZK

sell

100

market

1:08

XYZZ

sell

200

25 ½

1:09

ATRI

buy

600

market

1:11

ANAM

Sell

400

25

Table 1. An example order flow.



Buyers

Price

Sellers

Trader

Size


Size

Trader



market

100

BRZK

ERKA

300

25



ACKL

200

25





25

400

ANAM



25 ¼

400

RPMP



25 ½

200

XYZZ

ATRI

600

market



Table 2. Example Limit-Order book from the order flow in Table 1. Orders are sorted by price-time priority.





The main idea of a central limit-order book application is to accept buy and sell orders, and perform a matching function between the buys and sells. Resulting matches between traders must be logged and then sent to a central clearinghouse for further processing. The sequence of logs is called the audit trail. A key question in limit order books relates to market structure. The main issue is the time factor used to perform the match between buys and sells. There are two classes of market structure: call markets and continuous auction markets.

In call markets, such as the Arizona Stock Exchange, orders are held for a long time interval, (hours, or in the case of AZX, a day) and at the end of the period the market application computes a single price against which all orders are executed. The time the single price is determined is called the "call". The price is the one which maximizes some function, such as the sum of all traders' surpluses. The trader's surplus os the difference between the limit price and call price.

In continuous auction markets, (NYSE is somewhat like this), orders are matched against the "standing limit order" for both the buy and sell side. That is, as soon as an order arrives, the market attempts to match it. For example, in Table 1, as soon as order 4 arrived, it would be matched against order 1. In a call market, order 4 might get matched against an order that occurred later in time, resulting in a better price for the trader. The primary difference between the two is immediacy. The continuous auction allows the trader to obtain the good as soon as the limit order is reached; the call market is slower but allows for greater maximization of traders' surpluses. Which type is better depends on the trader. In dealer markets, a dealer provides liquidity by placing firm quotes that can be traded against. This class of market isn't as interesting from a computer systems perspective, and so we will not consider it further.

These continuous and call markets, however, are actually a continuum of a single type of market. The real difference is in the time dimension; a continuous market is one in which the matching interval period has been reduced to zero. Thus, from a system perspective, the real challenge is the ability to support a scale of matching periods ranging from near zero to a day, or even days, depending on the structure of the market.

Class Projects

Certain reduction operators are tolerant to duplicates. For example, max() and min() return the same result for a given set even if duplicate items are introduced into the set. Could you take advantage of these operations' tolerance to duplicates to design a fault-tolerant max or min distributed algorithm on a cluster? In the context of a central-limit order book, rapidly finding the best price in a fault tolerant manner, is critical to the operation of the order book.

Develop a fault tolerant sort. Many markets are organized by price-time priority. That is, the orders are sorted using price first, then time, as the fields on which to match. Sorting is somewhat resistant to duplicates as well. Could you modify and existing parallel sort to add duplicates in such a way as to be fault-tolerant? How would you remove duplicates after the sort finished? A good start to parallel sorting algorithms can be found here. Could you extend some of the algorithms to be fault tolerant?

Assume that a cluster contains all orders distributed over all nodes, which may or may not be sorted. Compute the price that maximizes the traders' surplus. Would you sort the orders first, or use some other algorithm to find the price that maximizes the traders surplus?

Matching also has an invariant property with respect to duplicates. If orders A and B are matched at price C, then duplicate orders A' and B' should also be matched to each other at price C. Devise a fault tolerant matching algorithm which takes advantage of this property.

Readings:

    L. R. Glosten. Is the Electronic Open Limit Order Book Inevitable? Journal of Finance, 49, 1127-1161.

    L. Harris. The Economics of Best Execution. USC Working Paper, March 9, 1996


1. One interesting twist on the limit order idea is to leave the amount unbound but bind the final price; e.g., buy $1000 of IBM at whatever number of shares another trader is willing to sell at. This is not exactly the same thing as a market order depending on the structure of the market. In a market with firm quotes, such as dealer market, such an unbound order reduces to a market order. However, in a limit order book structure, such a limited market order can be matched against existing limit and market orders in many ways.