Consider a network where each node is either good or bad. The good nodes all run an algorithm that attempts to achieve a specific goal. The hidden set of bad nodes are controlled by an adversary who uses them to thwart this goal.
Informally, cost-competitive analysis considers the resource cost of each good node as a function of the total resource cost of the adversary. The goal is to design algorithms that achieve their objectives, while minimizing this cost. Critically, when bad nodes suffer higher costs than good nodes, it is expected that they will eventually cease their attack, as their resources become depleted.
Goals of this project are to design cost-competitive algorithms for: communication in wireless networks; tolerating distributed denial-of-service attacks; secure routing in peer-to-peer networks; and enabling nodes to come to agreement.
Cost-competitive analysis offers a novel approach for making progress on challenging attacks that cannot be adequately addressed in models that ignore the costs of the attacker. By adopting a more realistic attack model, this approach more accurately quantifies the limits of efficient attack resistance. It is thus expected that a cost-competitive approach will yield more compelling solutions to security challenges in many domains. In particular, this project may have high impact in security challenges involving open environments such as: wireless sensor networks, overlays, reputation systems; and aspects of contemporary problems in industry such as: public cloud computing, reliable versions of MapReduce, and robust distributed lock managers like Google's Chubby lock service.
