To improve the availability and reliability of files the data are often replicated at several sites. A scheme must then be chosen to maintain the consistency of the file contents in the presence of site failures. The most commonly used scheme is voting. Voting is popular because it is simple and robust: voting schemes do not depend on any sophisticated message passing scheme and are unaffected by network partitions. When network partitions cannot occur, better availabil- ities and reliabilities can be achieved with the available copy scheme. This scheme is somewhat more complex than vot- ing as the recovery algorithm invoked after a failure of all sites has to know which site failed last. We present in this paper a new method aimed at finding this site. It consists of recording those sites which received the most recent up- date; this information can then be used to determine which site holds the most recent version of the file upon site re- covery. Our approach does not require any monitoring of site failures and so has a much lower overhead than other methods. We also derive, under standard Markovian assumptions, closed-form expressions for the availability of replicated files managed by voting, available copy and a naive scheme that does not keep track of the last copy to fail.

Broadcasting protocols can lower the cost of video-on-demand services by more efficiently distributing all videos that are simultaneously watched by many viewers. The most efficient broadcasting protocols require a customer set-top box capable of capturing data from five to seven video channels at the same time. We show how to modify existing broadcasting protocols so that their client bandwidth would never exceed three to four channels and apply our method to the fast broadcasting and the new pagoda broadcasting protocols. Our data show that this modification has only a moderate effect on the overall performance of the two protocols because their server bandwidth never increases by more than 15 percent.

Data are often replicated in distributed systems to protect them against site failures and network malfunctions. When this is the case, an access policy must be chosen to insure that a consistent view of the data is always presented. Voting protocols guarantee consistency of replicated data in the presence of any scenario involving non-Byzantine site failures and network partitions. While Static Majority Consensus Voting protocols use static quorums, Dynamic Voting protocols, like Dynamic Voting and Lexicographic Dynamic Voting, dynamically adjust quorums to changes in the status of the network of sites holding the copies. The availabilities of replicated data managed by these three protocols are compared using a simulation model with realistic parameters. Dynamic Voting is found to perform better than Majority Consensus Voting for all files having more than three copies while Lexicographic Dynamic Voting performs much better than the two other protocols for all eleven configurations under study.

Available copy protocols guarantee the consistency of replicated data objects against any combination of non-Byzantine failures that do not result in partial communication failures. While the original available copy protocol assumed instantaneous detection of failures and instantaneous propagation of this information, more realistic protocols that do not rely on these assumptions have been devised. Two such protocols are investigated in this paper: a naive available copy (NAC) protocol that does not maintain any state information, and an optimistic available copy (OAC) protocol that only maintains state information at write and recovery times. Markov models are used to compare the performance of these two protocols with that of the original available copy protocol. These protocols are shown to perform nearly as well as the original available copy protocol, which is shown to perform much better than quorum consensus protocols. © 1990.

Most broadcasting protocols for video-on-demand do not allow the customer to pause, move fast-forward or backward while watching a video. We propose a broadcasting protocol implementing these features in a purely proactive fashion. Our protocol implements rewind and pause interactions at the set-top box level by requiring the set-top box to keep in its buffer all video data it has received from the server until the customer has finished watching the video. It implements fast-forward by letting the video server transmit video data more frequently than needed by customers watching the video in sequence. As a result, any customer having watched the first x minutes of a video will be able to fast-forward to any scene within the first 2x or 3x minutes of the video. We show that this expanding horizon feature can be provided at a reasonable cost. We also show how our protocol can accommodate customers connected to the service through a device lacking either the ability to receive data at more than two times the video consumption rate or the storage space required to store more than 20 to 25 percent of the video they are watching. While these customers will not have access to any of the interactive features provided by our protocol, they will be able to watch videos after the same wait time as all other customers.

Batch-correlated failures result from the manifestation of a common defect in most, if not all, disk drives belonging to the same production batch. They are much less frequent than random disk failures but can cause catastrophic data losses even in systems that rely on mirroring or erasure codes to protect their data. We propose to reduce impact of batch-correlated failures on disk arrays by storing redundant copies of the same data on disks from different batches and, possibly, different manufacturers. The technique is especially attractive for mirrored organizations as it only requires that the two disks that hold copies of the same data never belong to the same production batch. We also show that even partial diversity can greatly increase the probability that the data stored in a RAID array will survive batch-correlated failures. © 2006 ACM.

Tabbycat is a video server prototype demonstrating the benefits of a proactive approach for distributing popular videos on demand to a large customer base. Rather than reacting to individual customer requests, Tabbycat broadcasts the contents of the most popular videos according to a fixed schedule. As a result, the number of customers watching a given video does not affect the cost of distributing it. We found that one workstation with a single ATA disk drive and a Fast Ethernet interface could distribute three two-hour videos while achieving a maximum customer waiting time of less than four minutes.