Paper: arXiv 2412.08624
Authors: Mohit Garg, Suneel Sarswat
Abstract
Continuous double auctions are commonly used to match orders at currency, stock, and commodities exchanges. A verified implementation of continuous double auctions is a useful tool for market regulators as they give rise to automated checkers that are guaranteed to detect errors in the trade logs of an existing exchange if they contain trades that violate the matching rules. We provide an efficient and formally verified implementation of continuous double auctions that takes \(O(n \log n)\) time to match \(n\) orders. This improves an earlier \(O(n^2)\) verified implementation. We also prove a matching \(Ω(n\log n)\) lower bound on the running time for continuous double auctions. Our new implementation takes only a couple of minutes to run on ten million randomly generated orders as opposed to a few days taken by the earlier implementation. Our new implementation gives rise to an efficient automatic checker. We use the Coq proof assistant for verifying our implementation and extracting a verified OCaml program. While using Coq’s standard library implementation of red-black trees to obtain our improvement, we observed that its specification has serious gaps, which we fill in this work; this might be of independent interest.
Complexity vs Empirical Score
- Math Complexity: 6.5/10
- Empirical Rigor: 4.0/10
- Quadrant: Lab Rats — high math complexity, limited empirical testing
Why this score: The paper involves significant theoretical computer science, including formal proofs of algorithmic lower bounds and verification of correctness using Coq, which is mathematically dense. However, the empirical validation is limited to runtime comparisons on synthetic data and lacks real-world backtests or statistical metrics on market data.
Research Flowchart
flowchart TD Goal["Research Goal<br>Efficient & Verified Continuous Double Auction Implementation"] Inputs["Data/Inputs<br>- Millions of Random Orders<br>- Trade Logs from Exchanges"] Method["Methodology<br>- Formal Verification (Coq Proof Assistant)<br>- O(n log n) Algorithm using Red-Black Trees<br>- Improved Standard Library Specifications"] Process["Computational Process<br>- Automated Order Matching<br>- Extraction to OCaml Program"] Outcomes["Key Findings & Outcomes<br>- Lower Bound: Ω(n log n)<br>- Verified Implementation (Minutes vs Days)<br>- Efficient Automatic Error Checker"] Goal --> Inputs Inputs --> Method Method --> Process Process --> Outcomes
Evidence Card
What the authors claim, on what data, and who has checked it. Read from the paper's own text by a language model: every quote is verbatim, nothing was re-run. How to read this card
Proposes
We provide an efficient and formally verified implementation of continuous double auctions that runs in O(n log n) time, improving on the earlier O(n^2) implementation.
Source sentence
We provide an efficient and formally verified implementation of continuous double auctions that takes $O(n \log n)$ time to match $n$ orders.
Assumes 4
- The exchange receives instructions consisting of a command (Buy, Sell, Delete) and an order, and maintains resident bid and ask sets. model
Source sentence
The exchange receives instructions from the traders (buyers and sellers) of the product. Each in-struction comprises of a command and an order.
- The matching algorithm must satisfy positive bid‑ask spread, price‑time priority, and conservation properties. model
Source sentence
(B, A, Command w) P7→( ˆB, ˆA, M) Given the above description of the exchange, it was observed in [5] that the following three properties must be satisfied by P. • Positive bid-ask spread: The most competitive bid in ˆB has a lower limit price than the most competitive ask in ˆA, i.e., no transaction is possible among resident orders. • Price-time priority: If Command w is a bid: if w gets traded with an ask a′,
- Resident bids and asks are stored in sorted data structures (lists in the previous implementation, red‑black trees in the new implementation). execution
Source sentence
In the implementation, B and A are kept as sorted lists. We store the resident bids and asks as BSTs.
- The red‑black tree operations (insertion, extraction, deletion) run in O(log n) time as per the Coq standard library specification. other
Source sentence
11 5.1 Strengthening the standard library guarantees For our BSTs, we use the standard library implementation of red-black trees [3], which implements insertion, extraction, and deletions in O(log n) time.
Data
- randomly generated order books synthetic unknown
Source sentence
We randomly generate order books of various sizes using a python script, run the extracted verified OCaml programs of ePro-cess instruction and Process instruction on it, and report the running times. Our or-der books generated are of sizes going from 200 thousand to 10 million.
Costs
Not applicable
Finds 3
- The new implementation matches orders in O(n log n) time, which is asymptotically optimal given the Ω(n log n) lower bound. theoretical
Source sentence
We provide an efficient and formally verified implementation of continuous double auctions that takes $O(n \log n)$ time to match $n$ orders. We also prove a matching $Ω(n\log n)$ lower bound on the running time for continuous double auctions.
- Running the new implementation on ten million randomly generated orders takes less than two minutes, a thousand‑fold speedup over the previous implementation. performance
Source sentence
Our new implementation takes only a couple of minutes to run on ten million randomly generated orders as opposed to a few days taken by the earlier implementation. In particular, for ten million orders our implementation takes less than two minutes to run, at least a thousandfold improvement.
- The previous implementation using lists required O(n^2) time and would take days on ten‑million‑order datasets. performance
Source sentence
The implementation uses the List data structure resulting in an O(n2)-time implementation for n orders. In this work, we drastically improve the running time by producing an O(n log n)-time implementation of continuous double auctions using Red-black trees instead of Lists.
Checked by others
No other paper in the archive has been found to support or contradict these findings (compared with 10 related papers). Coverage is partial, so this is neither replication nor refutation.
Code
No repository by the authors found in the paper.
Extracted 2026-11-14 · same card as JSON · A language model chose these items: check the source sentence before relying on one.