This paper investigates under which conditions information can be reliably shared and consensus can be solved in unknown and anonymous message-passing networks that suffer from crash-failures. We provide algorithms to emulate registers and solve consensus under different synchrony assumptions. For this, we introduce a novel pseudo leader-election approach which allows a leader-based consensus implementation without breaking symmetry.
There have been several approaches to solve fault-tolerant consensus in anonymous networks deterministically. In @cite_5 , fault-tolerant consensus is solved under the assumption that failure detector @math @cite_7 exists, i.e. exactly one correct process eventually knows forever that it is the leader. In @cite_3 , fault-tolerant and obstruction-free For obstruction-free consensus, termination is only guaranteed if a process can take enough steps without beeing interrupted by other processes. consensus is solved if registers are available.
@cite_5 @cite_3 @cite_7
1796152689 2077240273
We present Byzantine Disk Paxos, an asynchronous shared-memory consensus algorithm that uses a collection of n < 3t disks, t of which may fail by becoming non-responsive or arbitrarily corrupted. We give two constructions of this algorithm; that is, we construct two different t-tolerant (i.e., tolerating up to t disk failures) building blocks, each of which can be used, along with a leader oracle, to solve consensus. One building block is a t-tolerant wait-free shared safe register. The second building block is a t-tolerant regular register that satisfies a weaker termination (liveness) condition than wait freedom: its write operations are wait-free, whereas its read operations are guaranteed to return only in executions with a finite number of writes. We call this termination condition finite writes (FW), and show that wait-free consensus is solvable with FW-terminating registers and a leader oracle. We construct each of these t-tolerant registers from n < 3t base registers, t of which can be non-responsive or Byzantine. All the previous t-tolerant wait-free constructions in this model used at least 4t + 1 fault-prone registers, and we are not familiar with any prior FW-terminating constructions in this model. 1. Introduction.PART I: FUNDAMENTALS.2. Basic Algorithms in Message-Passing Systems.3. Leader Election in Rings.4. Mutual Exclusion in Shared Memory.5. Fault-Tolerant Consensus.6. Causality and Time.PART II: SIMULATIONS.7. A Formal Model for Simulations.8. Broadcast and Multicast.9. Distributed Shared Memory.10. Fault-Tolerant Simulations of Read Write Objects.11. Simulating Synchrony.12. Improving the Fault Tolerance of Algorithms.13. Fault-Tolerant Clock Synchronization.PART III: ADVANCED TOPICS.14. Randomization.15. Wait-Free Simulations of Arbitrary Objects.16. Problems Solvable in Asynchronous Systems.17. Solving Consensus in Eventually Stable Systems.References.Index. This paper defines a new consensus problem, convex consensus. Similar to vector consensus [13, 20, 19], the input at each process is a d-dimensional vector of reals (or, equivalently, a point in the d-dimensional Euclidean space). However, for convex consensus, the output at each process is a convex polytope contained within the convex hull of the inputs at the fault-free processes. We explore the convex consensus problem under crash faults with incorrect inputs, and present an asynchronous approximate convex consensus algorithm with optimal fault tolerance that reaches consensus on an optimal output polytope. Convex consensus can be used to solve other related problems. For instance, a solution for convex consensus trivially yields a solution for vector consensus. More importantly, convex consensus can potentially be used to solve other more interesting problems, such as convex function optimization [5, 4].