{"paper_id":"2412.08624","title":"Efficient and Verified Continuous Double Auctions","authors":["Mohit Garg","Suneel Sarswat"],"paper_date":"2024-12-11","paper_type":"theoretical","paper_url":"https://arxiv.org/pdf/2412.08624v1","page_url":"https://thequant.space/flowcharts/efficient-and-verified-continuous-double-auctions/","scores":{"empirical_rigor":4,"math_complexity":6.5,"quadrant":"Lab Rats"},"proposes":{"status":"available","statement":"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.","quote":"We provide an efficient and formally verified implementation of continuous double auctions that takes $O(n \\log n)$ time to match $n$ orders.","summary":"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…","strategy":null},"assumptions":{"status":"available","items":[{"assumption":"The exchange receives instructions consisting of a command (Buy, Sell, Delete) and an order, and maintains resident bid and ask sets.","type":"model","stated":"explicit","quote":"The exchange receives instructions from the traders (buyers and sellers) of the product. Each in-struction comprises of a command and an order.","support":"full"},{"assumption":"The matching algorithm must satisfy positive bid‑ask spread, price‑time priority, and conservation properties.","type":"model","stated":"explicit","quote":"(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′,","support":"full"},{"assumption":"Resident bids and asks are stored in sorted data structures (lists in the previous implementation, red‑black trees in the new implementation).","type":"execution","stated":"explicit","quote":"In the implementation, B and A are kept as sorted lists. We store the resident bids and asks as BSTs.","support":"full"},{"assumption":"The red‑black tree operations (insertion, extraction, deletion) run in O(log n) time as per the Coq standard library specification.","type":"other","stated":"explicit","quote":"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.","support":"full"}]},"datasets":{"status":"available","items":[{"name":"randomly generated order books","provider":null,"kind":"synthetic","access":"unknown","period":null,"universe":null,"quote":"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.","support":"full"}],"known":[],"sample":{"start":null,"end":null,"market":null,"asset_class":null,"frequency":null},"data_resolution":"synthetic"},"transaction_costs":{"status":"not_applicable","modeled":"n/a","headline_net_of_costs":null,"detail":null,"quote":null,"source":"front_matter","rule":"R3","candidates":{"front_matter":"n/a","evidence_card":"n/a","evidence_card_quoted":false},"meaning":"the paper reports no trading or execution result"},"results":{"status":"available","evaluation_type":"none","findings":[{"finding":"The new implementation matches orders in O(n log n) time, which is asymptotically optimal given the Ω(n log n) lower bound.","kind":"theoretical","quote":"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.","support":"full"},{"finding":"Running the new implementation on ten million randomly generated orders takes less than two minutes, a thousand‑fold speedup over the previous implementation.","kind":"performance","quote":"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.","support":"full"},{"finding":"The previous implementation using lists required O(n^2) time and would take days on ten‑million‑order datasets.","kind":"performance","quote":"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.","support":"full"}],"reported_performance":null,"out_of_sample":{"method":"none","headline_out_of_sample":null}},"independent_evidence":{"status":"none_found","supports":[],"contradicts":[],"qualifies":[],"compared_with":10,"citations":{"cited_by_in_corpus":0,"by_independent_authors":0,"how_cited":{"used_as_baseline":0,"uses_method_or_data":0,"extends":0,"discusses_findings":0,"mentions":0,"unclassified":0},"independent_papers":[],"scope":"Citations between papers in this corpus only; citations from outside it are not counted."}},"implementation":{"status":"available","public":false,"code_url":null,"note":"No repository presented by the authors as their own was found in the paper. Absence here is not proof that no code exists."},"replication":{"status":"none_found","card":null,"note":"No replication of this paper has been run by thequant.space yet."},"extraction":{"text_source":"fulltext","model":"openai/gpt-oss-120b","version":2,"extracted_at":"2026-11-14T19:53:31Z"},"provenance":{"claims":"Everything here is what the authors state in the paper. Nothing was re-run or reproduced by the platform.","quotes":"Assumptions, datasets, cost detail and findings were extracted by a language model. Every quote is verbatim paper text. Where an item has `support`, \"full\" means every figure in it appears in the quoted sentences and \"partial\" means a figure is stated elsewhere in the paper; items with a figure found nowhere in the paper were discarded.","datasets_known":"datasets.known lists well-known vendors and public datasets by a stable id, found by a dictionary over the full text where the sentence says the data is used; it is independent of the model and covers only names in the dictionary.","flags":"transaction_costs.modeled, results.evaluation_type and results.out_of_sample.method are platform classifications (structured-decision models); see https://thequant.space/score-guide/#penalty-flags","comparisons":"supports / contradicts / qualifies are a language model's reading of two papers' quoted findings, restricted to closely related papers that share no author. They are pointers to read, not verified replications, and coverage is partial.","implementation":"code_url is a repository the paper itself presents as its own (rule-scored, ambiguous cases judged by a model), checked for liveness when it was recorded."},"docs":"https://thequant.space/agents/"}