Theses     Last modified: 08/27/03 11:56:53 AM

S.W. Smith
Secure Distributed Time for Secure Distributed Protocols
Technical Report CMU-CS-94-177, Department of Computer Science, Carnegie Mellon University
September 1994.

Ph.D. thesis. Advisor: Doug Tygar.


This thesis develops a framework for secure distributed time, and uses this framework to build secure protocols for practical problems. In distributed systems, many important problems-such as detecting potential causality, obtaining global states, and recovering from process failure-center on temporal relations more general than the linear order of real time. Systems with asynchronous message passing require a partial order time model, and systems with multiple levels of abstraction require multiple levels of time models. Building clock primitives for these time models facilitates building protocols for these application problems. However, protocols built (even tacitly) on such clocks open themselves to security and privacy risks, since tracking these temporal relations requires sharing and trusting private information.

This thesis addresses these issues of time and security by constructing a distributed time formalism that supports hierarchies of general time models, and then constructing clock primitives---the Signed Vector Timestamp protocol and the Sealed Vector Timestamp protocol---that provide security and privacy. Framing application problems in terms of this distributed time framework grants insight that often allows us to build protocols more general and flexible than were previously possible. Separating clocks from protocols grants additional flexibility by allowing us to keep their design issues mutually transparent.

This thesis explores three applications of this secure distributed time framework. We transparently add security and privacy to immediate ordered service protocols. We build basic distributed snapshot protocols and transparently add security, privacy, and increased flexibility. Finally, we use the framework to build a new optimistic rollback recovery protocol that substantially improves on previous work by providing full asynchrony while also reducing the worst-case bound for rollbacks after a failure from exponential to one per process; further, developing this protocol within the distributed time framework transparently allows for security and privacy.



See Also

Smith Tygar 1994

Smith Johnson Tygar 1995

Smith Johnson 1996

Back to home page Maintained by Sean Smith,