Deterring Cheating in Grassroots Systems

Mark Lillibridge

Compaq Systems Research Center

Systems built (mostly) using networked home computers (grassroots systems) have two major advantages over conventional systems: they can tap a huge network of effectively free resources (home users usually have occasional idle disk, CPU, and bandwidth that they've already paid for), and they can be made more resistant to external interference due to their decentralized nature (e.g, Gnutella). Their biggest drawback is their tendency to fall apart due to widespread user cheating.

This drawback can be overcome in many cases through careful system design incorporating ideas from the security community (crypto, digital signatures, secure protocols, interactive proofs, etc.) as well as from economics and game theory (careful choice of incentives, commitment costs). In this talk, I will describe two case studies of how this may be done: a prototype backup system we have built and our proposed solution to how to prevent Gnutella-like systems from clogging up with spam.

Gates 4B (opposite 490), 2/27/01, 4:15 PM