Abstract
Providing high availability and the ability to share data despite the weak connectivity of mobile computing raises the problem of trusting replicated data servers that may be corrupt. This is because servers must be run on portable computers, and these machines are less secure and thus less trustworthy than those traditionally used to run servers. We describe the kinds of problems one must be prepared to deal with, noting that even users of secured, non‐portable computers are at risk if servers trust all authorized peers. We show that high availability through data replication on portable computers need not be mutually exclusive with various levels of data security one might want. We give three solutions to this trust problem for a simple example architecture, achieving progressively higher levels of security with progressively higher costs. We then show how to solve this trust problem for the more complex architecture of Bayou, a weakly consistent replicated data system we built at Xerox PARC.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
F. Cristian, H. Aghili, R. Strong and D. Dolev, Atomic broadcast: From simple message diffusion to byzantine agreement, in: Proceedings of 15th Symposium on Fault Tolerant Computing, Ann Arbor, MI (June 1985) pp. 200–206.
R.A. Golding, A weak-consistency architecture for distributed information services, Computing Systems 5(4) (Fall 1992) 379–405.
R.G. Guy, J.S. Heidemann, W. Mak, T.W. Page, Jr., G.J. Popek and D. Rothmeier, Implementation of the Ficus replicated file system, in: Proceedings of Summer USENIX Conference(June 1990) pp. 63–71.
L. Kalwell Jr., S. Beckhardt, T. Halvorsen, R. Ozzie and I. Greif, Replicated document management in a group communication system, in: Groupware: Software for Computer-Supported Cooperative Work, <nt>eds.</nt> D. Marca and G. Bock (IEEE Computer Society Press, 1992) pp. 226–235.
J.J. Kistler and M. Satyanarayanan, Disconnected operation in the Coda file system, ACM Transactions on Computer Systems 10(1) (February 1992) 3–25.
L. Lamport, R. Shostak and M. Pease, The Byzantine generals problem, ACM Transactions on Programming Languages and Systems 4(3) (July 1982) 382–401.
K. Petersen, M.J. Spreitzer, D.B. Terry, M.M. Theimer and A.J. Demers, Flexible update propagation for weakly consistent replication, in: Proceedings of the 16th ACM Symposium on Operating Systems Principles (SOSP), Saint-Malo, France (October 1997) pp. 288–301.
W. Pugh, Skip lists: a probabilistic alternative to balanced trees, Communications of the ACM 33(6) 668–676.
P. Reiher, Personal communication.
B. Schneier, Applied Cryptography(Wiley, New York, 1996).
D.B. Terry, A.J. Demers, K. Petersen, M.J. Spreitzer, M.M. Theimer and B.B. Welch, Session guarantees for weakly consistent replicated data, in: Proceedings of 3rd International Conference on Parallel and Distributed Information Systems, Austin, TX (September 1994) pp. 140–149.
D.B. Terry, M.M. Theimer, K. Petersen, A.J. Demers, M.J. Spreitzer and C.H. Hauser, Managing update conflicts in Bayou, a weakly connected replicated storage system, in: Proceedings of 15th ACM Symposium on Operating Systems Principles, Copper Mountain, CO (December 1995) pp. 172–183.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Spreitzer, M.J., Theimer, M.M., Petersen, K. et al. Dealing with server corruption in weakly consistent replicated data systems. Wireless Networks 5, 357–371 (1999). https://doi.org/10.1023/A:1019175717085
Issue Date:
DOI: https://doi.org/10.1023/A:1019175717085