Byzantine Disk
Paxos: Optimal
Resilience with Byzantine Shared Memory
Ittai Abraham Gregory Chokler Idit Keidar Dahlia Malkhi |
|
|
Abstract We present Byzantine Disk Paxos, an
asynchronous shared-memory consensus protocol 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 protocol; that is,
we construct two different building blocks, each of which can be used, along
with a leader oracle, to solve consensus. One building block is a shared wait-free
safe register. The second
building block is a regular register that satisfies a weaker termination (liveness) condition than wait freedom: its write
operations are wait-free, whereas it's 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 consensus is solvable with FW-terminating registers
and a leader oracle. We construct each of these reliable registers from n
> 3t base registers, t of which can be non-responsive or
Byzantine. All the previous 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. |
||
[PODC version pdf] |