Consensus Related Problems In Distributed System

In this thesis, we mainly study the consensus problem in distributed system. Con-sensus is one of the most fundamental and important problems in distributed computingwhich abstracts the basic agreement problem one often sees in distributed systems.In 1985, it has been proven that it is impossible to solve consensus in asyn-chronous system[1]. In the following 20+ years, people propose many methods tocircumvent this impossible result. One of the methods is the use of failure detectorabstractions, which is first proposed by Chandra and Toueg[2]. It becomes a powerfultechnique to encapsulate system conditions needed to solve many distributed comput-ing problems. Among failure detectors studied in the literature, the failure detectorsfor k-set agreement have received many attentions from the research community in therecent year. In this thesis, we first propose two new classes of failure detectorsΩ_k′andΩ′k′, which are new ways of extendingΩ, and show that they are equivalent toΩ_k. Then, we present a faithful extension of the Paxos algorithm based onΩ′k′. Boththe new failure detectors and the new algorithm enrich our understanding of the k-setagreement problem. We then propose the partition approach and define several newclasses of partitioned failure detectors which are weaker than existing failure detectorsfor the k-set agreement in both the shared-memory model and the message-passingmodel. Our results demonstrate that the partition approach opens a new dimension forweakening failure detectors related to set agreement, and it is an effective approach tocheck whether a failure detector is the weakest one or not for set agreement. We showthat all previous candidates for the weakest failure detectors of set agreement have beendisproved by the partitioned failure detectors.Two basic forms of consensus are binary consensus and multivalued consensus.We firstly present two bounded cost algorithms that solve multivalued consensus usingbinary consensus instances in message-passing system with reliable links. Then, weextend the results into message-passing system with fair-lossy links. We show that with binary consensus we can implement uniform reliable broadcast directly in systems withfair-lossy links, and thus binary consensus and multivalued consensus are equivalentin such system. We further prove that, when binary consensus instances are availableonly as black boxes, any implementation requires the invocations of an infinite numberof binary consensus instances.