Browse Prior Art Database

Weighted Voting for Replicated Data

IP.com Disclosure Number: IPCOM000128886D
Original Publication Date: 1979-Dec-31
Included in the Prior Art Database: 2005-Sep-20
Document File: 13 page(s) / 46K

Publishing Venue

Software Patent Institute

Related People

David K. Gifford: AUTHOR [+3]

Abstract

The requirements of distributed computer systems are stimulating interest in keeping copies of the same information at different nodes in a computer network. Replication of data allows information to be located close to its point of use, either by statically locating copies in high use areas, or by dynamically creating temporary copies as dictated by demand. Replication of data also increases the availability of data, by allowing many nodes to service requests for the same information in parallel, and by masking partial system failures. Thus, in some cases, tile cost of maintaining copies is offset by the performance, communication cost, and reliability benefits that replicated data affords. We present a new algorithm for the maintenance of replicated files. The algorithm can be briefly characterized by the following description: - Every copy of a replicated file is assigned some number of votes. - Every transaction collects a read quorum of r votes to read a file, and a write quorum of w votes to write a file, such that r+w is greater than the total number of votes assigned to the file. 'This ensures that there is a non-null intersection between every read quorum and every write quorum. There is always a subset of the representatives of a file whose votes total to w that are current. - Thus, any read quorum that is gathered is guaranteed to have a current copy.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 8% of the total text.

Page 1 of 13

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Weighted Voting for Replicated Data

by David K. Gifford

CSL-79-14 September, 1979

In a new algorithm for maintaining replicated data, every copy of a replicated file is assigned some number of votes, Every transaction collects a read quorum of r votes to read a file, and a write quorum of w votes to write a file, such that r + w is greater than the total number of votes assigned to the file. This ensures that there is a non-null intersection between every read quorum and every write quorum. Version numbers make it possible to determine which copies are current. The reliability and performance characteristics of a replicated file can be controlled by appropriately choosing r, w, and the file's voting configuration. The algorithm guarantees serial consistency, admits temporary copies in a natural way by the introduction of copies with no votes, and has been implemented in the context of an application system called Violet.

CR Categories: 4.3, 4.35, 4.33, 3.81

Key Words and Phrases: weighted voting, replicated data, quorum, file system, file suite, representative, weak representative, transaction, locking, computer network

David Gifford is a graduate student at Stanford University, and this work was supported in part by the Xerox Corporation and by the Fannie and John Hertz Foundation, This paper was presented at the Seventh Symposium on Operating System Principles on December 12, 1979 in Pacific Grove, California.

XEROX PALO ALTO RESEARCH CENTER

3333 Coyote Hill Road / Palo Alto / California 94304

1. Introduction

The requirements of distributed computer systems are stimulating interest in keeping copies of the same information at different nodes in a computer network. Replication of data allows information to be located close to its point of use, either by statically locating copies in high use areas, or by dynamically creating temporary copies as dictated by demand. Replication of data also increases the availability of data, by allowing many nodes to service requests for the same information in parallel, and by masking partial system failures. Thus, in some cases, tile cost of maintaining copies is offset by the performance, communication cost, and reliability benefits that replicated data affords. We present a new algorithm for the maintenance of replicated files. The algorithm can be briefly characterized by the following description:

- Every copy of a replicated file is assigned some number of votes.

- Every transaction collects a read quorum of r votes to read a file, and a write quorum of w votes to write a file, such that r+w is greater than the total number of votes assigned to the file.

Xerpx Palo Alto Research Center Page 1 Dec 31, 1979

Page 2 of 13

Weighted Voting for Replicated Data

'This ensures that there is a non-null intersection between every read quorum and every write quorum. There is always a subset of the representatives of a file whose votes tota...