US 6,671,821 B1 · Byzantine fault tolerance

Abstract

A new approach for asynchronous state-machine replication in a fault-tolerant system offers both integrity and high availability in the presence of Byzantine faults. The approach also improves the security of previous systems by recovering replicas proactively without necessarily identifying that they have failed or been attacked. This proactive recovery limits the time extent of a particular fault by regularly recovering replicas. In this way, the system works correctly even when all the replicas fail multiple times over the lifetime of the system, provided that less than ⅓ of the replicas are all faulty within a window of vulnerability. The approach also features an efficient implementation of message authentication that prevents an attacker from impersonating a replicated node that was faulty after that node recovers

Claims12

Dependent claims

A method for fault tolerant operation of a distributed server system that includes N asynchronous servers that may experience faults, comprising:

receiving a series of requests from a client over a time interval associated with the requests;
at each of the N servers, processing some or all of the client requests including, for each of the requests processed at a server, updating a state of a state machine at that server according to the request and transmitting a response to the client;
and
resetting each of the N servers repeatedly during the time interval, wherein resetting a server includes establishing the state of the state machine at that server using data stored at other of the servers so that the state at that server corresponds to a common state of the server system;
wherein when (a) for a predetermined duration time window, fewer than N/3 of the server systems experience faults in any time window of the time interval of the requests of that predetermined duration, and (b) N/3 or more of the N servers experience faults at some time during the time interval of the requests, the N servers provide responses to the client that are sufficient for the client to determine correct responses to each of the series of requests.

2 more elements

Dependencies are inferred from the claim text.

Byzantine fault tolerance

Life of this patent

Byzantine fault tolerance

Life of this patent

Abstract

Claims12