We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Byzantine disk paxos: optimal resilience with byzantine shared memory.
- Authors
Abraham, Ittai; Chockler, Gregory; Keidar, Idit; Malkhi, Dahlia
- Abstract
We present Byzantine Disk Paxos, an asynchronous shared-memory consensus algorithm that uses a collection of n < 3 t 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 < 3 t 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 4 t + 1 fault-prone registers, and we are not familiar with any prior FW-terminating constructions in this model. We further show tight lower bounds on the number of invocation rounds required for optimal resilience reliable register constructions, or more generally, constructions that use less than 4 t + 1 fault-prone registers. Our lower bounds show that such constructions are inherently more costly than constructions that use 4 t + 1 registers, and that our constructions have optimal round complexity. Furthermore, our wait-free construction is early-stopping, and it achieves the optimal round complexity with any number of actual failures.
- Subjects
ALGORITHMS; MATHEMATICAL models; SIMULATION methods &; models; MATHEMATICAL transformations; MACHINE translating; FOUNDATIONS of arithmetic; GENETIC algorithms; PAXOS (Computer science)
- Publication
Distributed Computing, 2006, Vol 18, Issue 5, p387
- ISSN
0178-2770
- Publication type
Article
- DOI
10.1007/s00446-005-0151-6