[Busec] BUsec this week: Maxwell Young (Tues 11AM)
goldbe at cs.bu.edu
Mon May 14 13:48:02 EDT 2012
This week, we have Maxwell Young, a visitor from the National
University of Singapore, speaking at our seminar. We meet as usual at
11AM in MCS137, with lunch provided.
Defending a Communication Channel
Maxwell Young. National U of Singapore.
Consider a scenario where Alice wishes to send a message to Bob, but
there is a Byzantine adversary named Carol who aims to prevent this.
Specifically, while there exists a communication channel between Alice
and Bob, Carol is capable of blocking this channel. For each unit of
time, assume that there is a cost of S dollars to send on the channel,
L dollars to listen on the channel and J dollars to block the channel.
How much will Alice and Bob need to spend in order to guarantee
transmission of the message?
This problem abstracts many types of conflict in information networks
including: jamming attacks in wireless networks and distributed
denial-of-service (DDoS) attacks on the Internet, where the costs to
Alice, Bob and Carol represent an expenditure of network resources.
This problem allows us to quantitatively analyze the economics of
information exchange in an adversarial setting and ask: Is
communication cheaper than censorship?
Our work from PODC'11 answers this question in the affirmative by
showing that it is significantly more costly for Carol to prevent
communication of the message than for Alice to communicate it to Bob.
Specifically, if S, L, and J are fixed constants, and Carol spends a
total of T dollars trying to block the message, then Alice and Bob
spend only O(T^(g-1) + 1)=O(T^(0.62)+1) dollars in expectation in
order to successfully communicate, where g = (1+ sqrt(5))/2 is the
golden ratio. In a more generalized scenario, where Alice wish es to
communicate with n neighbors for large n, our recent work in PODC'12
shows that a larger advantage is possible in terms of forcing Carol to
pay a disproportionate cost.
These results find application in wireless sensor networks where
devices are typically battery powered and energy is scarce. In this
context, our work implies that jamming attacks by Byzantine devices
will rapidly deplete their respective on-board power supplies, thus
forcing the malicious devices to cease their interference. In
contrast, any correct devices will survive such attacks and the
receivers will successfully obtain information from a sender.
Joint work with Seth Gilbert (National University of Singapore),
Valerie King (University of Victoria), and Jared Saia (University of
Computer Science, Boston University
More information about the Busec