A “majority consensus” algorithm which represents a new solution to the update synchronization problem for multiple copy databases is presented. The algorithm embodies distributed control and can function effectively in the presence of communication and database site outages. The correctness of the algorithm is demonstrated and the cost of using it is analyzed. Several examples that illustrate aspects of the algorithm operation are included in the Appendix.

The protocol discussed in this paper was developed by many members of the ARPANET community starting in 1969 and continuing through the present. Many individuals and institutions have been members of this community at one time or another over the years. A review of the documents, both working and published, written on the subject of this protocol reveals that the following individuals were among those who contributed to the protocol design: A. Bhushan, R. Braden, R. Bressler, J. Burchfiel, S. Carr, V. Cerf, B. Cosell, D. Crocker, S. Crocker, W. Crowther, J. Davidson, D. Dodds, W. Duvall, G. Grossman, R. Gumpertz, W. Hathaway, W. Kantrowitz, R. Long, J. McConnell, A. McKenzie, R. Merryman, J. Melvin, R. Metcalfe, E. Meyer, N. Mimno, L. Nelson, T. O'Sullivan, M. Padlipsky, K. Pogran, J. Postel, M. Reese, J. Rulifson. R. Schantz, R. Thomas, R. Tomlinson, D. Walden, R. Watson, D. Wells, J. Winett, and S. Wolfe. No doubt others also contributed to the design and dozens of other individuals contributed to the many implementations of the protocol. We acknowledge all of their contributions. Many of the above named individuals were offered an opportunity to collaborate on the writing of this paper. The authors are those who responded. We apologize for the oversight to any individual who would have liked to help write this paper but was not apprised of the opportunity.

Users and administrators of a small computer often desire more service than it can provide. In a network environment additional services can be provided to the small computer, and in turn to the users of the small computer, by one or more other computers. An operational system for providing such “resource sharing” is described; some “fundamental principles” are abstracted from the experience gained in constructing the system; and some generalizations are suggested.