Appendix A:
Definition of Gridlock and Gridlock Resolution in Kronos
As described in Chapter 3, situations can arise where payments in an RTGS system are blocked due to inappropriate distribution of liquidity among the participants, even though overall there is sufficient liquidity in the system to settle the payments. This situation is called gridlock. Gridlock can be resolved if there is a subset of pending payments that can be settled simultaneously without any of the participants ending up with an overdraft. An algorithm that selects this subset is called a gridlock resolution mechanism.[1]
GRIDLOCK RESOLUTION
Assume that there are n participants and let 
be the number of payments in participant i's queue. The overall queue in the RTGS system is given as 
. In the same way, a subset of payments for simultaneous settlement in order to resolve gridlock is given as 
, where
is the contribution from each participant's queue. Ex ante and ex post balances, including the overdraft access on each participant's account, are given as respectively 
and 
, i.e. the balance of participant i's account before and after a gridlock resolution. The value of the payments received by participant i is given as 
, where -i signifies non-i, and the value of the payments remitted by participant i is given as
.
A gridlock resolution is a situation where there is a non-empty subset 
, so that if the payments were settled simultaneously then
(1)
Condition (1) ensures that if the payments are settled simultaneously the ex-post balance for all participants will be non-negative. The ex post balance is given by the ex ante balance less the value of payments remitted from participant i, 
plus the value of payments received by participant i,
.
The definition does not take account of the sequence of the payments in the liquidity queue. This means that any possible gridlock resolution will not respect any prioritised sequence that participants in the payment system can allocate to their payments. Therefore let 
indicate a preference relation for participant i with regard to the sequence in which the payments are required to be settled.
By adding the following condition (2) to the gridlock resolution it is ensured that the participants' prioritised sequence is complied with:
\
so that 
(2)
Gridlock resolution presents the maximisation challenge of settling as many payments as possible, so as to minimise the waiting time for the queued payments. The maximisation challenge is therefore to select the largest possible subset of queued payments that can be settled simultaneously, given the two sub-conditions defined above.
Let V(X) be the value or number of payments in X. Resolution of the gridlock is
,
on condition that the liquidity condition stated in (1) and the sequence condition stated in (2) are fulfilled.
The subconditions ensure that both the value and the number of simultaneously settled payments are maximised.
GRIDLOCK RESOLUTION IN KRONOS
As described in Chapter 6, Kronos has an algorithm that can search the liquidity queue for possible gridlock resolutions, as well as a functionality that can resolve the gridlock itself. The algorithm takes account of the sequence of payments so as to respect the participants' prioritisation. The participants' liquidity management is thus not interfered with.
In Kronos, the algorithm can either be activated to search the current liquidity queue once, or to monitor the liquidity queue on an ongoing basis. Ongoing monitoring entails that the algorithm seeks to find a solution each time a participant changes the sequence of its payments in the liquidity queue, or if a payment is either added to or removed from the liquidity queue. The algorithm will also seek to find a solution each time there is a change in the disposable current-account balances of the relevant participants.
CALCULATION OF THE OPTIMUM SOLUTION IN KRONOS[2]
Gridlock resolution in Kronos adheres to the same principles and sub-conditions as are given in equations (1) and (2).
Let 
be the number of direct participants.
Let
be the number of queued payments for the i’th participant.
Let
be the amount of a queued payment where
identifies the remitter,
identifies the recipient, and
indicates the position in the queue.
Let 
indicate the disposable amount for the i’th participant's current account[3].
Let 
indicate the number of payments in the i’th participant's queue included in the solution 
is the value of the payments that are settled
and 
indicate the total amount that the i´th participant is respectively to remit and receive.
Let 
be the new disposable amount[4] for the i’th participant.
The maximisation task can now be written as:
The solution is an algorithm that in view of the sub-conditions is considered to be fair since respecting the sequence entails that no participant is favoured at the expense of others. The algorithm furthermore finds the optimum solution for both the system overall and for the individual account holder. No account holder or group of account holders will be able to settle more payments by coming up with their own solution compared to the solution found by the algorithm.
In practice, the algorithm first calculates each participant's ex post balance if all payments in the liquidity queue are settled simultaneously. If this leads to a negative ex post balance for one or more participants the algorithm will remove the last payment belonging to one of the participants with a negative ex post balance. The algorithm then calculates the result of simultaneous settlement of the rest of the payments in the liquidity queue. If one or more participants once again end up with a negative ex post balance, another payment will be removed from the calculations, and the algorithm runs again. This will continue until all participants that are part of the solution end up with a positive ex post balance.
LITERATURE
Bech, Morten Linnemann and Kimmo Soramäki, 2001. Gridlock Resolution in Payment Systems, Danmarks Nationalbank, Monetary Review 4th Quarter 2001.
Danmarks Nationalbank, 2001. Kronos System Specifications.
[1] The Appendix is based on Bech and Soramäki (2001) and the Kronos System Specifications.
[2] The algorithm was designed in cooperation with the Department of Informatics and Mathematical Modelling at the Technical University of Denmark.
[3] If the balance of the account is kr. 20 million and the overdraft access is kr. 50 million the disposable amount is kr. 70 million.
[4] The overdraft access is assumed to be constant.