Electronic trading systems provide the computational support for stock exchanges. Liquid markets use order-driven systems, i.e., where client requests, for trading nancial instruments, are served through individual orders. This paper presents Petri net models assembling some crucial processes executed within order-driven systems such as orders submission, application of precedence rules, and the order matching mechanism. Such processes were modelled as types of agents running in a multi-agent system (MAS) using nested Petri nets (NP-nets) - a convenient formalism for modelling MAS. With NP-nets, we focus on the control- ow perspective (causal dependence between activities executed by agents) and in the synchronization between agents. Conversely, we have used coloured Petri nets to extend the model including orders as objects with attributes. Thus, this work with Petri nets represents an experimental & initial research phase to validate trading systems using related methods such as process mining, simulations and model checking.
Stock exchanges have been historically the forum where market participants
trade nancial instruments, i.e., shares of a company. Brokers, with access to
the stock exchanges, provide the intermediary services to clients for trading.
The core of stock exchanges lies in stock trading systems - software solutions
supporting all the processes executed to perform trades. In this research, we
focus on order-driven systems [
University Higher School of Economics. ? Copyright c 2019 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0) orders from participants, rank/place orders in order books, and perform trades, among other operations.
Nowadays an important part of the trading volume of stock exchanges have
been shifted to order-driven electronic systems. As their trading volume growths,
with many participants and processes involved, it is a task of utmost importance
the validation of the trading system's correctness. i.e. auditing of the system's
processes, performance analysis, veri cation of its properties, among other tasks.
For such tasks, we consider Petri nets [
This paper presents an exploratory research work where we assemble as Petri
nets some important processes executed within order-driven systems. We focus
on the modelling of the processes of orders submission, execution of order
precedence rules, and the matching mechanism. We model the order-driven system as
a multi-agent system (MAS), where agents are conceived as running instances of
the mentioned processes, and these execute speci c tasks within the processing
of orders. This approach represents a theoretical model and do not necessarily
re ects real life technical implementations of electronic stock trading systems.
The main di erence is the sequencing of events into a single thread in the latter.
In this work, we use two classes of Petri nets. We present a rst model based on
nested Petri nets (NP-nets) [
The rest of this paper is organized as follows. Section 2 introduces some basic concepts of order-driven trading systems. Section 3 describes the NP-net and CPN models developed. Section 4 presents some conclusions and introduces future research work. 2
Order-driven systems handle requests from clients for trading nancial instruments as orders. At the core they contain rule-based processing that stores orders into the order books, applies precedence rules to prioritize orders, and matching mechanisms to perform automated trades between orders. The core is surrounded by order-routing systems, which deliver the orders from the clients and order presentation systems and market data systems send reports to clients about orders and trades. In this paper, we focus on the processes of submitting orders into an order book, and the activities of rule-based matching systems including the order precedence rules and the matching procedure. 2.1
An order, which we denoted as o, is a client instruction to trade a instrument, i.e., shares of a speci c company. Among its attributes, an order o has a side s 2 fbuy; sellg indicating whether the client wants to buy or sell, a price per stock p; and a quantity of stocks q to trade. Orders also include other constraints regarding in which terms the client wants to trade.
Order states. An order may have the following states. An order is submitted when it has been received by the system. The system veri es if the order is valid; if so, the order eventually changes its state to placed in an order book; otherwise, it is rejected. If an order o1 is traded with another order o2, then o1 is lled if q1 q2 where q1 and q2 are the stocks quantities of o1 and o2 to be traded; otherwise, o1 is partially lled waiting to trade its remainder q10 = q1 q2 with other orders. An order also may be replaced, canceled or expired.
Types of orders. In this paper, we focus on two kind of orders whose use is
very common, market orders and limit orders. Market orders aim to trade at the
best price available, i.e, a client placing a buy market order does not specify a
price, so he is willing to buy at the best price available that sellers ask. Instead,
limit orders trade at a nal price ptr not worse than a (limit) price p, i.e., buy
limit orders trade i ptr p, whereas sell limit orders trade i ptr p. We refer
to [
Order-driven systems use order precedence rules to separately rank buy and sell orders. Orders with highest precedence are served rst. The system ranks orders using a primary rule which usually is the price. Buy orders with higher prices, and sell orders with lower prices are ranked rst in their sides. Market orders always rank highest (their prices are not limited). If two or more orders have the same price, then it is applied a secondary rule; in this work, we consider time as the secondary rule - if two orders have the same price, it will be served the rst one submitted in the system. With price and time as our precedence rules, we considered a price-time policy for serving orders.
As an example, tables 1(a) and 1(c) show buy and sell orders received by the system. Each row in tables 1(a) and 1(c) represents an order o with a submitted time, its trader, size (quantity of stocks) and price per stock. As each order arrives, these are placed and ranked in the order book based on the price-time policy. Table 1(b) shows the order book state after all listed buy and sell orders have been ranked and inserted.
In Table 1(b), buy orders are served from the top to the bottom. Bif's order ranks highest (highest buy price), while Bud's order is ranked last (lowest buy price). Orders of Bea and Ben have the same price, but Bea's order is ranked rst since her order arrived before. Sell orders are served from the bottom to the top. Sol's order ranks rst (lowest sell price), while Stu is ranked last (highest sell price). Notice that the order book presented in Table 1(b) is a simpli ed and abstracted version w.r.t to how order books may be presented in real systems. The matching mechanism matches highest-ranked buy and sell orders. If the buy order price is greater or equal than the sell order price (the buyer is willing to pay at least what the seller demands) then a match is executed between the two orders. If one order is smaller than the other, the smaller order is lled, and discarded from the order book. The remainder of the largest order is placed in the order book. Such order still ranks highest in its side, so the system will attempt to match it against the next highest-ranking order on the other side of the order book. If two matched orders have the same size, both are lled completely. This process continues as long as the next highest-ranked buy order's price is greater or equal than the next highest-ranked sell order's price. From the example of table 1(b), matchings are executed as follows: 1. Sol's order to sell 1 at 19.8 with Bif's market order to buy 4. Sol's order is lled, and Bifs order is partially lled with a remainder of 3. 2. Bif's remainder order to buy 3 with Sue's order to sell 6 at 20.0. Bifs order is lled, and Sues order is partially lled with a remainder of 3. 3. Sue's remainder order of 3 with Bob's order to buy 2 for 20.1. Bob's order is lled, and Sue's order is partially lled with a remainder of 1. 4. Sue's remainder order of 1 with Bea's order to buy 3 for 20.0. Sue's order is lled, and Bea's order is partially lled with a remainder of 2. Table 2 shows the order book after execution of all possible matchings. Then, the process cannot execute matchings since now the highest-ranked buy order is less than the highest-ranked sell order. 3
Modelling Order-driven trading systems Distinct sub-processes with a prede ned set of tasks may operate concurrently in an order-driven system. Each sub-process may be seen as a kind of agent, which is instantiated upon request, it executes its tasks independently, it sends/receives messages from other agents, and eventually it is terminated upon completion of its tasks. Thus, we model using Petri nets some major components of an orderdriven system under a multi-agent system (MAS) approach.
The notion of agents has become an important concept in the software
engineering and arti cial intelligence (AI) domains, i.e., a MAS approach provides
a convenient degree of modularity, and it allows to understand the
communication points between sub-processes, which now we treat as agents. This section
describes the kind of agents we devised, and the MAS-based nested Petri net
(NP-nets) and coloured Petri net (CPN) models. In the following, it is assumed
that the reader has a basic understanding of NP-nets and CPNs; we refer to [
We have focused in the orders submission into the system, insertion and ranking on the order book, and the matching mechanism. Thus, we conceive a MAS model with the following kind of agents: { (x) Request handler agent. It handles an order submission into the system. It veri es whether or not the order is valid. If is valid, such order is forwarded to what we denote as an order book handler agent. Otherwise, the order is rejected and discarded. { (y) Order book handler agent. It is initiated upon a call from a request handler agent. It places and rank the received order in the proper order book side. When a matching is executed, against other order handled by other agent, it takes the order from its respective order book side, and it sends the order to a trade handler agent. Eventually, this agent receives a response indicating whether or not its order was lled. If so, the agent terminates. If not, it keeps handling the partially lled order that keeps stored in the order book. The agent also handles the replace, cancel or expire events of an order. { (z) Trade handler agent. It is initiate upon the reception of two orders, a buy and sell order, that have matched. This agent sends the trade to the clients. In addition, it checks if the orders are lled. If they have been partially lled, the agent places their remainders in the order book. Finally, it sends back to the order book handler agents which handle the buy and sell orders, informing whether or not the orders they handle are lled or not.
(x , o) request handlers serving orders a4 place in book order book handlers serving orders b8 notify match (y ,o) orders matched pending 2⋅(y ,o)
invoke matching handler o
t1 received orders receive order o o order book
handlers
Invoke t2 request
handler (x , o) (x , o) a3 reject order request handlers receive sell order b1
rank sell order b3 b5 replace b6 b7 cancel (EN y ) Order book handler agent y (EN z ) Trade handler agent z a
receive 1 order a2 order
verify reject order (EN x) agent x a3 a4 place in book Request handler
The NP-net model is depicted in Fig. 1 showing the system net SN , and the element nets ENx, ENy, and ENz, which describe the activities of agents of type x, y and z. The places request handlers, order book handlers, and trade handlers contain black dots indicating respectively the number of agents (system resources) of type x, y, and z available to be instantiated.
A submitted order o is produced in the place received order when the
transition t1 (receive order) res. If there is an available resource at the request
handlers place, the transition t2 (invoke request handler) res: it consumes a
black dot and a variable o, and produces a pair (x; o) at the place request
handlers serving orders meaning that an agent x will handle an order o. Agent x
may execute its internal transitions, described in ENx, for verifying the validity
of order o. If the order o is not valid, it is performed a vertical synchronization
step [
As depicted by the net ENy, an agent y may re transitions b1 (receive sell order) and b3 (rank sell order) if o is a sell order; otherwise, if res b1 (receive buy order) and b4 (rank buy order). Transitions b3 and b4 represent the activites of placing and ranking o in its corresponding order book side. Later, either one among of the activities b5 (replace order), b6 (expire order), b7 (cancel order) may be executed (thus, terminating agent y) or transition b8 (notify match) is red; if so, in the system net SN , the current agent y and the order o, represented as (y; o) will be transferred to the orders matched pending place.
Two tokens of type (y; o) at the place orders matched pending represent two orders (a buy and a sell order) that are matched. When transition t4 (invoke matching handler ) res, it consumes such couple of pairs (y; o), and a black dot from the trade handlers place; then, t4 produces a new pair (z; 2 o) in the place trade handlers running - it means that an agent z will handle the matching of the buy and sell order. Notice that t4 also produces back the two tokens of type (y; o); the latter means that the two agents of type y will wait for a response to be noti ed if the orders that they manage are lled.
The behavior of agent z is described by EN z. It executes transition c4 to send a message to the clients about the trade performed. It also executes c2 if the orders have been lled or c3 if one of the two orders is just partially lled; the latter is done to inform the previous two agents of type y, that wait for such response at the orders matching matching place. When receiving such response, each of the two agents of type y will be able to re either b9 (notify order partially lled) or b10 (notify order lled) according to the case. If b9 is red, then the pair (y; o) will be transferred from the order matched pending to the order book handlers serving orders place, indicating that y will attempt to eventually match the remainder of order o; otherwise, if b10 is red, the pair (y; o) simply disappears indicating the completion of y, and producing a black dot at the orders book handlers place. Notice that the place next matching enabled constrains the execution of transition b8 (notify match) to at most two times in a round (for a buy and a sell order), and no other matching can be executed until an agent z gives back the previously explained response to the two agents y handling the buy and sell order. The motivation of this is to give highest priority to be matched again to the orders processed by agent z (and that rank highest in their sides of the order book) in case one of them were just partially lled and transferred back to the order book. 3.3
Coloured Petri Net Model 1`("Bea",2000,3,buy)++ 1`("Ben",2000,2,buy)++ 1`("Bif",5000,4,buy)++ t1 o_ ORDER11``((""BBoubd"",,21091800,,27,,bbuuyy))++++ 1`("Sam",2010,2,sell)++ 1`("Sol",1980,1,sell)++ o_ o_ 11``((""SStuue"",,22002000,,56,,sseellll))++
y
o_ x X_O order book handlers
Y.alYl() t2 irnevqoukeest handler (x,o_)
AGENTSX (x, o_) tx (x,o_)
(x,o_) X_O x X.all() X request handlers y y y a3 roerjdeecrt x repbl5ace (y,o_) (y,o_) b6 (y,o_) Y_O (y,o_) o_ expire Y_O b7 (y,o_) (y,o_) o_ cancel Y_O orders filled o_ b10 o_ o_ b9 o_ ORDER ORDER
ORDER o_ c2 o_ ch2
ORDER o_ c3 o_ ch1
ORDER (x,o_)
X_O (x,o_) place in book a4 (y,o_)
Y_O y AGENTSY notify match omradtecrhsed pending (y,o_) ty o_pair o_pair t3 (z, o_pair) (z, o_pair)
ORDER_PAIR Z_O_PAIR list_
list_ list_ list_ 1`[] S list_ ORDER_BOOK list_
As a second exercise, we developed a CPN model, developed with CPN Tools
[
INT
SIDE ; Order book. An order book (from the color set ORDER_BOOK) is a sorted list l = fo1; o2; :::; ong such that the rst element o1 of l is the highest ranked order, and the last element on is the lowest ranked order. Thus, for a speci c nancial instrument, we devised to model an order book as two sorted lists lS and lB, such that lB stores buy orders, and lS stores sell orders. The system net of the CPN depicted in Fig. 2 shows places B and S - tokens in B and S are sorted lists of the color set ORDER_BOOK. The place B stores lists of buy orders, and S stores lists of sell orders. Since it is assumed to work with a single nancial instrument, the initial marking of S and B are unique empty lists (denoted as [ ] ). If we were working with m nancial instruments, then there would be m lists in each of these places.
1`[O]RDER_BOOK
In/Out 1 S 1`[("Sam",2010,2,sell)]
OuYt_O OuYt_O OuYt_O (y, o_) b5_ (y, o_) b6_
Fig. 3: CPN sub-page for execution of agents of type y (order book handlers).
Agents. CPNs do not follow the nets-within-nets paradigm as NP-nets do, i.e., tokens cannot be Petri nets themselves in CPN. Hence, CPNs become less suitable to model multi-agent systems (MAS). As a way to model MAS in CPN, we have devised the use of a hierarchical CPN model in the following way: the system net is the top page of the CPN model, whereas the internal net structure of agents x, y, and z, described in Fig. 1, have been modelled as sub-pages in the CPN model. The sub-pages with the tasks performed by agents x, y, and z are linked with the top page by substitution transitions tx, ty, and tz. For instance, Fig. 3 shows the sub-page for agents of type y where a few agents are handling orders, i.e, agent ay ( 1 ) is about to process Ben's order; agent ay ( 3 ) is waiting to execute b4 for ranking Bif's order, and agent ay ( 4 ) already placed Sam's order in the order book, so its order eventually may be matched, or its order may be replaced, expired, or canceled. Hence, agents are emulated by object tokens which navigate through a shared structure which is the model sub-page. Note also that each sub-page is connected by input and output channels with places of the system net using the ports-sockets mechanism provided by hierarchical CPNs. Through these channels, an agent into the sub-page for agents y (Fig. 3) is able to place an order into a list of the places B and S (an order book side), it is noti ed if an order has been lled, among other communication points. This principle is the same for agents of type x and z.
Order precedence rules. Arc inscriptions of the used CPN model are allowed to have functions as expressions. Thus, we were able to model order precedence rules (using a price-time policy) on the lists stored in places S and B, which represent the buy and sell sides of an order book. As depicted by Fig. 3, when an agent y res b4 (rank buy order) it is consumed the order o_ that the agent y is handling, and the list of sell orders list_; as a result, the transition produces in place B a reorganized list executing the function buy_rank ( o_ , list_ ) which has been implemented as follows: fun buy_rank ( i , p , q , s ) [ ] = [ ( i , p , q , s ) ] j buy_rank ( i , p , q , s ) ( ( i2 , p2 , q2 , s2 ) : : list_ ) = if p > p2 then
( i , p , q , s ) : : ( i , 2 , q2 , s2 ) : : list_ else ( i2 , p2 , q2 , s2 ) : : ( buy_rank ( i , p , q , s ) list_ )
The function rst checks the case if list_ is empty; if so, it returns the list with the single order ( i , p , q , s ) ; otherwise, it compares the order ( i , p , q , s ) with the rst element of the list, ( i2 , p2 , q2 , s2 ) (the operator : : stands for concatenation). If the price p of the new order is strictly greater (>) than the price p2 of the rst order in the list, it is returned a new list where the new order ( i , p , q , s ) is placed rst since now it is the order which ranks highest; otherwise, ( i2 , p2 , q2 , s2 ) is maintained as the highest ranked order, and a recursive call of buy_rank ( i , p , q , s ) , list_ is done with list_ as the rest of the list without the rst element we already compared. This principle is applied in the function sell_rank using the operator strictly less than (<) since sell orders whose price is lowest are ranked rst. Note that albeit time semantics yet are not used in our work, the use of strict operators, < and >, allow to give precedence to orders who were submitted before.
Guards. Boolean expressions known as guards [
In this paper we have developed experimental Petri net models for some components of order-driven trading systems: orders submission, ranking of orders in an order book, and the matching mechanism. We conceived a multi-agent system (MAS), where each process of the system has been devised as a kind of agent. We aim to focus on nested Petri nets (NP-nets), where tokens can be Petri net themselves, so we have shown how its semantics allow to suitably model MAS. We focused on the control- ow perspective, i.e., causal dependence between activities executed by the system net and the agents, and on their synchronization points, for instance, taking advantage of vertical synchronization steps. Notice that a MAS model is capable to respect the sequential priority execution of order matchings in an order book, i.e., in Fig. 1, when two agents y1 and y2 with orders o1 and o2 respectively are matched, then no other orders can match until the trade (o1; o2) is handled completely by an agent z.
We also designed a CPN model to express attributes of orders; this allowed to model explicitly the use of precedence rules over orders. Guards, logic expressions, on transitions, are a way to impose additional constraints on the execution of an activity based on the order attributes. Future research will address the necessary formal de nitions for our MAS models. The use of Petri nets describing these processes of a trading system is a milestone in our research. Based on such models, Fig. 4 shows some validation tasks which are matter of future research:
Conformance checking [
Simulation and performance analysis. Simulation helps to identify errors on the system's execution, and to carry out a performance analysis. For instance, if we include time semantics on the Petri net models, we are able through simulations to identify bottlenecks, i.e., waiting time for orders to be served by an Petri-net-based model Multi-agent system approach processes (agents) b a c d b a c d system net (agent society)
MODELLING agent, time needed for an agent to complete its activities, etc.Time semantics would allow to model other crucial concepts of trading, such as trading sessions and orders validity and expiration that we did not tackle in this work. We may use well-known tools for Petri nets, such as CPN Tools, which execute Petri net models, and allow software extensions; thus, we may develop an order book interface, whose orders and state is a ected by the execution of a Petri net.
Veri cation of behavioral properties. Exhaustive and automated formal
verication of the functional and non-functional properties of the system by means
of the model checking approach [