{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:14:05Z","timestamp":1763468045939,"version":"3.41.0"},"reference-count":46,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1016847"],"award-info":[{"award-number":["1016847"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/G023018\/1EP\/H018816\/1"],"award-info":[{"award-number":["EP\/G023018\/1EP\/H018816\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2012,1]]},"abstract":"<jats:p>\n            We study deterministic broadcasting on multiple access channels when packets are injected continuously. The quality of service is considered in the framework of adversarial queuing. An adversary is determined by injection rate and burstiness, the latter denoting the number of packets that can be injected simultaneously in a round. We consider only injection rates that are less than 1. A protocol is stable when the numbers of packets in queues stay bounded at all rounds, and it is of fair latency when waiting times of packets in queues are\n            <jats:italic>O<\/jats:italic>\n            (burstiness\/rate). For channels with collision detection, we give a full-sensing protocol of fair latency for injection rates that are at most 1 2(\u2308lg\n            <jats:italic>n<\/jats:italic>\n            \u2309 + 1), where\n            <jats:italic>n<\/jats:italic>\n            is the number of stations, and show that fair latency is impossible to achieve for injection rates that are\n            <jats:italic>\u03c9<\/jats:italic>\n            (1 log\n            <jats:italic>n<\/jats:italic>\n            ). For channels without collision detection, we present a full-sensing protocol of fair latency for injection rates that are at most 1\n            <jats:italic>c<\/jats:italic>\n            lg\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            , for some\n            <jats:italic>c<\/jats:italic>\n            &gt; 0. We show that there exists an acknowledgment-based protocol that has fair latency for injection rates that are at most 1\n            <jats:italic>cn<\/jats:italic>\n            lg\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            , for some\n            <jats:italic>c<\/jats:italic>\n            &gt; 0, and develop an explicit acknowledgment-based protocol of fair latency for injection rates that are at most 1 27\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ln\n            <jats:italic>n<\/jats:italic>\n            . Regarding impossibility to achieve just stability by restricted protocols, we prove that no acknowledgment-based protocol can be stable for injection rates larger than 3 1 + lg\n            <jats:italic>n<\/jats:italic>\n            .\n          <\/jats:p>","DOI":"10.1145\/2071379.2071384","type":"journal-article","created":{"date-parts":[[2012,1,24]],"date-time":"2012-01-24T16:47:14Z","timestamp":1327423634000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":58,"title":["Adversarial Queuing on the Multiple Access Channel"],"prefix":"10.1145","volume":"8","author":[{"given":"Bogdan S.","family":"Chlebus","sequence":"first","affiliation":[{"name":"University of Colorado Denver"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dariusz R.","family":"Kowalski","sequence":"additional","affiliation":[{"name":"University of Liverpool"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mariusz A.","family":"Rokicki","sequence":"additional","affiliation":[{"name":"University of Liverpool"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,1]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1985.1057021"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1681"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703435522"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/1009385.1010054"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.v45:1"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10877-8_15"},{"volume-title":"Proceedings of the 29th IEEE International Conference on Computer Communications (INFOCOM). 1--5.","author":"Anantharamu L.","key":"e_1_2_1_7_1","unstructured":"Anantharamu , L. , Chlebus , B. S. , Kowalski , D. R. , and Rokicki , M. A . 2010. Deterministic broadcast on multiple access channels . In Proceedings of the 29th IEEE International Conference on Computer Communications (INFOCOM). 1--5. Anantharamu, L., Chlebus, B. S., Kowalski, D. R., and Rokicki, M. A. 2010. Deterministic broadcast on multiple access channels. In Proceedings of the 29th IEEE International Conference on Computer Communications (INFOCOM). 1--5."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276789"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2003.818186"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/363647.363677"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02259748"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073970.1074023"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703426805"},{"volume-title":"Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS). 83--94","author":"Bie\u0144kowski M.","key":"e_1_2_1_14_1","unstructured":"Bie\u0144kowski , M. , Klonowski , M. , Korzeniowski , M. , and Kowalski , D. R . 2010. Dynamic sharing of a multiple access channel . In Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS). 83--94 . Bie\u0144kowski, M., Klonowski, M., Korzeniowski, M., and Kowalski, D. R. 2010. Dynamic sharing of a multiple access channel. In Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS). 83--94."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/363647.363659"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1011767.1011806"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_29"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-009-0086-4"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704442726"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 23rd International Symposium on Distributed Computing (DISC). Lecture Notes in Computer Science","volume":"5805","author":"Czy\u017cowicz J.","unstructured":"Czy\u017cowicz , J. , G\u0105sieniec , L. , Kowalski , D. R. , and Pelc , A . 2009. Consensus and mutual exclusion in a multiple access channel . In Proceedings of the 23rd International Symposium on Distributed Computing (DISC). Lecture Notes in Computer Science , vol. 5805 , Springer-Verlag, 512--526. Czy\u017cowicz, J., G\u0105sieniec, L., Kowalski, D. R., and Pelc, A. 2009. Consensus and mutual exclusion in a multiple access channel. In Proceedings of the 23rd International Symposium on Distributed Computing (DISC). Lecture Notes in Computer Science, vol. 5805, Springer-Verlag, 512--526."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1985.1057022"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700369168"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480100376022"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/355541.355567"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700381851"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3828.214125"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792233828"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms (SODA). 697--704","author":"Indyk P.","year":"2002","unstructured":"Indyk , P. 2002 . Explicit constructions of selectors and related combinatorial structures, with applications . In Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms (SODA). 697--704 . Indyk, P. 2002. Explicit constructions of selectors and related combinatorial structures, with applications. In Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms (SODA). 697--704."},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 13th International Symposium on Algorithms and Computation (ISAAC). Lecture Notes in Computer Science","volume":"2518","author":"Jurdzi\u0144ski T.","unstructured":"Jurdzi\u0144ski , T. and Stachowiak , G . 2002. Probabilistic algorithms for the wakeup problem in single-hop radio networks . In Proceedings of the 13th International Symposium on Algorithms and Computation (ISAAC). Lecture Notes in Computer Science , vol. 2518 , Springer-Verlag, 535--549. Jurdzi\u0144ski, T. and Stachowiak, G. 2002. Probabilistic algorithms for the wakeup problem in single-hop radio networks. In Proceedings of the 13th International Symposium on Algorithms and Computation (ISAAC). Lecture Notes in Computer Science, vol. 2518, Springer-Verlag, 535--549."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/571825.571833"},{"volume-title":"Reversibility and Stochastic Networks","author":"Kelly F. P.","key":"e_1_2_1_31_1","unstructured":"Kelly , F. P. 1979. Reversibility and Stochastic Networks . Wiley . Kelly, F. P. 1979. Reversibility and Stochastic Networks. Wiley."},{"volume-title":"Queueing Systems","author":"Kleinrock L.","key":"e_1_2_1_32_1","unstructured":"Kleinrock , L. 1975-1976. Queueing Systems . Wiley . Kleinrock, L. 1975-1976. Queueing Systems. Wiley."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1985.1057100"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-004-1181-3"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073814.1073843"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794279109"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702413306"},{"volume-title":"Distributed Algorithms","author":"Lynch N. A.","key":"e_1_2_1_38_1","unstructured":"Lynch , N. A. 1996. Distributed Algorithms . Morgan-Kaufmann Publishers . Lynch, N. A. 1996. Distributed Algorithms. Morgan-Kaufmann Publishers."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/360248.360253"},{"key":"e_1_2_1_40_1","doi-asserted-by":"crossref","unstructured":"Mitzenmacher M. and Upfal E. 2005. Probability and Computing. Cambridge University Press. Mitzenmacher M. and Upfal E. 2005. Probability and Computing . Cambridge University Press.","DOI":"10.1017\/CBO9780511813603"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795285333"},{"volume-title":"The New Book of Prime Number Records","author":"Ribenboim P.","key":"e_1_2_1_42_1","unstructured":"Ribenboim , P. 1995. The New Book of Prime Number Records . Springer-Verlag . Ribenboim, P. 1995. The New Book of Prime Number Records. Springer-Verlag."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(02)00312-5"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.22.2.417"},{"volume-title":"An Introduction to Queuing Networks","author":"Walrand J.","key":"e_1_2_1_45_1","unstructured":"Walrand , J. 1988. An Introduction to Queuing Networks . Prentice-Hall . Walrand, J. 1988. An Introduction to Queuing Networks. Prentice-Hall."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215032"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2071379.2071384","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2071379.2071384","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:06:22Z","timestamp":1750241182000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2071379.2071384"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1]]},"references-count":46,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,1]]}},"alternative-id":["10.1145\/2071379.2071384"],"URL":"https:\/\/doi.org\/10.1145\/2071379.2071384","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2012,1]]},"assertion":[{"value":"2008-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-01-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}