A Study on Asynchronous Randomized Consensus Algorithms for Byzantine Fault Tolerant Replication
純哉 中村 · OUKA (Osaka University Knowledge Archive) (Osaka University) · 2014
A distributed system consists of multiple processes connected by a network and the processes can communicate with each other by sending messages.The processes execute a distributed algorithm to solve a problem to provide a function, e.g.routing, an overlay network, and a distributed file system.One of the important features provided by the distributed system is fault tolerance.A distributed system realizes the fault tolerance by utilizing redundancy, and a target of fault tolerance, e.g., data, service, and so on, is replicated to the processes.The processes keep their replicas consistent to tolerate failures of communication links or processes.Byzantine failure is the most malicious failure, in which a faulty system behaves in an arbitrary way deviating from the original program.Such failures are caused by software bugs, hardware problems, or cracker attacks.In particular, cracker's attacks such as infections from viruses and intrusions are serious problems that severely damage systems connected in the Internet.Therefore, a practical fault tolerant method for Byzantine failure is strongly demanded.State machine replication is one of the main approaches to build a server system that can tolerate such Byzantine failures.In the replication, the server role is replicated to multiple replicas and the replicas process requests submitted by clients to the server.The replication guarantees that the server system can continue to process requests, even if a fraction of the replicas is Byzantine faulty because of crackers' attacks or software errors.To eliminate their malicious behaviors, a client uses a majority rule; the client collects responses from the replicas of a request and accepts only a major value of them.The non-faulty replicas must make the same responses so that the majority rule can work correctly, and this is realized if the replicas process all requests in the same order.Since network speed is not uniform and requests may be delivered to the replicas in different orders, the replicas execute a consensus protocol to agree on processing orders of the requests.In this dissertation, we propose two methods for the Byzantine fault tolerant (BFT) state machine replication that focus on the consensus part of the replication and improve efficiency vii viii and practicality.First, we define a new type of consensus problem called request set consensus problem and propose a randomized BFT protocol that solves it.The protocol is designed for an asynchronous distributed system like the Internet, and can be used to realize state machine replication.The protocol has two features to solve the problem efficiently.First, although most existing multivalued consensus protocols take a modular approach, in which replicas repeatedly solve a binary consensus problem to reach an agreement, our consensus protocol solves the request set consensus problem directly without such repetition.Thanks to the simple structure of the protocol, we can reduce the communication steps needed to reach an agreement.Second, we introduce an efficient coin tossing scheme that enables replicas to reach an agreement in a few rounds by exploiting the structure of the BFT replication.We prove that the protocol satisfies the correctness of the request set consensus problem.Performance evaluation is conducted from two viewpoints, i.e., analytically and experimentally.The analytical evaluation shows that our protocol can reach an agreement within two rounds, even if there are many replicas to tolerate Byzantine faults.In the experimental evaluation, our protocol achieves higher throughput and shorter latency than the existing ones, especially when the number of replicas is large.Second, we propose a method that parallelizes consensuses to determine processing order of requests.Since the BFT replication is deployed on an asynchronous network such as the Internet and every consensus protocol for the replication is a randomized one, the duration of an execution of consensuses varies every time.If some consensus takes a long time, invocations of succeeding consensuses are delayed.This causes performance degradation to the server replication, and we solve the problem by parallelizing consensus executions.However, if replicas simply process the agreed requests in their terminated orders of the consensuses, it also makes their replicated server states inconsistency, since the network is asynchronous and the terminated orders may differ among the replicas.Therefore, we introduce an extra agreement step to resolve this discrepancy.Moreover, to decrease the cost of the parallelization, we introduce a randomization technique to a consensus protocol to generate initial proposals for newly-invoked consensuses.It reduces the size of the proposals, and, as a result, the duration taken for the consensus protocol becomes shorter.We prove that the parallelizing method satisfies correctness for the replication and evaluate its performance by comparing the parallelizing method with a sequential method currently in use.The evaluation results show that the parallelization has a strong advantage in spite of requiring additional consensuses, especially, when some replicas work slowly or some requests are delivered late.