SRI Logo
About Us|R and D Divisions|Careers|Newsroom|Contact Us|SRI Home
     
  SRI Logo

Reconfiguration and Transient Recovery in State-Machine Architectures
 by Dr. John Rushby.

Abstract

We consider an architecture for ultra-dependable operation based on synchronized state machine replication. extended to provide transient recovery and reconfiguration in the presence of Byzantine faults.

The architecture allows processors suspected of being faulty to be placed on "probation." Processors in this status cannot disrupt other processors. but those that are nonfaulty or recovering from transient faults arc able to remain synchronized with the other processors and with each other. can participate in interactively consistent exchange of data (i.e., Byzantine Agreement). and can restore damaged state data by loading majority-voted copies from other processors. The processors that are not on probation are able to coordinate membership of their group and to take processors on and off probation. These properties are achieved even if all the processors on probation and some of the others exhibit Byzantine faults.

Key elements of the architecture are modified treatments for the problems of interactive consistency. clock synchronization, and group membership. Classical algorithms for these problems that tolerate t Byzantine faults among n processors are extended to tolerate t + P faults among n + p processors. partitioned into n "core members" and p "probationers." provided no more then t faults occur among the core members.

Files
 













 

About Us  |  R&D Divisions  |  Careers  |  Newsroom  |  Contact Us
© 2017 SRI International 333 Ravenswood Avenue, Menlo Park, CA 94025-3493
SRI International is an independent, nonprofit corporation. Privacy policy