{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:48:41Z","timestamp":1781077721544,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":52,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["Graduate Research Fellowship Program Grant"],"award-info":[{"award-number":["Graduate Research Fellowship Program Grant"]}]},{"DOI":"10.13039\/501100001742","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1629\/19"],"award-info":[{"award-number":["1629\/19"]}],"id":[{"id":"10.13039\/501100001742","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100014718","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS 1408695, CNS 1755615, CCF 1439084, CCF 1617618, CCF 1637546, CCF 1716252, CCF 1815316, XPS 1533644"],"award-info":[{"award-number":["CNS 1408695, CNS 1755615, CCF 1439084, CCF 1617618, CCF 1637546, CCF 1716252, CCF 1815316, XPS 1533644"]}],"id":[{"id":"10.13039\/100014718","id-type":"DOI","asserted-by":"publisher"}]},{"name":"BSF","award":["2018364"],"award-info":[{"award-number":["2018364"]}]},{"DOI":"10.13039\/501100006088","name":"Hertz Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100006088","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384305","type":"proceedings-article","created":{"date-parts":[[2020,6,7]],"date-time":"2020-06-07T01:45:25Z","timestamp":1591494325000},"page":"105-118","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Contention resolution without collision detection"],"prefix":"10.1145","author":[{"given":"Michael A.","family":"Bender","sequence":"first","affiliation":[{"name":"Stony Brook University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tsvi","family":"Kopelowitz","sequence":"additional","affiliation":[{"name":"Bar-Ilan University, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"William","family":"Kuszmaul","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Seth","family":"Pettie","sequence":"additional","affiliation":[{"name":"University of Michigan, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","first-page":"11","volume":"802","year":"2016","unstructured":"2016 . IEEE Standard for Information Technology\u2013Telecommunications and Information Exchange Between Systems Local and Metropolitan Area Networks \u2013 Specific Requirements - Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications. IEEE Std 802 . 11 - 2016 (Revision of IEEE Std 802.11-2012), 1\u20133534. 2016. IEEE Standard for Information Technology\u2013Telecommunications and Information Exchange Between Systems Local and Metropolitan Area Networks \u2013 Specific Requirements - Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications. IEEE Std 802.11-2016 (Revision of IEEE Std 802.11-2012), 1\u20133534.","journal-title":"IEEE Std"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1987.1057295"},{"key":"e_1_3_2_1_3_1","volume-title":"Proceedings of the 13th International Conference on Principles of Distributed Systems (OPODIS). 174\u2013188","author":"Anantharamu Lakshmi","unstructured":"Lakshmi Anantharamu , Bogdan S. Chlebus , and Mariusz A. Rokicki . 2009. Adversarial Multiple Access Channel with Individual Injection Rates . In Proceedings of the 13th International Conference on Principles of Distributed Systems (OPODIS). 174\u2013188 . Lakshmi Anantharamu, Bogdan S. Chlebus, and Mariusz A. Rokicki. 2009. Adversarial Multiple Access Channel with Individual Injection Rates. In Proceedings of the 13th International Conference on Principles of Distributed Systems (OPODIS). 174\u2013188."},{"key":"e_1_3_2_1_4_1","volume-title":"Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA. 183\u2013194","author":"William","unstructured":"William C. Anderton and Maxwell Young. 2017. Is Our Model for Contention Resolution Wrong?: Confronting the Cost of Collisions . In Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA. 183\u2013194 . William C. Anderton and Maxwell Young. 2017. Is Our Model for Contention Resolution Wrong?: Confronting the Cost of Collisions. In Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA. 183\u2013194."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-013-9816-x"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1400751.1400759"},{"key":"e_1_3_2_1_7_1","volume-title":"Proceedings of the 17th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 325\u2013332","author":"Bender Michael A.","unstructured":"Michael A. Bender , Martin Farach-Colton , Simai He , Bradley C. Kuszmaul , and Charles E. Leiserson . 2005. Adversarial Contention Resolution for Simple Channels . In Proceedings of the 17th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 325\u2013332 . Michael A. Bender, Martin Farach-Colton, Simai He, Bradley C. Kuszmaul, and Charles E. Leiserson. 2005. Adversarial Contention Resolution for Simple Channels. In Proceedings of the 17th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 325\u2013332."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/11841036_13"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch47"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3276769"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Michael A. Bender Tsci Kopelowitz William Kuszmaul and Seth Pettie. 2020. Contention Resolution without Collision Detection. ArXiv.  Michael A. Bender Tsci Kopelowitz William Kuszmaul and Seth Pettie. 2020. Contention Resolution without Collision Detection. ArXiv.","DOI":"10.1145\/3357713.3384305"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897655"},{"key":"e_1_3_2_1_13_1","unstructured":"D. J. Bernstein. 1998. qmail \u2014 An email Message Transfer Agent. http:\/\/cr.yp.to\/qmail.html  D. J. Bernstein. 1998. qmail \u2014 An email Message Transfer Agent. http:\/\/cr.yp.to\/qmail.html"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/49.840210"},{"key":"e_1_3_2_1_15_1","volume-title":"2nd Symposium on Simplicity in Algorithms (SOSA) (OASICS","volume":"16","author":"Chang Yi-Jun","year":"2019","unstructured":"Yi-Jun Chang , Wenyu Jin , and Seth Pettie . 2019 . Simple Contention Resolution via Multiplicative Weight Updates . In 2nd Symposium on Simplicity in Algorithms (SOSA) (OASICS , Vol. 69). 16:1\u201316: 16 . Yi-Jun Chang, Wenyu Jin, and Seth Pettie. 2019. Simple Contention Resolution via Multiplicative Weight Updates. In 2nd Symposium on Simplicity in Algorithms (SOSA) (OASICS, Vol. 69). 16:1\u201316:16."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055481"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_29"},{"key":"e_1_3_2_1_18_1","volume-title":"Proceedings of 23rd ACM Symposium on Principles of Distributed Computing (PODC). 266\u2013274","author":"Bogdan","unstructured":"Bogdan S. Chlebus and Dariusz R. Kowalski. 2004. A Better Wake-up in Radio Networks . In Proceedings of 23rd ACM Symposium on Principles of Distributed Computing (PODC). 266\u2013274 . Bogdan S. Chlebus and Dariusz R. Kowalski. 2004. A Better Wake-up in Radio Networks. In Proceedings of 23rd ACM Symposium on Principles of Distributed Computing (PODC). 266\u2013274."},{"key":"e_1_3_2_1_19_1","volume-title":"Proc. Twenty-Fifth Annual ACM Symposium on Principles of Distributed Computing (PODC). 92\u2013101","author":"Chlebus Bogdan S.","unstructured":"Bogdan S. Chlebus , Dariusz R. Kowalski , and Mariusz A. Rokicki . 2006. Adversarial queuing on the multiple-access channel . In Proc. Twenty-Fifth Annual ACM Symposium on Principles of Distributed Computing (PODC). 92\u2013101 . Bogdan S. Chlebus, Dariusz R. Kowalski, and Mariusz A. Rokicki. 2006. Adversarial queuing on the multiple-access channel. In Proc. Twenty-Fifth Annual ACM Symposium on Principles of Distributed Computing (PODC). 92\u2013101."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2071379.2071384"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704442726"},{"key":"e_1_3_2_1_22_1","volume-title":"Sendmail","author":"Costales Bryan","unstructured":"Bryan Costales and Eric Allman . 2002. Sendmail ( third ed.). O\u2019Reilly . Bryan Costales and Eric Allman. 2002. Sendmail (third ed.). O\u2019Reilly."},{"key":"e_1_3_2_1_23_1","volume-title":"32nd International Symposium on Distributed Computing (DISC","author":"Marco Gianluca De","year":"2018","unstructured":"Gianluca De Marco , Dariusz R Kowalski , and Grzegorz Stachowiak . 2018 . Brief Announcement: Deterministic Contention Resolution on a Shared Channel . In 32nd International Symposium on Distributed Computing (DISC 2018). Gianluca De Marco, Dariusz R Kowalski, and Grzegorz Stachowiak. 2018. Brief Announcement: Deterministic Contention Resolution on a Shared Channel. In 32nd International Symposium on Distributed Computing (DISC 2018)."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087801.3087831"},{"key":"e_1_3_2_1_25_1","volume-title":"Local Queuing Under Contention. In 32nd International Symposium on Distributed Computing (DISC","author":"Garncarek Pawel","year":"2018","unstructured":"Pawel Garncarek , Tomasz Jurdzinski , and Dariusz R Kowalski . 2018 . Local Queuing Under Contention. In 32nd International Symposium on Distributed Computing (DISC 2018). Pawel Garncarek, Tomasz Jurdzinski, and Dariusz R Kowalski. 2018. Local Queuing Under Contention. In 32nd International Symposium on Distributed Computing (DISC 2018)."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/140901.140906"},{"key":"e_1_3_2_1_27_1","volume-title":"Doubly Logarithmic Communication Algorithms for Optical-Communication Parallel Computers. 26, 4","author":"Goldberg Leslie Ann","year":"1997","unstructured":"Leslie Ann Goldberg , Mark Jerrum , Tom Leighton , and Satish Rao . 1997. Doubly Logarithmic Communication Algorithms for Optical-Communication Parallel Computers. 26, 4 ( 1997 ), Aug., 1100\u20131119. Leslie Ann Goldberg, Mark Jerrum, Tom Leighton, and Satish Rao. 1997. Doubly Logarithmic Communication Algorithms for Optical-Communication Parallel Computers. 26, 4 (1997), Aug., 1100\u20131119."},{"key":"e_1_3_2_1_28_1","volume-title":"MacKenzie","author":"Goldberg Leslie Ann","year":"1996","unstructured":"Leslie Ann Goldberg and Philip D . MacKenzie . 1996 . Analysis of Practical Backoff Protocols for Contention Resolution with Multiple Servers. In Proc. Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 554\u2013563. Leslie Ann Goldberg and Philip D. MacKenzie. 1996. Analysis of Practical Backoff Protocols for Contention Resolution with Multiple Servers. In Proc. Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 554\u2013563."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/355541.355567"},{"key":"e_1_3_2_1_30_1","volume-title":"Oct., 1829\u20131847","author":"Goldberg Leslie Ann","year":"1999","unstructured":"Leslie Ann Goldberg , Yossi Matias , and Satish Rao . 1999 . An Optical Simulation of Shared Memory. 28, 5 (1999) , Oct., 1829\u20131847 . Leslie Ann Goldberg, Yossi Matias, and Satish Rao. 1999. An Optical Simulation of Shared Memory. 28, 5 (1999), Oct., 1829\u20131847."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/44483.44488"},{"key":"e_1_3_2_1_32_1","unstructured":"Google. 2014. GCM (Google Cloud Messaging) Advanced Topics. http:\/\/developer.android.com\/google\/gcm\/adv.html##retry  Google. 2014. GCM (Google Cloud Messaging) Advanced Topics. http:\/\/developer.android.com\/google\/gcm\/adv.html##retry"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/23005.23006"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3828.214125"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792233828"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/165123.165164"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/52325.52356"},{"key":"e_1_3_2_1_38_1","volume-title":"On the method of bounded differences. Surveys in combinatorics, 141, 1","author":"McDiarmid Colin","year":"1989","unstructured":"Colin McDiarmid . 1989. On the method of bounded differences. Surveys in combinatorics, 141, 1 ( 1989 ), 148\u2013188. Colin McDiarmid. 1989. On the method of bounded differences. Surveys in combinatorics, 141, 1 (1989), 148\u2013188."},{"key":"e_1_3_2_1_39_1","first-page":"395","article-title":"Ethernet","volume":"19","author":"Metcalfe Robert M.","year":"1976","unstructured":"Robert M. Metcalfe and David R. Boggs . 1976 . Ethernet : Distributed Packet Switching for Local Computer Networks. Commun. ACM , 19 , 7 (1976), July , 395 \u2013 404 . Robert M. Metcalfe and David R. Boggs. 1976. Ethernet: Distributed Packet Switching for Local Computer Networks. Commun. ACM, 19, 7 (1976), July, 395\u2013404.","journal-title":"Distributed Packet Switching for Local Computer Networks. Commun. ACM"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1452335.1452338"},{"key":"e_1_3_2_1_41_1","volume-title":"Sade: competitive MAC under adversarial SINR. Distributed Computing, 31, 3","author":"Ogierman Adrian","year":"2018","unstructured":"Adrian Ogierman , Andrea Richa , Christian Scheideler , Stefan Schmid , and Jin Zhang . 2018. Sade: competitive MAC under adversarial SINR. Distributed Computing, 31, 3 ( 2018 ), 01 Jun, 241\u2013254. Adrian Ogierman, Andrea Richa, Christian Scheideler, Stefan Schmid, and Jin Zhang. 2018. Sade: competitive MAC under adversarial SINR. Distributed Computing, 31, 3 (2018), 01 Jun, 241\u2013254."},{"key":"e_1_3_2_1_42_1","unstructured":"Google Apps Platform. 2011. Google Documents List API version 3.0: Implementing Exponential Backoff. https:\/\/developers.google.com\/google-apps\/documents-list\/?csw=1##implementing_exponential_backoff  Google Apps Platform. 2011. Google Documents List API version 3.0: Implementing Exponential Backoff. https:\/\/developers.google.com\/google-apps\/documents-list\/?csw=1##implementing_exponential_backoff"},{"key":"e_1_3_2_1_43_1","volume-title":"Stochastic Contention Resolution With Short Delays. 28, 2","author":"Raghavan Prabhakar","year":"1999","unstructured":"Prabhakar Raghavan and Eli Upfal . 1999. Stochastic Contention Resolution With Short Delays. 28, 2 ( 1999 ), April, 709\u2013719. Prabhakar Raghavan and Eli Upfal. 1999. Stochastic Contention Resolution With Short Delays. 28, 2 (1999), April, 709\u2013719."},{"key":"e_1_3_2_1_44_1","volume-title":"Proc. of the 34th Annual Intnl. Symposium on Microarchitecture","author":"Rajwar Ravi","unstructured":"Ravi Rajwar and James R. Goodman . 2001. Speculative Lock Elision: Enabling Highly Concurrent Multithreaded Execution . In Proc. of the 34th Annual Intnl. Symposium on Microarchitecture . Austin, Texas. 294\u2013305. http:\/\/www.cs.wisc.edu\/~rajwar\/papers\/micro01.pdf Ravi Rajwar and James R. Goodman. 2001. Speculative Lock Elision: Enabling Highly Concurrent Multithreaded Execution. In Proc. of the 34th Annual Intnl. Symposium on Microarchitecture. Austin, Texas. 294\u2013305. http:\/\/www.cs.wisc.edu\/~rajwar\/papers\/micro01.pdf"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15763-9_17"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2011.8"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2332432.2332488"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-012-0180-x"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2012.2210241"},{"key":"e_1_3_2_1_50_1","unstructured":"Amazon Web Services. 2012. Error Retries and Exponential Backoff in AWS. http:\/\/docs.aws.amazon.com\/general\/latest\/gr\/api-retries.html  Amazon Web Services. 2012. Error Retries and Exponential Backoff in AWS. http:\/\/docs.aws.amazon.com\/general\/latest\/gr\/api-retries.html"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.6028\/jres.108.027"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215032"}],"event":{"name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","location":"Chicago IL USA","acronym":"STOC '20","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384305","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384305","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384305","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:12Z","timestamp":1750200072000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384305"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":52,"alternative-id":["10.1145\/3357713.3384305","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384305","relation":{},"subject":[],"published":{"date-parts":[[2020,6,22]]},"assertion":[{"value":"2020-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}