实时全额支付系统中基于基本环的高效多边撮合算法分析和设计

ANALYSIS AND DESIGN OF ELEMENTARY CIRCLES-BASED EFFICIENT MULTILATERAL OFFSETTING ALGORITHM IN REAL TIME GROSS SETTLEMENT SYSTEM

传统撮合法一般会找到一个可撮合环后,就立即进行撮合,属于典型的贪心算法。针对这种情况,提出从全局角度考虑多环清算。算法首先使用双边撮合和拓扑排序对有向图进行简化处理,剩下节点和边必然构成环,提高了查找基本环算法(时间复杂度:O(n^32~n)的效率;对于多环共用公共节点的情况,利用银行家算法得出多环的安全推进序列;对于多环共用有向边的情况,不仅给出多环的安全推进序列,还考虑了共同撮合的情景。通过以上步骤,提升了多边撮合的性能,节约了参与机构的流动性、提高了资金使用效率。最后,给出了算法的时间复杂度分析和复杂案例应用(多环交于多点或多边)。

Traditional offsetting methods will immediately start to offset after finding an executable offsetting circle, which belong to the typical greedy algorithm. In view of this,the paper proposes an algorithm from the global perspective to consider the multi-cyclic clearing. First, the algorithm adopts bilateral offsetting and topological ordering to simplify a directed graph, and the rest of nodes and edges must constitute circles ,which improves the efficiency of basic circles searching algorithm （time complexity： O（ n^32^n） ）. In the case of multi-cyclic sharing common vertexes, the algorithm utilises the bank＇ s algorithm to obtain an orderly offsetting sequence. In the case of multi-cyclic sharing directed edges,the algorithm not only provides a multi-cyclic orderly offsetting sequence, but also considers the circumstance of common offsets. Through the above steps ,the performance of the multilateral offsetting is improved, which saves the liquidity of participants and improves the efficiency of fund utilisation. Finally, the time complexity of the algorithm is analysed, and complex case applications （e. g. malti-cyclic sharing common multi-vertexes or multi-edges） are presented.