A Vector Clock Based Leaderless Consensus Algorithm

Distributed consensus is fundamental to building high available systems,which allows a collection of machines to work as a coherent group that can tolerate the failures of some of its members.It requires high throughput,low latency and high availability.However,these requirements cannot be satisfied well at the same time in any existing consensus algorithm.In this paper,we propose Veca,a consensus algorithm for state machine replication that tries to satisfy the requirements at the same time as well as possible.Byzantine fault tolerance is essential to building high reliable systems.The popularity of blockchain applications revitalizes Byzantine fault tolerant algorithms.However,Byzantine fault tolerant algorithms can impose much overhead and cannot satisfy high throughput,low latency and high availability.In this paper,we extend Veca and propose BVeca,an algorithm for Byzantine fault tolerant state machine replication that tries to satisfy the requirements at the same time as well as possible.The main work and contributions include:(1)Veca consensus algorithm is proposed.Veca is a leaderless consensus algorithm for which all replicas can propose commands concurrently at any time,and each command can be committed after just one round of communication with a majority of replicas in the normal case.Veca separates agreement from ordering and execution,which allows all replicas to commit commands concurrently without determining their order,but to track their dependencies using vector clocksl,then they are assigned an order and executed in that order.Commands are committed out of order and then be executed in the same order by all replicas.The system can provide continuous service as long as more than half of the replicas are available.(2)BVeca Byzantine fault tolerant algorithm is proposed.BVeca is a no-primary Byzantine fault tolerant algorithm for which all replicas can propose commands concurrently at any time,and each command can be committed by a two-phase agreement protocol in the normal case.BVeca separates agreement from ordering and execution,which allows all replicas to commit commands concurrently without determining their order,but to track their dependencies using vector clocks,then they are assigned an order and executed in that order.Commands are committed out of order and then be executed in the same order by all non-faulty replicas.The system can provide continuous service as long as less than one third of the replicas are faulty.(3)BVeca is used for blockchain consensus,and a blockchain prototype system is implemented to verify the safety and validity of the algorithms.The latency,throughput,latency with throughput,and availability of Veca and BVeca are evaluated through experiments in LAN and WAN.The fault tolerant capabilities of Veca and BVeca are verified using Jepsen.The experimental result shows that Veca and BVeca have high performance and fault tolerant capability.