Check out the new USENIX Web site. next up previous
Next: 3.2.2 Exploiting the grace Up: 3.2 Free-rider attacks Previous: 3.2 Free-rider attacks


3.2.1 Agreement violations

The most basic free-rider attack against our scheme is for an attacker to intentionally fail to uphold his end of his agreements. For example, under our simplified scheme a computer could free ride by letting its partners backup its data but refuse to hold their data in turn; this would give the computer backup service at essentially no cost to itself.

To prevent such attacks, participating computers should police their agreements by verifying whether or not their partners are honoring their promises. Each computer can periodically challenge each of their partners to make sure that the partner in question is up when promised and continuing to hold the data it agreed to hold.

Such a challenge might consist of a request for the block of the challenger's data stored at a challenger-chosen random offset; the answer would then be checked to make sure it is a valid block that belongs on that partner at that offset. Optionally, the block's version number could also be checked to make sure it is the most recent version. Because a partner who holds only fraction $d$ of the challenger's data will pass $c$ challenges with probability $d^c$, by challenging frequently enough, the challenger can be assured with high probably that its partner is still holding almost all of its data.

While a challenge remains pending (i.e., not yet answered correctly), the challenger should keep retrying it until either it is answered correctly or the partner claims data loss (aka, needs restoration). After a computer has restored its data, it signals its partners, who then reload their data (empty blocks until their cleaners have a chance to run) on it and resume challenging it. The time the challenger spends waiting for an answer should be counted as downtime for that partner. Partners who are down too often (relative to their uptime-level agreement) or need restoration too often should be forever abandoned in favor of a new partner.

Unfortunately, a crashed computer looks just like a cheating one that is trying to dodge a challenge it cannot answer--both do not respond to requests. If computers using our scheme abandoned partners (discarding their backup data) as soon as they were clearly down more than their uptime agreements allow (say, 8 hours for a strict 100% agreement), our backup service would not be very useful because backups would likely be discarded before computer owners realized they were needed.

Accordingly, we suggest allowing a grace period of two weeks: partners should not be abandoned until two weeks have passed since they first went down excessively. We recommend two weeks to cover the case where a machine crashes, losing data, just after the owner leaves on a two week vacation.


next up previous
Next: 3.2.2 Exploiting the grace Up: 3.2 Free-rider attacks Previous: 3.2 Free-rider attacks
Mark Lillibridge 2003-04-07