Computer Science – Distributed – Parallel – and Cluster Computing
Scientific paper
2012-02-29
Computer Science
Distributed, Parallel, and Cluster Computing
Scientific paper
Consider the general scenario where Alice wishes to transmit a message m to Bob. These two players share a communication channel; however, there exists an adversary, Carol, who aims to prevent the transmission of m by blocking this channel. There are costs to send, receive or block m on the channel, and we ask: How much do Alice and Bob need to spend relative to the adversary Carol in order to guarantee transmission of m? We show that in a time-slotted network with constant costs to send, receive and block m in a slot, if Carol spends a total of B slots trying to block m, then both Alice and Bob must be active for only O(B^{\varphi - 1} + 1)=O(B^{.62}+1) slots in expectation to transmit m, where \varphi = (1 + \sqrt{5})/2 is the golden ratio. Surprisingly, this result holds even if (1) B is unknown to either player; (2) Carol knows the algorithms of both players, but not their random bits; and (3) Carol can attack using total knowledge of past actions of both players. In the spirit of competitive analysis, approximation guarantees, and game-theoretic treatments, our approach represents another notion of relative performance that we call resource competitiveness. This new metric measures the worst-case performance of an algorithm relative to any adversarial strategy and pertains to scenarios where all network devices are resource-constrained. Here, we apply the resource-competitive results above to two concrete problems. First, we consider jamming attacks in WSNs and address the fundamental task of propagating m from a single device to all others in the presence of faults. Second, we examine how to mitigate application-level DDoS attacks in a wired client-server scenario.
King Valerie
Saia Jared
Young Maxwell
No associations
LandOfFree
Resource-Competitive Communication does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Resource-Competitive Communication, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Resource-Competitive Communication will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-523574