Paper Info
Title
Resource-Competitive Algorithms
Abstract
The point of adversarial analysis is to model the worst-case performance of an algorithm. Unfortunately, this analysis may not always reect performance in practice because the adversarial assumption can be overly pessimistic. In such cases, several techniques have been developed to provide a more refined understanding of how an algorithm performs e.g., competitive analysis, parameterized analysis, and the theory of approximation algorithms. Here, we describe an analogous technique called resource competitiveness, tailored for distributed systems. Often there is an operational cost for adversarial behavior arising from bandwidth usage, computational power, energy limitations, etc. Modeling this cost provides some notion of how much disruption the adversary can inict on the system. In parameterizing by this cost, we can design an algorithm with the following guarantee: if the adversary pays T, then the additional cost of the algorithm is some function of T. Resource competitiveness yields results pertaining to secure, fault tolerant, and efficient distributed computation. We summarize these results and highlight future challenges where we expect this algorithmic tool to provide new insights.
Year
DOI
Venue
2015
10.1145/2818936.2818949
SIGACT News
Field
DocType
Volume
Adversary model,Computer science,Theoretical computer science,Distributed computing,Approximation algorithm,Mathematical optimization,Parameterized complexity,Combinatorics,Algorithm,Fault tolerance,Bandwidth (signal processing),Adversary,Adversarial system,Competitive analysis
Journal
46
Issue
Citations 
PageRank 
3
5
0.39
References 
Authors
44
8
Name
Order
Citations
PageRank
Michael A. Bender12144138.24
Jeremy T. Fineman258736.10
Mahnush Movahedi3999.31
Jared Saia4101996.95
Varsha Dani543240.05
Seth Gilbert6141394.72
Seth Pettie769247.36
Maxwell Young821017.86