Competitive and Fair Throughput for Co-Existing Networks Under Adversarial Interference

Andrea Richa, Christian Scheideler, Stefan Schmid, and Jin Zhang

This paper initiates the formal study of a fundamental problem: How to efficiently allocate a shared communication medium among a set of K co-existing networks in the presence of arbitrary external interference? While most literature on medium access focuses on how to share a medium among nodes, these approaches are often either not directly applicable to co-existing networks as they would violate the independence requirement, or they yield a low throughput if applied to multiple networks. We present the randomized medium access (MAC) protocol COMAC which guarantees that a given communication channel is shared fairly among competing and independent networks, and that the available bandwidth is used efficiently. These performance guarantees hold in the presence of arbitrary external interference or even under adversarial jamming. Concretely, we show that the co-existing networks can use a -fraction of the non-jammed time steps for successful message transmissions, where is the (arbitrarily distributed) fraction of time which is not jammed.


Guest: Andrea Richa
Host: Shantanu Das

Conflict on a Communication Channel

Valerie King, Jared Saia, Maxwell Young

Abstract: Imagine that Alice wants to send a message to Bob, and that Carol wants to prevent this. Assume there is a communication channel between Alice and Bob, but that Carol is capable of blocking this channel. Furthermore, there is a cost of S dollars to send on the channel, L dollars to listen on the channel and B 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 energy and network resources. The problem allows us to quantitatively analyze the economics of information exchange in an adversarial setting and ask: Is communication cheaper than censorship? We answer this question in the affirmative by showing that it is significantly more costly for Carol to block communication of the message than for Alice to communicate it to Bob.

Guest: Valerie King
Host: Yvonne-Anne Pignolet