A High Performance Total Order Broadcast Algorithm

Total order broadcast is an important group communication primitive for building fault-tolerant distributed applications, and it guarantees that all members in a communication group receive messages in the same order even if some members are faulty. The existing total order broadcast algorithms can not achieve both low latency and high throughput at the same time, and lack adaptability for the communication patterns of applications, and thus they are not suitable for high performance computing environments. In analyzed in this paper are the ordering mechanisms in some existing typical algorithms, and the key factors that affect the performance of total order broadcast algorithms are pointed out. Then a novel algorithm is proposed, which builds the total order using the leader/followers pattern and is driven by block detection mechanism. It works as follows: each group member can send messages at any time, but only messages from the current leader are delivered, and if the leader remains inactive, it will issue a special request to change the leadership to one of the active follower members. Simulation experiments are performed and the results show that the new algorithm achieves good performance in terms of both latency and throughput, and is much more efficient under bursty message arrival pattern.