Raising the BAR in dependable cooperative services

Cooperative services--a term which includes any system that relies on the resources and participation of its clients to function--have proven to be a popular, naturally scalable means to disseminate content, distribute computational workloads, or provide network connectivity. However, because these services critically depend on participants that are not controlled by a single administrative domain, these services must be designed to function in environments where no participant--because of failure or selfishness--will necessarily follow the specified protocol. This thesis addresses the challenge of establishing and maintaining cooperation in cooperative services by (1) advancing our understanding of the limits to what our services can guarantee in the presence of failure, (2) demonstrating the critical role that correct participants can play in the incentives provided by the service, and (3) proposing a new notion of equilibrium that, unlike traditional notions, provides both rigorous yet practical guarantees in the presence of collusion. Furthermore, we demonstrate that our ideas can be applied to practice by designing and implementing Seer, a system that provides a scalable, reliable, and robust method for disseminating content even if participants may fail arbitrarily or deviate selfishly as a coalition.