Byzantine Fault-Tolerant Storage system.

This thesis considers the problem of implementing secure distributed shared storage with atomic semantics in asynchronous systems. It considers a system with an unbounded number of clients (readers and writers) and n servers, ƒ of which can fail arbitrarily. The solution assumes that data is not self-verifying. The thesis considers both wait-free and non wait-free implementations. One main contribution of this work is the introduction of non-skipping timestamps. Unlike timestamps that have traditionally been used in this setting, non-skipping timestamps are guaranteed not to skip any value. This means that non-skipping timestamp will grow logarithmically in the number of write operations in the system and therefore can practically be implemented with a finite number of bits. The thesis gives the definition and provides the first implementation of non-skipping timestamps. By using non-skipping timestamps, this thesis presents a solution to the problem of providing atomic semantics for non self-verifying data in the presence of Byzantine server failures and an unbounded number of clients. The space requirements for readers is O(n), which is a significant improvement over the best previously known solution which requires O(ƒ n) space, where ƒ is the maximum number of faulty servers in the system. The solution has low write-load if ƒ is small compared to n, whereas previously proposed solutions always have a high constant write-load. This thesis presents the first direct bounded wait-free implementation of a replicated register with atomic semantics in a system with an unbounded number of clients and in which up to ƒ servers are subject to Byzantine failures. The message requirements of this wait-free implementations are considerably better in the worst case (for the case of readers) or comparable (for the case of writers) to those of the best known non wait-free implementations. To verify the practicality and correctness, a Byzantine Fault-Tolerant Storage system with atomic semantics is implemented. It tolerates up to ƒ servers Byzantine failures in a system having n ≥ 4ƒ + 1 servers. This thesis describes the implementation techniques, analyzes the performance model, and presents the performance results.