{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,23]],"date-time":"2025-01-23T05:20:38Z","timestamp":1737609638174,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540677154"},{"type":"electronic","value":"9783540450221"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-45022-x_59","type":"book-chapter","created":{"date-parts":[[2007,11,13]],"date-time":"2007-11-13T23:57:25Z","timestamp":1194998245000},"page":"705-717","source":"Crossref","is-referenced-by-count":3,"title":["A Bound on the Capacity of Backoff and Acknowledgement-Based Protocols"],"prefix":"10.1007","author":[{"given":"Leslie Ann","family":"Goldberg","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mark","family":"Jerrum","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sampath","family":"Kannan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mike","family":"Paterson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,2,18]]},"reference":[{"issue":"2","key":"59_CR1","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1109\/TIT.1987.1057295","volume":"IT-33","author":"D. Aldous","year":"1987","unstructured":"D. Aldous, Ultimate instability of exponential back-off protocol for acknowledgement-based transmission control of random access communication channels, IEEE Trans. Inf. Theory IT-33(2) (1987) 219\u2013233.","journal-title":"IEEE Trans. Inf. Theory"},{"key":"59_CR2","doi-asserted-by":"crossref","unstructured":"H. Al-Ammal, L.A. Goldberg and P. MacKenzie, Binary Exponential Backoff is stable for high arrival rates, To appear in International Symposium on Theoretical Aspects of Computer Science 17 (2000).","DOI":"10.1007\/3-540-46541-3_14"},{"issue":"5","key":"59_CR3","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1109\/TIT.1979.1056093","volume":"IT-25","author":"J.I. Capetanakis","year":"1979","unstructured":"J.I. Capetanakis, Tree algorithms for packet broadcast channels, IEEE Trans. Inf. Theory IT-25(5) (1979) 505\u2013515.","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"6","key":"59_CR4","doi-asserted-by":"publisher","first-page":"2416","DOI":"10.1109\/18.720543","volume":"44","author":"A. Ephremides","year":"1998","unstructured":"A. Ephremides and B. Hajek, Information theory and communication networks: an unconsummated union, IEEE Trans. Inf. Theory 44(6) (1998) 2416\u20132432.","journal-title":"IEEE Trans. Inf. Theory"},{"key":"59_CR5","doi-asserted-by":"crossref","unstructured":"G. Fayolle, V.A. Malyshev, and M.V. Menshikov, Topics in the Constructive Theory of Countable Markov Chains, (Cambridge University Press, 1995).","DOI":"10.1017\/CBO9780511984020"},{"key":"59_CR6","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1006\/jcss.1998.1590","volume":"58","author":"L.A. Goldberg","year":"1999","unstructured":"L.A. Goldberg and P.D. MacKenzie, Analysis of Practical Backoff Protocols for Contention Resolution with Multiple Servers, Journal of Computer and Systems Sciences, 58 (1999) 232\u2013258.","journal-title":"Journal of Computer and Systems Sciences"},{"key":"59_CR7","unstructured":"L.A. Goldberg, P.D. MacKenzie, M. Paterson and A. Srinivasan, Contention resolution with constant expected delay, Pre-print (1999) available at http:\/\/www.dcs.warwick.ac.uk\/~leslie\/pub.html . (Extends a paper by the first two authors in Proc. of the Symposium on Foundations of Computer Science (IEEE) 1997 and a paper by the second two authors in Proc. of the Symposium on Foundations of Computer Science (IEEE) 1995.)"},{"issue":"3","key":"59_CR8","doi-asserted-by":"publisher","first-page":"579","DOI":"10.1145\/44483.44488","volume":"35","author":"J. Goodman","year":"1988","unstructured":"J. Goodman, A.G. Greenberg, N. Madras and P. March, Stability of binary exponential backoff, J. of the ACM, 35(3) (1988) 579\u2013602.","journal-title":"J. of the ACM"},{"issue":"2","key":"59_CR9","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1145\/23005.23006","volume":"34","author":"A.G. Greenberg","year":"1987","unstructured":"A.G. Greenberg, P. Flajolet and R. Ladner, Estimating the multiplicities of conflicts to speed their resolution in multiple access channels, J. of the ACM, 34(2) (1987) 289\u2013325.","journal-title":"J. of the ACM"},{"key":"59_CR10","unstructured":"G.R. Grimmet and D.R. Stirzaker, Probability and Random Processes, Second Edition. (Oxford University Press, 1992)"},{"issue":"4","key":"59_CR11","doi-asserted-by":"publisher","first-page":"740","DOI":"10.1137\/S0097539792233828","volume":"25","author":"J. H\u00e5stad","year":"1996","unstructured":"J. H\u00e5stad, T. Leighton and B. Rogoff, Analysis of backoff protocols for multiple access channels, SIAM Journal on Computing 25(4) (1996) 740\u2013774.","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"59_CR12","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1111\/j.2517-6161.1985.tb01367.x","volume":"47","author":"F.P. Kelly","year":"1985","unstructured":"F.P. Kelly, Stochastic models of computer communication systems, J.R. Statist. Soc. B 47(3) (1985) 379\u2013395.","journal-title":"J.R. Statist. Soc. B"},{"issue":"4","key":"59_CR13","doi-asserted-by":"publisher","first-page":"1557","DOI":"10.1214\/aop\/1176991993","volume":"15","author":"F.P. Kelly","year":"1987","unstructured":"F.P. Kelly and I.M. MacPhee, The number of packets transmitted by collision detect random access schemes, The Annals of Probability, 15(4) (1987) 1557\u20131568.","journal-title":"The Annals of Probability"},{"key":"59_CR14","doi-asserted-by":"crossref","unstructured":"U. Loher, Efficiency of first-come first-served algorithms, Proc. ISIT (1998) 108.","DOI":"10.1109\/ISIT.1998.708696"},{"key":"59_CR15","unstructured":"U. Loher, Information-theoretic and genie-aided analyses of random-access algorithms, PhD Thesis, Swiss Federal Institute of Technology, DISS ETH No. 12627, Zurich (1998)."},{"key":"59_CR16","unstructured":"I.M. MacPhee, On optimal strategies in stochastic decision processes, D. Phil Thesis, University of Cambridge, (1987)."},{"key":"59_CR17","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1145\/360248.360253","volume":"19","author":"R.M. Metcalfe","year":"1976","unstructured":"R.M. Metcalfe and D.R. Boggs, Ethernet: Distributed packet switching for local computer networks. Commun. ACM, 19 (1976) 395\u2013404.","journal-title":"Commun. ACM"},{"key":"59_CR18","unstructured":"M. Molle and G.C. Polyzos, Conflict resolution algorithms and their performance analysis, Technical Report CS93-300, Computer Systems Research Institute, University of Toronto, (1993)."},{"issue":"2","key":"59_CR19","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1109\/TCOM.1985.1096261","volume":"COM-33","author":"J. Mosely","year":"1985","unstructured":"J. Mosely and P.A. Humblet, A class of efficient contention resolution algorithms for multiple access channels, IEEE Trans. on Communications, COM-33(2) (1985) 145\u2013151.","journal-title":"IEEE Trans. on Communications"},{"key":"59_CR20","doi-asserted-by":"crossref","unstructured":"R. Motwani and P. Raghavan, Randomized Algorithms (Cambridge University Press, 1995.)","DOI":"10.1017\/CBO9780511814075"},{"key":"59_CR21","first-page":"229","volume":"24","author":"P. Raghavan","year":"1995","unstructured":"P. Raghavan and E. Upfal, Contention resolution with bounded delay, Proc. of the ACM Symposium on the Theory of Computing 24 (1995) 229\u2013237.","journal-title":"Proc. of the ACM Symposium on the Theory of Computing"},{"key":"59_CR22","doi-asserted-by":"crossref","unstructured":"R. Rom and M. Sidi, Multiple access protocols: performance and analysis, (Springer-Verlag, 1990).","DOI":"10.1007\/978-1-4612-3402-9"},{"issue":"3","key":"59_CR23","first-page":"64","volume":"23","author":"B.S. Tsybakov","year":"1987","unstructured":"B.S. Tsybakov and N. B. Likhanov, Upper bound on the capacity of a random multiple-access system, Problemy Peredachi Informatsii, 23(3) (1987) 64\u201378.","journal-title":"Problemy Peredachi Informatsii"},{"issue":"4","key":"59_CR24","first-page":"259","volume":"14","author":"B.S. Tsybakov","year":"1978","unstructured":"B.S. Tsybakov and V. A. Mikhailov, Free synchronous packet access in a broadcast channel with feedback, Probl. Information Transmission, 14(4) (1978) 259\u2013280.","journal-title":"Probl. Information Transmission"},{"issue":"4","key":"59_CR25","doi-asserted-by":"publisher","first-page":"613","DOI":"10.1109\/PROC.1986.13513","volume":"74","author":"S. Verdu","year":"1986","unstructured":"S. Verdu, Computation of the efficiency of the Mosely-Humblet contention resolution algorithm: a simple method, Proc. of the IEEE 74(4) (1986) 613\u2013614.","journal-title":"Proc. of the IEEE"},{"key":"59_CR26","unstructured":"N.S. Vvedenskaya and M.S. Pinsker, Nonoptimality of the part-and-try algorithm, Abstr. Papers, Int. Workshop \u201cConvolutional Codes; Multi-User Commun.,\u201d Sochi, U.S.S.R, May 30\u2013June 6, 1983, 141\u2013144."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45022-X_59","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,22]],"date-time":"2025-01-22T09:03:38Z","timestamp":1737536618000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45022-X_59"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540677154","9783540450221"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/3-540-45022-x_59","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}