Korman Center, Room 245, 15 S. 33rd Street, Philadelphia, PA 19104
Colloquium: Attack-Resistant Algorithms for Massive Decentralized Networks
Wednesday, October 30, 2013
3:00 PM-4:00 PM
Maxwell Young, PhD, University of Waterloo in Canada
Abstract: The notion of inflicting higher costs on an attacker has appeared in isolated instances in various areas of computer science. This talk will introduce a recent approach for designing and analyzing distributed algorithms which formalizes the concept of imposing prohibitive resource costs on an attacker.
As an example, we consider a scenario where Alice wishes to transmit information to Bob over a communication channel that is vulnerable to disruption by an attacker. There is a cost for accessing the channel (sending, listening, or disrupting) and this cost is measured in terms of network resources such as computational power, bandwidth, or energy. This communication problem abstracts many types of conflict in networks.
For example, in wireless sensor networks, where both the correct and the attacking devices are battery powered, energy is a scarce resource. In this setting, we will see randomized algorithms that guarantee that either (1) communication is quickly achieved, or (2) the attacking devices rapidly deplete their energy supply in attempting to thwart Alice and Bob. In the latter case, the attackers may delay communication for a time, but they are quickly rendered bankrupt and unable to launch further attacks on the system.
These results are joint work with Jared Saia (University of New Mexico), Valerie King (University of Victoria), Seth Gilbert (National University of Singapore), and Seth Pettie (University of Michigan).