Please use this identifier to cite or link to this item: https://doi.org/10.1145/2335470.2335471
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
Source: 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. https://doi.org/10.1145/2335470.2335471
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
URI: http://scholarbank.nus.edu.sg/handle/10635/40394
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.

SCOPUSTM   
Citations

5
checked on Dec 13, 2017

Page view(s)

65
checked on Dec 9, 2017

Google ScholarTM

Check

Altmetric


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