{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,10]],"date-time":"2025-11-10T21:03:25Z","timestamp":1762808605046,"version":"3.41.0"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2018,4,30]],"date-time":"2018-04-30T00:00:00Z","timestamp":1525046400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"crossref","award":["EP\/G023018\/1"],"award-info":[{"award-number":["EP\/G023018\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100004281","name":"Polish National Science Centre","doi-asserted-by":"crossref","award":["DEC-2012\/07\/B\/ST6\/01534, DEC-2013\/09\/B\/ST6\/01538 and 2016\/22\/E\/ST6\/00499"],"award-info":[{"award-number":["DEC-2012\/07\/B\/ST6\/01534, DEC-2013\/09\/B\/ST6\/01538 and 2016\/22\/E\/ST6\/00499"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2018,4,30]]},"abstract":"<jats:p>\n            We consider the problems of online and stochastic packet queueing in a distributed system of\n            <jats:italic>n<\/jats:italic>\n            nodes with queues, where the communication between the nodes is done via a multiple access channel. In the online setting, in each round, an arbitrary number of packets can be injected to nodes\u2019 queues. Two measures of performance are considered: the total number of packets in all queues, called the\n            <jats:italic>total load<\/jats:italic>\n            , and the maximum queue size, called the\n            <jats:italic>maximum load<\/jats:italic>\n            . We develop a\u00a0deterministic distributed algorithm that is asymptotically optimal with respect to both complexity measures, in a\u00a0competitive way. More precisely, the total load of our algorithm is bigger than the total load of any other algorithm, including centralized online solutions, by only an additive term of\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ), whereas the maximum queue size of our algorithm is at most\n            <jats:italic>n<\/jats:italic>\n            times bigger than the maximum queue size of any other algorithm, with an extra additive\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ). The optimality for both measures is justified by proving the corresponding lower bounds, which also separates nearly exponentially distributed solutions from the centralized ones. Next, we show that our algorithm is also stochastically stable for\n            <jats:italic>any<\/jats:italic>\n            expected injection rate smaller or equal to 1. This is the first solution to the stochastic queueing problem on a multiple access channel that achieves such stability for the (highest possible) rate equal to 1.\n          <\/jats:p>","DOI":"10.1145\/3182396","type":"journal-article","created":{"date-parts":[[2018,5,23]],"date-time":"2018-05-23T15:08:42Z","timestamp":1527088122000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Distributed Online and Stochastic Queueing on a Multiple Access Channel"],"prefix":"10.1145","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2453-7772","authenticated-orcid":false,"given":"Marcin","family":"Bienkowski","sequence":"first","affiliation":[{"name":"University of Wroc\u0142aw, Poland"}]},{"given":"Tomasz","family":"Jurdzinski","sequence":"additional","affiliation":[{"name":"University of Wroc\u0142aw, Poland"}]},{"given":"Miroslaw","family":"Korzeniowski","sequence":"additional","affiliation":[{"name":"Wroc\u0142aw University of Science and Technology"}]},{"given":"Dariusz R.","family":"Kowalski","sequence":"additional","affiliation":[{"name":"University of Liverpool, UK"}]}],"member":"320","published-online":{"date-parts":[[2018,5,22]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365676"},{"volume-title":"Proceedings of the 29th IEEE International Conference on Computer Communications (INFOCOM\u201910)","author":"Anantharamu Lakshmi","key":"e_1_2_1_2_1","unstructured":"Lakshmi Anantharamu , Bogdan S. Chlebus , Dariusz R. Kowalski , and Mariusz A. Rokicki . 2010. Deterministic broadcast on multiple access channels . In Proceedings of the 29th IEEE International Conference on Computer Communications (INFOCOM\u201910) . IEEE, Los Alamitos, CA, 146--150. Lakshmi Anantharamu, Bogdan S. Chlebus, Dariusz R. Kowalski, and Mariusz A. Rokicki. 2010. Deterministic broadcast on multiple access channels. In Proceedings of the 29th IEEE International Conference on Computer Communications (INFOCOM\u201910). IEEE, Los Alamitos, CA, 146--150."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-016-9725-x"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/363647.363677"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-013-9816-x"},{"volume-title":"Online Algorithms: The State of the Art","author":"Aspnes James","key":"e_1_2_1_6_1","unstructured":"James Aspnes . 1998. Competitive analysis of distributed algorithms . In Online Algorithms: The State of the Art , A. Fiat and G. J. Woeginger (Eds.). Springer , New York, NY , 118--146. James Aspnes. 1998. Competitive analysis of distributed algorithms. In Online Algorithms: The State of the Art, A. Fiat and G. J. Woeginger (Eds.). Springer, New York, NY, 118--146."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1014-9"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/49.840210"},{"volume-title":"Online Computation and Competitive Analysis","author":"Borodin Allan","key":"e_1_2_1_9_1","unstructured":"Allan Borodin and Ran El-Yaniv . 1998. Online Computation and Competitive Analysis . Cambridge University Press , New York, NY . Allan Borodin and Ran El-Yaniv. 1998. Online Computation and Competitive Analysis. Cambridge University Press, New York, NY."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/363647.363659"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-3124-8"},{"volume-title":"Handbook on Randomized Computing","author":"Chlebus Bogdan S.","key":"e_1_2_1_12_1","unstructured":"Bogdan S. Chlebus . 2001. Randomized communication in radio networks . In Handbook on Randomized Computing , P. M. Pardalos, S. Rajasekaran, J. H. Reif, and J. D. P. Rolim (Eds.). Kluwer Academic , Dordrecht, Netherlands , 401--456. Bogdan S. Chlebus. 2001. Randomized communication in radio networks. In Handbook on Randomized Computing, P. M. Pardalos, S. Rajasekaran, J. H. Reif, and J. D. P. Rolim (Eds.). Kluwer Academic, Dordrecht, Netherlands, 401--456."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-009-0086-4"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2071379.2071384"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/140982763"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1064-z"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1985.1057022"},{"key":"e_1_2_1_18_1","volume-title":"Retrieved","author":"Goldberg Leslie Ann","year":"2000","unstructured":"Leslie Ann Goldberg . 2000 . Notes on Contention Resolution . Retrieved February 11, 2018, from http:\/\/www.cs.ox.ac.uk\/people\/leslieann.goldberg\/contention.html. Leslie Ann Goldberg. 2000. Notes on Contention Resolution. Retrieved February 11, 2018, from http:\/\/www.cs.ox.ac.uk\/people\/leslieann.goldberg\/contention.html."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1952-0052057-2"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792233828"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-012-0180-x"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3182396","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3182396","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:41:20Z","timestamp":1750282880000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3182396"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,4,30]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,4,30]]}},"alternative-id":["10.1145\/3182396"],"URL":"https:\/\/doi.org\/10.1145\/3182396","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2018,4,30]]},"assertion":[{"value":"2016-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-05-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}