{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T14:38:37Z","timestamp":1773931117006,"version":"3.50.1"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2015,9,1]],"date-time":"2015-09-01T00:00:00Z","timestamp":1441065600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGACT News"],"published-print":{"date-parts":[[2015,9]]},"abstract":"<jats:p>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.<\/jats:p>\n          <jats:p>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.<\/jats:p>\n          <jats:p>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.<\/jats:p>","DOI":"10.1145\/2818936.2818949","type":"journal-article","created":{"date-parts":[[2015,9,8]],"date-time":"2015-09-08T12:36:15Z","timestamp":1441715775000},"page":"57-71","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["Resource-Competitive Algorithms"],"prefix":"10.1145","volume":"46","author":[{"given":"Michael A.","family":"Bender","sequence":"first","affiliation":[{"name":"Stony Brook University, Stony Brook, NY, USA"}]},{"given":"Jeremy T.","family":"Fineman","sequence":"additional","affiliation":[{"name":"Georgetown University, Washington, DC, USA"}]},{"given":"Mahnush","family":"Movahedi","sequence":"additional","affiliation":[{"name":"University of New Mexico, Albuquerque, NM, USA"}]},{"given":"Jared","family":"Saia","sequence":"additional","affiliation":[{"name":"University of New Mexico, Albuquerque, NM, USA"}]},{"given":"Varsha","family":"Dani","sequence":"additional","affiliation":[{"name":"University of New Mexico, Albuquerque, NM, USA"}]},{"given":"Seth","family":"Gilbert","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore"}]},{"given":"Seth","family":"Pettie","sequence":"additional","affiliation":[{"name":"University of Michigan, Ann Arbor, MI, USA"}]},{"given":"Maxwell","family":"Young","sequence":"additional","affiliation":[{"name":"Mississippi State University, Starkville, MS, USA"}]}],"member":"320","published-online":{"date-parts":[[2015,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1095810.1095817"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1998037.1998055"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1095810.1095816"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICC.2007.550"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1400751.1400759"},{"key":"e_1_2_1_6_1","unstructured":"Michael Bender Jeremy Fineman Seth Gilbert and Maxwell Young. How to Scale Exponential Backoff. http:\/\/arxiv.org\/abs\/1402.5207 2014.  Michael Bender Jeremy Fineman Seth Gilbert and Maxwell Young. How to Scale Exponential Backoff. http:\/\/arxiv.org\/abs\/1402.5207 2014."},{"key":"e_1_2_1_7_1","first-page":"80","volume-title":"Proceedings of the 6th International Workshop on Algorithms and Data Structures (WADS)","author":"Michael","year":"1999"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073970.1074023"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(00)00089-2"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxm037"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.39"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.33"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993659"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TDSC.2008.11"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/1060289.1060317"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/571637.571640"},{"key":"e_1_2_1_17_1","first-page":"442","volume-title":"Chalasani and James M. Conrad. A Survey of Energy Harvesting Sources for Embedded Systems. In Proceedings of IEEE Southeastcon","author":"Sravanthi","year":"2008"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2071379.2071384"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281100.1281172"},{"key":"e_1_2_1_20_1","volume-title":"Spread the Word: Reliable Tor Bridge Distribution. Available at: http:\/\/cs.unm.edu\/~zamani\/papers\/tor-bridges","author":"Crandall Jed","year":"2015"},{"key":"e_1_2_1_21_1","unstructured":"Johannes Dams Martin Hoefer and Thomas Kesselheim. Jamming-Resistant Learning in Wireless Networks. http:\/\/arxiv.org\/abs\/1307.5290 2013.  Johannes Dams Martin Hoefer and Thomas Kesselheim. Jamming-Resistant Learning in Wireless Networks. http:\/\/arxiv.org\/abs\/1307.5290 2013."},{"key":"e_1_2_1_22_1","first-page":"575","volume-title":"Maxwell Young. Interactive Communication with Unknown Noise Rate. In Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP)","author":"Dani Varsha","year":"2015"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1976.1055638"},{"key":"e_1_2_1_24_1","first-page":"208","volume-title":"Proceedings of the International Symposium on Distributed Computing (DISC)","author":"Dolev Shlomi","year":"2007"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1400751.1400767"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-12450-1_10"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/646757.705669"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-41527-2_23"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3149.214121"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1315245.1315292"}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2818936.2818949","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2818936.2818949","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:07:17Z","timestamp":1750223237000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2818936.2818949"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,9]]},"references-count":30,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,9]]}},"alternative-id":["10.1145\/2818936.2818949"],"URL":"https:\/\/doi.org\/10.1145\/2818936.2818949","relation":{},"ISSN":["0163-5700"],"issn-type":[{"value":"0163-5700","type":"print"}],"subject":[],"published":{"date-parts":[[2015,9]]},"assertion":[{"value":"2015-09-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}