{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:39:15Z","timestamp":1787337555984,"version":"build-2736575974"},"reference-count":27,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2004,1]]},"abstract":"<jats:p>We study contention-resolution protocols for multiple-access channels. We show that every backoff protocol is transient if the arrival rate, $\\lambda$, is at least 0.42 and that the capacity of every backoff protocol is at most 0.42. Thus, we show that backoff protocols have (provably) smaller capacity than full-sensing protocols. Finally, we show that the corresponding results, with the larger arrival bound of 0.531, also hold for every acknowledgment-based protocol.<\/jats:p>","DOI":"10.1137\/s0097539700381851","type":"journal-article","created":{"date-parts":[[2004,1,27]],"date-time":"2004-01-27T21:00:57Z","timestamp":1075237257000},"page":"313-331","source":"Crossref","is-referenced-by-count":29,"title":["A Bound on the Capacity of Backoff and Acknowledgment-Based Protocols"],"prefix":"10.1137","volume":"33","author":[{"given":"Leslie Ann","family":"Goldberg","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mark","family":"Jerrum","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sampath","family":"Kannan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mike","family":"Paterson","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2012,2,17]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1987.1057295"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1007\/s002240011005"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1979.1056093"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1109\/18.720543"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511984020"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1590"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177728976"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1145\/355541.355567"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1145\/44483.44488"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1145\/23005.23006"},{"key":"R11","volume-title":"Probability and random processes","author":"Grimmett G.","year":"1992"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792233828"},{"key":"R13","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1111\/j.2517-6161.1985.tb01367.x","volume":"47","author":"Kelly F. P.","year":"1985","journal-title":"J. Roy. Statist. Soc. Ser. B"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176991993"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"U. Loher,\n                      Efficiency of first\u2010come first\u2010served algorithms\n                      , in Proceedings of the 1998 IEEE International Symposium on Information Theory, IEEE Information Theory Society, 1998, p. 108.","DOI":"10.1109\/ISIT.1998.708696"},{"key":"R16","unstructured":"U. Loher,\n                      Information\u2010Theoretic and Genie\u2010Aided Analyses of Random\u2010Access Algorithms\n                      , Ph.D. Thesis, DISS ETH 12627, Swiss Federal Institute of Technology, Zurich, 1998."},{"key":"R17","unstructured":"I. M. MacPhee,\n                      On Optimal Strategies in Stochastic Decision Processes\n                      , D. Phil. Thesis, University of Cambridge, Cambridge, UK, 1987."},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1145\/360248.360253"},{"key":"R19","unstructured":"M. Molle and G. C. Polyzos,\n                      Conflict Resolution Algorithms and Their Performance Analysis\n                      , Technical Report CS93\u2010300, Computer Systems Research Institute, University of Toronto, 1993."},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1985.1096261"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814075"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795285333"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"R. Rom and M. Sidi,\n                      Multiple Access Protocols: Performance and Analysis\n                      , Springer\u2010Verlag, New York, 1990.","DOI":"10.1007\/978-1-4612-3402-9"},{"key":"R24","first-page":"64","volume":"23","author":"Tsybakov B.","year":"1987","journal-title":"Problemy Peredachi Informatsii"},{"key":"R25","unstructured":"B. Tsybakov, V. Mikhai\u02d8lov, Free synchronous packet access in a broadcast channel with feedback,  (), 0\u2013081g:94024"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1109\/PROC.1986.13513"},{"key":"R27","unstructured":"N. S. Vvedenskaya and M. S. Pinsker,\n                      Non\u2010optimality of the part\u2010and\u2010try algorithm\n                      , in Abstracts of the International Workshop on Convolutional Codes and Multiuser Communication, Sochi, USSR, 1983, pp. 141\u2013144."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539700381851","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:17:13Z","timestamp":1787336233000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539700381851"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,1]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2004,1]]}},"alternative-id":["10.1137\/S0097539700381851"],"URL":"https:\/\/doi.org\/10.1137\/s0097539700381851","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,1]]}}}