E.1 Continuous Double Auction (CDA)

Continuous Double Auctions are one out of thousands of possible auction forms i.e., procedures to "negociate" a price between sellers and buyers. The main characteristics of CDAs is that it runs in continuous mode i.e., there are no "trading phases" like other auctions may have.

For example, there are auctions like those organized by Southeby's where the seller fixes a minimal prices. Then potential buyers have a limited amount of time to submit their bids, there may be several rounds of bids, each bidder trying to outbid its opponents. Finally the auction is closed, awarding the good to the bidder that offered to pay the most.

In continuous auctions we have a fully symmetric configuration with multiple bidders and multiple sellers. Price offers to buy and buy offers to sell may be submitted at any time, and may be retracted at any time. A public order book lists the currently best (highest) bids and best (lowest) sell offers. As soon as one bidder offers a price that is equal or better to the lowest sell offer, the CDA matches these offers. They are removed from the system and from the order book. Today's electronic stock exchanges usually work with CDAs.

From an Operating System point of view, CDAs can be considered as an anonymous synchronization primitive where the system only reveils the price and quantity of items that a party wants to buy or sell and where the parties block until a match can be made. A single synchronization primitive is provided:

long long cda_offer(int handle, int *quantity, int *price, struct timeval *timeout)

where:

handle is similar to a file identifier in UNIX: it identifies the auction we would like to participate in. This number is returned by the
```
cda_create(int orderbooksize)
```
call.
quantity points to an integer variable that contains the number of items to buy.
If the quantity is negative, this means that we want to sell.
price points to an integer variable specifying the highest price that one is willing to pay.
In case of a negative quantity (selling), this is the minimum price that one requests for the good.
A price of -1 means: buy (or sell) at the currently best available price (which is usually dangerous ..., but sometimes convenient).
timeout is a pointer to a timeout value. If no match was possible after the specified time, the offer should be retracted from the system.
A null pointer means: block until a match is possible.
The result is a 64-bit entity (long long is GNU CC compiler's way to specify a 64 bit integer).
A 0 result means: no match
A -1 is never returned.
Any other return value means: match occured! The actual quantity and actual price are stored in the respective parameters.

In case of a match, both parties receive the same long long value, which acts like a contract number. It enables the parties to establish contact in order to exchange good against money. This phase of a buy transaction, however, is out of scope of this project. The task is to implement a CDA server under Linux and to write simple demo trading agents that make use of the CDA. An example demo would be a set of 20 concurrent buyers and 10 sellers, all using a simple ramp algorithm (once every second we increase our bid if we did not obtain a match, or lower our offer if we are a seller). The average match price should reflect the reservation prices of buyers and sellers and the buyer/seller ratio.

Implementation considerations

There are mainly two ways to implement CDAs:
(a) add a system call and extend the Linux kernel
(b) write a user-level server
The teams have to make up their own minds which approach they prefer.
The advantage of the kernel approach is that most of the functionality is already present: processes can block in ready-made waiting lists, wakeing up etc is easy. However, kernel programming is more tedious and error prone, although programming/debugging cycles could be simplified by writing a loadable kernel module.
Writing a user-level server has the problem of having to establish communication channels between buyer/seller clients (use named pipes/FIFO to contact the server at a known place), you must implement all list management yourself, maintain timeout lists etc. The server also has to watch for clients that die (are killed) bye watching for error conditions on the pipe's sockets, in order to release the client's entry in the order book. See the notes on the S.1 project on contacting a server inside UNIX.
Another disadvantage are concurrency problems between the server and the clients, especially when updating the file that contains the orderbook information (see below).
In case of a kernel implementation approach, the best way to publish the order book is to use the /proc file system. Because we provide the file's content from within the kernel, we can not have read/write access conflicts.
In case of a server implementation, the UNIX file system is the most natural choice (too), but it suffers from the previously mentioned access conflict which is not fatal but which may confuse clients.
In both cases we would have a file for each CDA that exists in the system. The content is the order book, the file's name would be some random number generated when we create the CDA. The orderbook is written as simple as follows:
```
% cat 198526454
0@0 3@6 2@7 10@8 5@9 5@20
```
The notation is quantity@price, the first half of the entries are buy bids, the second half are sell offers (asks). In the example we would have an orderbook of size 6, with only two buy offers in it, one wanting to buy three items at a price of 6, and another for 2 items at a price of 7. Three sellers offer to give away items at prices 8, 9 or 20.

Last updated: April 15, 1999 http://www.docs.uu.se/~tschudin