Please use this identifier to cite or link to this item:
Title: Resource-competitive analysis: A new perspective on attack-resistant distributed computing
Authors: Gilbert, S. 
King, V.
Saia, J.
Young, M.
Keywords: Byzantine fault tolerance
Denialof- service attacks
Energy efficiency
Jamming attacks
Resource-competitive analysis
Wireless sensor networks
Issue Date: 2012
Citation: Gilbert, S.,King, V.,Saia, J.,Young, M. (2012). Resource-competitive analysis: A new perspective on attack-resistant distributed computing. Proceedings of the 8th ACM SIGACT/SIGMOBILE International Workshop on Foundations of Mobile Computing, FOMC'12. ScholarBank@NUS Repository.
Abstract: In the spirit of competitive analysis, approximation guarantees, and game-theoretic treatments, we introduce an approach to evaluating the performance of attack-resistant algorithms in distributed systems. This new approach, which we call resource-competitive analysis, is concerned with the worst-case ratio of the cost incurred by an algorithm to the cost incurred by any adversarial strategy. Here, the notion of cost corresponds to any network resource such as bandwidth, computational power, or an onboard energy supply. An adversary who attacks the system is assumed to control and coordinate a large number of Byzantine users that can exhibit arbitrary deviation from any prescribed protocol; in other words, the adversary may select any strategy, whether it be rational or not. In a homogeneous network where all devices, correct and Byzantine, are resource constrained, relative cost is an especially well-motivated metric. An adversary who successfully attacks the system will be penalized by incurring a significantly higher cost than that experienced by correct users. Consequently, the adversary is forced to either (i) cease her malicious behavior or (ii) rapidly deplete the resources of her Byzantine users in perpetrating her attack. For a multitude of well-known distributed denial-of-service (DDoS) scenarios, this type of guarantee can be extremely valuable. Indeed, the utility of this approach has already been demonstrated for settings involving wireless ad-hoc networks where devices are battery powered and, thus, energy-constrained. Ultimately, we believe that resource-competitive analysis constitutes a useful technique for mitigating Byzantine behavior and that this approach to designing attack-resistant algorithms will find application in many other areas of distributed computing. Copyright 2012 ACM.
Source Title: Proceedings of the 8th ACM SIGACT/SIGMOBILE International Workshop on Foundations of Mobile Computing, FOMC'12
ISBN: 9781450315371
DOI: 10.1145/2335470.2335471
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Nov 15, 2018

Page view(s)

checked on Oct 13, 2018

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.