Bankruptcy in Byzantium

In the context of tolerating malicious behavior, the notion of inflicting higher costs on an adversary has appeared in isolated instances in several areas of computer science. This talk will introduce a recent approach for dealing with Byzantine attacks called "resource-competitive analysis' which aims to formalize the concept of imposing prohibitive resource costs on an attacker who seeks to disrupt the functionality of a distributed system. Here, a resource may correspond to computational power, bandwidth, or energy.

In order to provide concrete examples of how this new approach can be applied, I will summarize the results of two previous papers from PODC11 and PODC12 that address the challenge of achieving broadcast in a wireless sensor network in the presence of a jamming adversary. Specifically, in a setting where both correct and Byzantine devices are battery powered, energy is a scarce resource that can be treated as a common currency, and we demonstrate randomized algorithms that guarantee that either (1) broadcast is quickly achieved or (2) the Byzantine devices rapidly deplete their energy supply in attempting to jam communication. In the latter case, the adversary may delay broadcast for a time, but is quickly rendered bankrupt and unable to launch further attacks on the system. The talk will conclude with a discussion of some interesting open problems.

* The work presented in this talk is joint with Seth Gilbert (National University of Singapore), Valerie King (University of Victoria), and Jared Saia (University of New Mexico).