{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,2,2]],"date-time":"2023-02-02T00:11:39Z","timestamp":1675296699330},"reference-count":20,"publisher":"Association for Computing Machinery (ACM)","issue":"6","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2000,11]]},"abstract":"\n We study contention resolution in a multiple-access channel such as the Ethernet channel. In the model that we consider,\n n<\/jats:italic>\n users generate messages for the channel according to a probability distribution. Raghavan and Upfal have given a protocol in which the expected\n delay<\/jats:italic>\n (time to get serviced) of every message is O(log\n n<\/jats:italic>\n ) when messages are generated according to a Bernoulli distribution with generation rate up to about 1\/10. Our main results are the following protocols: (a) one in which the expected average message delay is O(1) when messages are generated according to a Bernoulli distribution with a generation rate smaller than 1\/\n e<\/jats:italic>\n , and (b) one in which the expected delay of any message is O(1) for an analogous model in which users are synchronized (i.e., they agree about the time), there are potentially an infinite number of users, and messages are generated according to a Poisson distribution with generation rate up to 1\/\n e<\/jats:italic>\n . (Each message constitutes a new user.)\n <\/jats:p>\n \n To achieve (a), we first show how to simulate (b) using\n n<\/jats:italic>\n synchronized users, and then show how to build the synchronization into the protocol.\n <\/jats:p>","DOI":"10.1145\/355541.355567","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:26:13Z","timestamp":1027769173000},"page":"1048-1096","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":46,"title":["Contention resolution with constant expected delay"],"prefix":"10.1145","volume":"47","author":[{"given":"Leslie Ann","family":"Goldberg","sequence":"first","affiliation":[{"name":"Univ. of Warwick, Coventry, UK"}]},{"given":"Philip D.","family":"Mackenzie","sequence":"additional","affiliation":[{"name":"Lucent Technologies, Murray Hill, NJ"}]},{"given":"Mike","family":"Paterson","sequence":"additional","affiliation":[{"name":"Univ. of Warwick, Coventry, UK"}]},{"given":"Aravind","family":"Srinivasan","sequence":"additional","affiliation":[{"name":"Lucent Technologies, Murray Hill, NJ"}]}],"member":"320","published-online":{"date-parts":[[2000,11]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"501","volume-title":"The ALOHA system","author":"ABRAMSON N.","unstructured":"ABRAMSON , N. 1973. The ALOHA system . In Computer-Communication Networks. N. Abramson and F. Kuo, Eds., Prentice-Hall , Englewood Cliffs, N.J. , pp. 501 - 517 . ABRAMSON, N. 1973. The ALOHA system. In Computer-Communication Networks. N. Abramson and F. Kuo, Eds., Prentice-Hall, Englewood Cliffs, N.J., pp. 501-517."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1987.1057295"},{"key":"e_1_2_1_3_1","volume-title":"The Probabilistic Method","author":"ALON N.","unstructured":"ALON , N. , SPENCER , J.H. , AND ERDOS , P. 1992. The Probabilistic Method . Wiley-Interscience Series , Wiley, New York. ALON, N., SPENCER,J.H.,AND ERDOS, P. 1992. The Probabilistic Method. Wiley-Interscience Series, Wiley, New York."},{"key":"e_1_2_1_5_1","first-page":"113","volume-title":"Colloq. Math. Soc. Janos Bolyai, A. Hajnal, L. Lovasz, and V. T. Sos Eds.","volume":"52","author":"BOLLOBAS B.","year":"1988","unstructured":"BOLLOBAS , B. 1988 . Martingales, isoperimetric inequalities and random graphs. In Combinatorics , Colloq. Math. Soc. Janos Bolyai, A. Hajnal, L. Lovasz, and V. T. Sos Eds. , Vol. 52 , North-Holland, Amsterdam, The Netherlands , pp. 113 - 139 . BOLLOBAS, B. 1988. Martingales, isoperimetric inequalities and random graphs. In Combinatorics, Colloq. Math. Soc. Janos Bolyai, A. Hajnal, L. Lovasz, and V. T. Sos Eds., Vol. 52, North-Holland, Amsterdam, The Netherlands, pp. 113-139."},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1214\/aoms\/1177729330","article-title":"A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations","volume":"23","author":"CHERNOFF H.","year":"1952","unstructured":"CHERNOFF , H. 1952 . A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations . Ann. Math. Stat. 23 , 493 - 509 . CHERNOFF, H. 1952. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann. Math. Stat. 23, 493-509.","journal-title":"Ann. Math. Stat."},{"key":"e_1_2_1_7_1","first-page":"110","volume-title":"Proceedings of the 5th ACM Symposium on Parallel Algorithms and Architectures (SPAA '93)","author":"DIETZFELBINGER M.","year":"1993","unstructured":"DIETZFELBINGER , M. , AND MEYER AUF DER H EIDE , F. 1993 . Simple, efficient shared memory simulations . In Proceedings of the 5th ACM Symposium on Parallel Algorithms and Architectures (SPAA '93) (Velen, Germany, June 30-July 2). ACM, New York , pp. 110 - 119 . 10.1145\/165231.165246 DIETZFELBINGER, M., AND MEYER AUF DER HEIDE, F. 1993. Simple, efficient shared memory simulations. In Proceedings of the 5th ACM Symposium on Parallel Algorithms and Architectures (SPAA '93) (Velen, Germany, June 30-July 2). ACM, New York, pp. 110-119. 10.1145\/165231.165246"},{"key":"e_1_2_1_8_1","first-page":"41","volume-title":"Proceedings of the 4th ACM Symposium on Parallel Algorithms and Architectures (SPAA '92)","author":"GEREB-GRAUS M.","year":"1992","unstructured":"GEREB-GRAUS , M. , AND TSANTILAS , T. 1992 . Efficient optical communication in parallel computers . In Proceedings of the 4th ACM Symposium on Parallel Algorithms and Architectures (SPAA '92) (San Diego, Calif., June 29-July 1). ACM, New York , pp. 41 - 48 . 10.1145\/140901.140906 GEREB-GRAUS, M., AND TSANTILAS, T. 1992. Efficient optical communication in parallel computers. In Proceedings of the 4th ACM Symposium on Parallel Algorithms and Architectures (SPAA '92) (San Diego, Calif., June 29-July 1). ACM, New York, pp. 41-48. 10.1145\/140901.140906"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793259483"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795290507"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/23005.23006"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792233828"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","article-title":"Probability inequalities for sums of bounded random variables","volume":"58","author":"HOEFFDING W.","year":"1963","unstructured":"HOEFFDING , W. 1963 . Probability inequalities for sums of bounded random variables . Amer. Stat. Assoc. J. 58 , 13 - 30 . IEEE TRANS.INF.THEORY. 1985. IT-31, special issue. HOEFFDING, W. 1963. Probability inequalities for sums of bounded random variables. Amer. Stat. Assoc. J. 58, 13-30. IEEE TRANS.INF.THEORY. 1985. IT-31, special issue.","journal-title":"Amer. Stat. Assoc. J."},{"issue":"3","key":"e_1_2_1_14_1","first-page":"379","article-title":"Stochastic models of computer communication systems","volume":"47","author":"KELLY F. P.","year":"1985","unstructured":"KELLY , F. P. 1985 . Stochastic models of computer communication systems . J. Roy. Stat. Soc. B 47 , 3 , 379 - 395 . KELLY, F. P. 1985. Stochastic models of computer communication systems. J. Roy. Stat. Soc. B 47, 3, 379-395.","journal-title":"J. Roy. Stat. Soc. B"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/274787.274816"},{"key":"e_1_2_1_16_1","first-page":"148","volume-title":"Surveys in Combinatorics","author":"MCDIARMID C.","unstructured":"MCDIARMID , C. 1989. On the method of bounded differences . In Surveys in Combinatorics , London Math . Soc. Lecture Notes Series, Vol. 141 . Cambridge University Press , Cambridge, England, pp. 148 - 188 . MCDIARMID, C. 1989. On the method of bounded differences. In Surveys in Combinatorics, London Math. Soc. Lecture Notes Series, Vol. 141. Cambridge University Press, Cambridge, England, pp. 148-188."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/360248.360253"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1109\/TIT.1981.1056332","article-title":"Bounds on the performance of protocols for a multiple access broadcast channel","author":"PIPPENGER N.","year":"1981","unstructured":"PIPPENGER , N. 1981 . Bounds on the performance of protocols for a multiple access broadcast channel . IEEE Trans. Inf. Theory IT-27 , 145 - 151 . PIPPENGER, N. 1981. Bounds on the performance of protocols for a multiple access broadcast channel. IEEE Trans. Inf. Theory IT-27, 145-151.","journal-title":"IEEE Trans. Inf. Theory IT-27"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795285333"},{"issue":"3","key":"e_1_2_1_20_1","first-page":"64","article-title":"Upper bound on the capacity of a random multiple-access system","volume":"23","author":"TSYBAKOV B.","year":"1987","unstructured":"TSYBAKOV , B. , AND LIKHANOV , N. 1987 . Upper bound on the capacity of a random multiple-access system . Problemy Peredachi Informatsii 23 , 3 , 64 - 78 . TSYBAKOV, B., AND LIKHANOV, N. 1987. Upper bound on the capacity of a random multiple-access system. Problemy Peredachi Informatsii 23, 3, 64-78.","journal-title":"Problemy Peredachi Informatsii"},{"key":"e_1_2_1_21_1","first-page":"141","volume-title":"Abstracts of the International Workshop on Convolutional Codes, Multiuser Communication, Sochi, USSR","author":"VVEDENSKAYA N. D.","year":"1983","unstructured":"VVEDENSKAYA , N. D. , AND PINSKER , M. S. 1983 . Non-optimality of the part-and-try algorithm . In Abstracts of the International Workshop on Convolutional Codes, Multiuser Communication, Sochi, USSR (1983), pp. 141 - 148 . VVEDENSKAYA, N. D., AND PINSKER, M. S. 1983. Non-optimality of the part-and-try algorithm. In Abstracts of the International Workshop on Convolutional Codes, Multiuser Communication, Sochi, USSR (1983), pp. 141-148."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/355541.355567","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,2]],"date-time":"2023-01-02T12:32:51Z","timestamp":1672662771000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/355541.355567"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,11]]},"references-count":20,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2000,11]]}},"alternative-id":["10.1145\/355541.355567"],"URL":"http:\/\/dx.doi.org\/10.1145\/355541.355567","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":["Artificial Intelligence","Hardware and Architecture","Information Systems","Control and Systems Engineering","Software"],"published":{"date-parts":[[2000,11]]},"assertion":[{"value":"2000-11-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}