{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:48:38Z","timestamp":1781077718058,"version":"3.54.1"},"reference-count":76,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2018,12,12]],"date-time":"2018-12-12T00:00:00Z","timestamp":1544572800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"AcRF Tier 1","award":["T1 251RES1719"],"award-info":[{"award-number":["T1 251RES1719"]}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF 1763680, CCF 1716252, CCF 1725543, CNS 1755615, CCF 1617618, CCF 1114809, CCF 1217708, CCF 1218188, CCF 1314633, IIS 1247726, IIS 1251137, CNS 1408695, CCF 1439084, CNS-1318294, CCF-1613772, and CNS-1816076"],"award-info":[{"award-number":["CCF 1763680, CCF 1716252, CCF 1725543, CNS 1755615, CCF 1617618, CCF 1114809, CCF 1217708, CCF 1218188, CCF 1314633, IIS 1247726, IIS 1251137, CNS 1408695, CCF 1439084, CNS-1318294, CCF-1613772, and CNS-1816076"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100016299","name":"NetApp","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100016299","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100006234","name":"Sandia National Laboratories","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100006234","id-type":"DOI","asserted-by":"crossref"}]},{"name":"C Spire"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2019,2,28]]},"abstract":"<jats:p>Randomized exponential backoff is a widely deployed technique for coordinating access to a shared resource. A good backoff protocol should, arguably, satisfy three natural properties: (1) it should provide constant throughput, wasting as little time as possible; (2) it should require few failed access attempts, minimizing the amount of wasted effort; and (3) it should be robust, continuing to work efficiently even if some of the access attempts fail for spurious reasons. Unfortunately, exponential backoff has some well-known limitations in two of these areas: it can suffer subconstant throughput under bursty traffic, and it is not robust to adversarial disruption.<\/jats:p>\n          <jats:p>\n            The goal of this article is to \u201cfix\u201d exponential backoff by making it scalable, particularly focusing on the case where processes arrive in an online, worst-case fashion. We present a relatively simple backoff protocol, R\n            <jats:sc>e<\/jats:sc>\n            -B\n            <jats:sc>ackoff<\/jats:sc>\n            , that has, at its heart, a version of exponential backoff. It guarantees expected constant throughput with dynamic process arrivals and requires only an expected polylogarithmic number of access attempts per process.\n          <\/jats:p>\n          <jats:p>\n            R\n            <jats:sc>e<\/jats:sc>\n            -B\n            <jats:sc>ackoff<\/jats:sc>\n            is also robust to periods where the shared resource is unavailable for a period of time. If it is unavailable for\n            <jats:italic>D<\/jats:italic>\n            time slots, R\n            <jats:sc>e<\/jats:sc>\n            -B\n            <jats:sc>ackoff<\/jats:sc>\n            provides the following guarantees. For\n            <jats:italic>n<\/jats:italic>\n            packets, the expected number of access attempts for successfully sending a packet is\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:sup>2<\/jats:sup>\n            (\n            <jats:italic>n<\/jats:italic>\n            +\n            <jats:italic>D<\/jats:italic>\n            )). For the case of an infinite number of packets, we provide a similar result in terms of the maximum number of processes that are ever in the system concurrently.\n          <\/jats:p>","DOI":"10.1145\/3276769","type":"journal-article","created":{"date-parts":[[2018,12,12]],"date-time":"2018-12-12T12:49:32Z","timestamp":1544618972000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["Scaling Exponential Backoff"],"prefix":"10.1145","volume":"66","author":[{"given":"Michael A.","family":"Bender","sequence":"first","affiliation":[{"name":"Stony Brook University, Stony Brook, NY, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jeremy T.","family":"Fineman","sequence":"additional","affiliation":[{"name":"Georgetown University, Washington, DC, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Seth","family":"Gilbert","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Maxwell","family":"Young","sequence":"additional","affiliation":[{"name":"Mississippi State University, MS, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,12,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1987.1057295"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 18th International Colloquium on Structural Information and Communication Complexity (SIROCCO\u201911)","author":"Anantharamu Lakshmi"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10877-8_15"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-013-9816-x"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1400751.1400759"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795288490"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073970.1074023"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/11841036_13"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884482"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897655"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Petra Berenbrink Artur Czumaj Matthias Englert Tom Friedetzky and Lars Nagel. 2012. Multiple-choice balanced allocation in (almost) parallel. In Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques (APPROX-RANDOM\u201912). 411--422.  Petra Berenbrink Artur Czumaj Matthias Englert Tom Friedetzky and Lars Nagel. 2012. Multiple-choice balanced allocation in (almost) parallel. In Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques (APPROX-RANDOM\u201912). 411--422.","DOI":"10.1007\/978-3-642-32512-0_35"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970444435X"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2486159.2486191"},{"key":"e_1_2_1_14_1","unstructured":"Daniel J. Bernstein. 1998. qmail \u2014 An email Message Transfer Agent. Retrieved from http:\/\/cr.yp.to\/qmail.html.  Daniel J. Bernstein. 1998. qmail \u2014 An email Message Transfer Agent. Retrieved from http:\/\/cr.yp.to\/qmail.html."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/49.840210"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2003.1208922"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/358910.358920"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/49.872963"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1979.1094298"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.11.046"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_29"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1011767.1011806"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146381.1146398"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2071379.2071384"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704442726"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/646975.711407"},{"key":"e_1_2_1_27_1","unstructured":"Bryan Costales and Eric Allman. 2002. Sendmail (3rd ed.). O\u2019Reilly.   Bryan Costales and Eric Allman. 2002. Sendmail (3rd ed.). O\u2019Reilly."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087801.3087831"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933057.2933110"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/958491.958508"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1380564.1380571"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/140901.140906"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/165231.166108"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201996)","author":"Goldberg Leslie Ann"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/355541.355567"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/355541.355567"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/44483.44488"},{"key":"e_1_2_1_38_1","unstructured":"Google. 2014. GCM (Google Cloud Messaging) Advanced Topics. Retrieved from http:\/\/developer.android.com\/google\/gcm\/adv.html#retry.  Google. 2014. GCM (Google Cloud Messaging) Advanced Topics. Retrieved from http:\/\/developer.android.com\/google\/gcm\/adv.html#retry."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/23005.23006"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3828.214125"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCOMM.2002.1010617"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792233828"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/165123.165164"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/863955.863968"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/52325.52356"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2767386.2767439"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2755573.2755602"},{"key":"e_1_2_1_48_1","unstructured":"James F. Kurose and Keith Ross. 2002. Computer Networking: A Top-Down Approach Featuring the Internet (2nd ed.). Addison-Wesley Longman Publishing Co. Boston MA.   James F. Kurose and Keith Ross. 2002. Computer Networking: A Top-Down Approach Featuring the Internet (2nd ed.). Addison-Wesley Longman Publishing Co. Boston MA."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2005.845533"},{"key":"e_1_2_1_50_1","volume-title":"Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC\u201905)","author":"Li Yuan","year":"2005"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1137\/140982763"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2017.05.014"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/360248.360253"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.17487\/RFC1129"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.963420"},{"key":"e_1_2_1_56_1","doi-asserted-by":"crossref","unstructured":"Michael Mitzenmacher and Eli Upfal. 2005. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press.   Michael Mitzenmacher and Eli Upfal. 2005. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press.","DOI":"10.1017\/CBO9780511813603"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-0013-1_9"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/1452335.1452338"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-017-0307-1"},{"key":"e_1_2_1_60_1","unstructured":"Google Apps Platform. 2011. Google Documents List API version 3.0: Implementing Exponential Backoff. Retrieved from https:\/\/developers.google.com\/google-apps\/documents-list\/?csw&equals;1#implementing_exponential_backoff.  Google Apps Platform. 2011. Google Documents List API version 3.0: Implementing Exponential Backoff. Retrieved from https:\/\/developers.google.com\/google-apps\/documents-list\/?csw&equals;1#implementing_exponential_backoff."},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225129"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.5555\/299868.299890"},{"key":"e_1_2_1_63_1","volume-title":"Proceedings of the 34th Annual International Symposium on Microarchitecture. 294--305","author":"Rajwar Ravi"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.5555\/1888781.1888804"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2011.8"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/2332432.2332488"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-012-0180-x"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2012.2210241"},{"key":"e_1_2_1_69_1","unstructured":"Amazon Web Services. 2012. Error Retries and Exponential Backoff in AWS. Retrieved from http:\/\/docs.aws.amazon.com\/general\/latest\/gr\/api-retries.html.  Amazon Web Services. 2012. Error Retries and Exponential Backoff in AWS. Retrieved from http:\/\/docs.aws.amazon.com\/general\/latest\/gr\/api-retries.html."},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/55482.55518"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.6028\/jres.108.027"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/792538.792546"},{"key":"e_1_2_1_73_1","volume-title":"Security in Distributed, Grid, Mobile, and Pervasive Computing","author":"Walters John Paul"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215032"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1109\/TWC.2005.850328"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1145\/1062689.1062697"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3276769","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3276769","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3276769","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:03:40Z","timestamp":1750273420000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3276769"}},"subtitle":["Constant Throughput, Polylogarithmic Channel-Access Attempts, and Robustness"],"short-title":[],"issued":{"date-parts":[[2018,12,12]]},"references-count":76,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,2,28]]}},"alternative-id":["10.1145\/3276769"],"URL":"https:\/\/doi.org\/10.1145\/3276769","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,12,12]]},"assertion":[{"value":"2016-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-12-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}