Dynamic Evolution in a Survivable Application Infrastructure

H.D. Thorvaldsson and K.J. Goldman (USA)


Fault tolerant systems, Dynamic evolution, Configurable distributed systems, Byzantine fault tolerance


We describe a highly scalable algorithm for secure sys tem evolution in an infrastructure for widely distributed Byzantine fault-tolerant applications. To maintain high availability, the system and its applications evolve on-line, providing uninterrupted service during installation of up grades. Installations are made to appear atomic with re spect to other installations and application execution steps. Our algorithm guarantees safe installation despite Byzan tine faulty replicas and replica groups. An initial phase pre pares replica groups for an upgrade, while a second phase triggers the installation of the upgrade by gossip among groups. A simple but novel scheme using secret sharing and Byzantine quorums prevents faulty replicas and replica groups from disrupting or maliciously exploiting installa tions. Installation message complexity and computational complexity grow linearly with the number of replicas.

Important Links:

Go Back