基于排序机制的全序广播算法分类与性能分析

Classification and performance of total order broadcast and multicast algorithms based on the mechanism of ordering

已有的全序广播和多播算法多达近五十种,为了便于人们根据需要从众多算法中进行选择,需要对这些算法进行明确分类。但现有的分类方法都存在着完备性较差,且难以理解等问题。基于排序机制,从全序广播和多播算法的通信记录、优先权、动态序列器、静态序列器和目的方一致五个方面,给出了一种针对全序广播与多播算法的新系统分类方法。同时,还从定性、定量两个方面对分类的各类算法进行了规范、应用模型环境以及性能的分析与评测。使用新的分类方法以及测评结果,可以在现实应用中很方便地从现有算法集中根据需要选择合适的算法。

So far, there are almost are almost fifty algorithms on total order broadcast and multicast, which makes it too difficult to select a best suited algorithm to a given application context. Though some attempts have been made at classifying and comparing these algorithms recently, none is comprehensive, and hence lacks generality. A novel classification system is proposed by using the ordering mechanisms. In this system, five classes of total order broadcast and multicast algorithms are defined, I.e. communication history based algorithm, privilege-based algorithms, dynamic sequencer algorithm, static sequencer algorithm and destination agreement algorithm. Then existing algorithms are related to these classes. Also, the performances of each class are analyzed qualitatively and quantitatively. With this classification method and the analytical result, it is very convenient to choose an appropriate algorithm for a specific a specific application.