Next: The
Algorithm Up: Contents Previous: System
Model
The algorithm provides both safety and liveness assuming
no more than (n-1)/3
replicas are faulty. Safety means that the replicated
service satisfies linearizability [14]
(modified to account for Byzantine-faulty clients [4]):
it behaves like a centralized implementation that executes operations atomically
one at a time. Safety requires the bound on the number of faulty replicas
because a faulty replica can behave arbitrarily, e.g., it can destroy its
state.
Safety is provided regardless of how many faulty clients are using the service (even if they collude with faulty replicas): all operations performed by faulty clients are observed in a consistent way by non-faulty clients. In particular, if the service operations are designed to preserve some invariants on the service state, faulty clients cannot break those invariants.
The safety property is insufficient to guard against faulty clients, e.g., in a file system a faulty client can write garbage data to some shared file. However, we limit the amount of damage a faulty client can do by providing access control: we authenticate clients and deny access if the client issuing a request does not have the right to invoke the operation. Also, services may provide operations to change the access permissions for a client. Since the algorithm ensures that the effects of access revocation operations are observed consistently by all clients, this provides a powerful mechanism to recover from attacks by faulty clients.
The algorithm does not rely on synchrony to provide safety. Therefore,
it must rely on synchrony to provide liveness; otherwise it could be used
to implement consensus in an asynchronous system, which is not possible
[9]. We guarantee liveness, i.e.,
clients eventually receive replies to their requests, provided at most
(n-1)/3
replicas are faulty and delay(t) does not grow faster than 2t
indefinitely. Here, delay(t) is the time between the
moment t when a message is sent for the first time and the moment
when it is received by its destination (assuming the sender keeps retransmitting
the message until it is received). (A more precise definition can be found
in [4].) This is a rather weak
synchrony assumption that is likely to be true in any real system provided
network faults are eventually repaired, yet it enables us to circumvent
the impossibility result in [9].
The resiliency of our algorithm is optimal: 3f+1 is the minimum number of replicas that allow an asynchronous system to provide the safety and liveness properties when up to freplicas are faulty (see [2] for a proof). This many replicas are needed because it must be possible to proceed after communicating with 2f+1 replicas, since f replicas might be faulty and not responding. However, it is possible that the f replicas that did not respond are not faulty and, therefore, fof those that responded might be faulty. Even so, there must still be enough responses that those from non-faulty replicas outnumber those from faulty ones, i.e., n-2f > f. Therefore n > 3f.
The algorithm does not address the problem of fault-tolerant privacy:
a faulty replica may leak information to an attacker. It is not feasible
to offer fault-tolerant privacy in the general case because service operations
may perform arbitrary computations using their arguments and the service
state; replicas need this information in the clear to execute such operations
efficiently. It is possible to use secret sharing schemes [35]
to obtain privacy even in the presence of a threshold of malicious replicas
[13] for the arguments and portions
of the state that are opaque to the service operations. We plan to investigate
these techniques in the future.
Next: The
Algorithm Up: Contents Previous: System
Model