{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:14:51Z","timestamp":1761621291627,"version":"3.41.0"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2016,11,28]],"date-time":"2016-11-28T00:00:00Z","timestamp":1480291200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2016,11,28]],"date-time":"2016-11-28T00:00:00Z","timestamp":1480291200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["0310503","1016847"],"award-info":[{"award-number":["0310503","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\/1"],"award-info":[{"award-number":["EP\/G023018\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2017,10]]},"DOI":"10.1007\/s00224-016-9725-x","type":"journal-article","created":{"date-parts":[[2016,11,28]],"date-time":"2016-11-28T00:34:50Z","timestamp":1480293290000},"page":"820-850","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Adversarial Multiple Access Channels with Individual Injection Rates"],"prefix":"10.1007","volume":"61","author":[{"given":"Lakshmi","family":"Anantharamu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4884-941X","authenticated-orcid":false,"given":"Bogdan S.","family":"Chlebus","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mariusz A.","family":"Rokicki","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,11,28]]},"reference":[{"issue":"2","key":"9725_CR1","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1109\/TIT.1985.1057021","volume":"31","author":"NM Abramson","year":"1985","unstructured":"Abramson, N.M.: Development of the ALOHANET. IEEE Trans. Inf. Theory 31(2), 119\u2013123 (1985)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"1","key":"9725_CR2","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1002\/net.20044","volume":"45","author":"C \u00c0lvarez","year":"2005","unstructured":"\u00c0lvarez, C., Blesa, M.J., D\u00edaz, J., Serna, M.J., Fern\u00e1ndez, A.: Adversarial models for priority-based networks. Networks 45(1), 23\u201335 (2005)","journal-title":"Networks"},{"key":"9725_CR3","doi-asserted-by":"crossref","unstructured":"\u00c0lvarez, C., Blesa, M.J., Serna, M.J.: The impact of failure management on the stability of communication networks. In: Proceedings of the 10th IEEE International Conference on Parallel and Distributed Systems (ICPADS), pp. 153\u2013160. IEEE (2004)","DOI":"10.1109\/ICPADS.2004.1316091"},{"key":"9725_CR4","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/j.tcs.2015.03.034","volume":"584","author":"L Anantharamu","year":"2015","unstructured":"Anantharamu, L., Chlebus, B.S.: Broadcasting in ad hoc multiple access channels. Theor. Comput. Sci. 584, 155\u2013176 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"9725_CR5","doi-asserted-by":"crossref","unstructured":"Anantharamu, L., Chlebus, B.S., Kowalski, D.R., Rokicki, M.A.: Deterministic broadcast on multiple access channels. In: Proceedings of the 29th IEEE International Conference on Computer Communications (INFOCOM), pp. 1\u20135. IEEE (2010)","DOI":"10.1109\/INFCOM.2010.5462256"},{"key":"9725_CR6","doi-asserted-by":"crossref","unstructured":"Anantharamu, L., Chlebus, B.S., Kowalski, D.R., Rokicki, M.A.: Medium access control for adversarial channels with jamming. In: Proceedings of the 18th International Colloquium on Structural Information and Communication Complexity (SIROCCO), Lecture Notes in Computer Science, vol. 6796, pp. 89-100. Springer (2011)","DOI":"10.1007\/978-3-642-22212-2_9"},{"key":"9725_CR7","doi-asserted-by":"crossref","unstructured":"Anantharamu, L., Chlebus, B.S., Rokicki, M.A.: Adversarial multiple access channel with individual injection rates. In: Proceedings of the 13th International Conference on Principles of Distributed Systems (OPODIS), Lecture Notes in Computer Science, vol. 5923, pp. 174\u2013188. Springer (2009)","DOI":"10.1007\/978-3-642-10877-8_15"},{"issue":"1","key":"9725_CR8","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1145\/363647.363677","volume":"48","author":"M Andrews","year":"2001","unstructured":"Andrews, M., Awerbuch, B., Fern\u00e1ndez, A., Leighton, F.T., Liu, Z., Kleinberg, J.M.: Universal-stability results and performance bounds for greedy contention-resolution protocols. J. ACM 48(1), 39\u201369 (2001)","journal-title":"J. ACM"},{"key":"9725_CR9","doi-asserted-by":"crossref","unstructured":"Andrews, M., Zhang, L.: Stability results for networks with input and output blocking. In: Proceedings of the 30th ACM Symposium on the Theory of Computing (STOC), pp. 369\u2013377. ACM (1998)","DOI":"10.1145\/276698.276789"},{"issue":"5","key":"9725_CR10","doi-asserted-by":"publisher","first-page":"848","DOI":"10.1109\/TNET.2003.818186","volume":"11","author":"M Andrews","year":"2003","unstructured":"Andrews, M., Zhang, L.: Achieving stability in networks of input-queued switches. IEEE\/ACM Trans. Netw. 11(5), 848\u2013857 (2003)","journal-title":"IEEE\/ACM Trans. Netw."},{"issue":"3","key":"9725_CR11","doi-asserted-by":"publisher","first-page":"Article 33","DOI":"10.1145\/1273340.1273349","volume":"3","author":"M Andrews","year":"2007","unstructured":"Andrews, M., Zhang, L.: Routing and scheduling in multihop wireless networks with time-varying channels. ACM Trans. Algorithm. 3(3), Article 33 (2007)","journal-title":"ACM Trans. Algorithm."},{"key":"9725_CR12","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Richa, A.W., Scheideler, C.: A jamming-resistant MAC protocol for single-hop wireless networks. In: Proceedings of the 27th ACM Symposium on Principles of Distributed Computing (PODC), pp. 45\u201354. ACM (2008)","DOI":"10.1145\/1400751.1400759"},{"key":"9725_CR13","doi-asserted-by":"crossref","unstructured":"Bender, M.A., Farach-Colton, M., He, S., Kuszmaul, B.C., Leiserson, C.E.: Adversarial contention resolution for simple channels. In: Proceedings of the 17th ACM Symposium on Parallel Algorithms (SPAA), pp. 325\u2013332. ACM (2005)","DOI":"10.1145\/1073970.1074023"},{"key":"9725_CR14","doi-asserted-by":"crossref","unstructured":"Bender, M.A., Fineman, J.T., Gilbert, S., Young, M.: How to scale exponential backoff: Constant throughput, polylog access attempts, and robustness. In: Proceedings of the 27th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 636\u2013654. SIAM (2016)","DOI":"10.1137\/1.9781611974331.ch47"},{"issue":"2","key":"9725_CR15","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1137\/S0097539703426805","volume":"34","author":"R Bhattacharjee","year":"2005","unstructured":"Bhattacharjee, R., Goel, A., Lotker, Z.: Instability of FIFO at arbitrarily low rates in the adversarial queueing model. SIAM J. Comput. 34(2), 318\u2013332 (2005)","journal-title":"SIAM J. Comput."},{"key":"9725_CR16","unstructured":"Bie\u0144kowski, M., Klonowski, M., Korzeniowski, M., Kowalski, D.R.: Dynamic sharing of a multiple access channel. In: Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS), Leibniz International Proceedings in Informatics, vol. 5, pp. 83\u201394. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik (2010)"},{"issue":"3","key":"9725_CR17","doi-asserted-by":"publisher","first-page":"304","DOI":"10.1007\/s00224-007-9046-1","volume":"44","author":"MJ Blesa","year":"2009","unstructured":"Blesa, M.J., Calzada, D., Fern\u00e1ndez, A., L\u00f3pez, L., Mart\u00ednez, A.L., Santos, A., Serna, M.J., Thraves, C.: Adversarial queueing model for continuous network dynamics. Theory Comput. Syst. 44(3), 304\u2013331 (2009)","journal-title":"Theory Comput. Syst."},{"issue":"1","key":"9725_CR18","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1145\/363647.363659","volume":"48","author":"A Borodin","year":"2001","unstructured":"Borodin, A., Kleinberg, J.M., Raghavan, P., Sudan, M., Williamson, D.P.: Adversarial queuing theory. J. ACM 48(1), 13\u201338 (2001)","journal-title":"J. ACM"},{"key":"9725_CR19","doi-asserted-by":"crossref","unstructured":"Chlebus, B.S.: Randomized communication in radio networks. In: Pardalos, P.M., Rajasekaran, S., Reif, J.H., Rolim, J.D.P. (eds.) Handbook of Randomized Computing, volume I, pp. 401\u2013456. Kluwer Academic Publishers (2001)","DOI":"10.1007\/978-1-4615-0013-1_11"},{"issue":"6","key":"9725_CR20","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1007\/s00446-005-0153-4","volume":"18","author":"BS Chlebus","year":"2006","unstructured":"Chlebus, B.S., Kowalski, D.R., Lingas, A.: Performing work in broadcast networks. Distrib. Comput. 18(6), 435\u2013451 (2006)","journal-title":"Distrib. Comput."},{"issue":"2","key":"9725_CR21","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/s00446-009-0086-4","volume":"22","author":"BS Chlebus","year":"2009","unstructured":"Chlebus, B.S., Kowalski, D.R., Rokicki, M.A.: Maximum throughput of multiple access channels in adversarial environments. Distrib. Comput. 22(2), 93\u2013116 (2009)","journal-title":"Distrib. Comput."},{"issue":"1","key":"9725_CR22","doi-asserted-by":"crossref","first-page":"5:15:31","DOI":"10.1145\/2071379.2071384","volume":"8","author":"BS Chlebus","year":"2012","unstructured":"Chlebus, B.S., Kowalski, D.R., Rokicki, M.A.: Adversarial queuing on the multiple access channel. ACM Trans. Algorithm. 8(1), 5:15:31 (2012)","journal-title":"ACM Trans. Algorithm."},{"issue":"15","key":"9725_CR23","doi-asserted-by":"publisher","first-page":"4460","DOI":"10.1016\/j.comnet.2007.07.001","volume":"51","author":"V Cholvi","year":"2007","unstructured":"Cholvi, V., Echag\u00fce, J.: Stability of FIFO networks under adversarial models State of the art. Comput. Netw. 51(15), 4460\u20134474 (2007)","journal-title":"Comput. Netw."},{"key":"9725_CR24","doi-asserted-by":"crossref","unstructured":"Clementi, A.E.F., Monti, A., Silvestri, R.: Optimal F-reliable protocols for the Do-All problem on single-hop wireless networks. In: Proceedings of the 13th International Symposium on Algorithms and Computation (ISAAC), Lecture Notes in Computer Science, vol. 2518, pp. 320-331. Springer (2002)","DOI":"10.1007\/3-540-36136-7_29"},{"issue":"7","key":"9725_CR25","doi-asserted-by":"publisher","first-page":"1092","DOI":"10.1109\/TPDS.2010.162","volume":"22","author":"J Czy\u017bowicz","year":"2011","unstructured":"Czy\u017bowicz, J., Gasieniec, L., Kowalski, D.R., Pelc, A.: Consensus and mutual exclusion in a multiple access channel. IEEE Trans. Parallel Distrib. Syst. 22 (7), 1092\u20131104 (2011)","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"9725_CR26","doi-asserted-by":"crossref","unstructured":"De Marco, G., Kowalski, D.R.: Contention resolution in a non-synchronized multiple access channel. In: Proceedings of the 27th IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp. 525\u2013533. IEEE (2013)","DOI":"10.1109\/IPDPS.2013.68"},{"issue":"8","key":"9725_CR27","doi-asserted-by":"publisher","first-page":"898","DOI":"10.1016\/j.dam.2006.08.009","volume":"155","author":"G De Marco","year":"2007","unstructured":"De Marco, G., Pellegrini, M., Sburlati, G.: Faster deterministic wakeup in multiple access channels. Discret. Appl. Math. 155(8), 898\u2013903 (2007)","journal-title":"Discret. Appl. Math."},{"key":"9725_CR28","doi-asserted-by":"crossref","unstructured":"Dolev, S., Gilbert, S., Guerraoui, R., Kuhn, F., Newport, C.C.: The wireless synchronization problem. In: Proceedings of the 28th ACM Symposium on Principles of Distributed Computing (PODC), pp. 190\u2013199. ACM (2009)","DOI":"10.1145\/1582716.1582749"},{"key":"9725_CR29","doi-asserted-by":"crossref","unstructured":"Dolev, S., Gilbert, S., Guerraoui, R., Newport, C.C.: Gossiping in a multi-channel radio network. In: Proceedings of the 21th International Symposium on Distributed Computing (DISC), Lecture Notes in Computer Science, vol. 4731, pp. 208\u2013222. Springer (2007)","DOI":"10.1007\/978-3-540-75142-7_18"},{"issue":"2","key":"9725_CR30","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1109\/TIT.1985.1057022","volume":"31","author":"RG Gallager","year":"1985","unstructured":"Gallager, R.G.: A perspective on multiaccess channels. IEEE Trans. Inf. Theory 31(2), 124\u2013142 (1985)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"2","key":"9725_CR31","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1137\/S0895480100376022","volume":"14","author":"L Gasieniec","year":"2001","unstructured":"Gasieniec, L., Pelc, A., Peleg, D.: The wakeup problem in synchronous broadcast systems. SIAM J. Discret. Math. 14(2), 207\u2013222 (2001)","journal-title":"SIAM J. Discret. Math."},{"key":"9725_CR32","doi-asserted-by":"crossref","unstructured":"Gilbert, S., Guerraoui, R., Kowalski, D.R., Newport, C.C.: Interference-resilient information exchange. In: Proceedings of the 28th IEEE International Conference on Computer Communications (INFOCOM), pp. 2249\u20132257. IEEE (2009)","DOI":"10.1109\/INFCOM.2009.5062150"},{"issue":"6-7","key":"9725_CR33","doi-asserted-by":"publisher","first-page":"546","DOI":"10.1016\/j.tcs.2008.10.008","volume":"410","author":"S Gilbert","year":"2009","unstructured":"Gilbert, S., Guerraoui, R., Newport, C.C.: Of Malicious motes and suspicious sensors: On the efficiency of Malicious interference in wireless networks. Theor. Comput. Sci. 410(6-7), 546\u2013569 (2009)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"9725_CR34","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1137\/S0097539700381851","volume":"33","author":"LA Goldberg","year":"2004","unstructured":"Goldberg, L.A., Jerrum, M., Kannan, S., Paterson, M.: A bound on the capacity of backoff and acknowledgment-based protocols. SIAM J. Comput. 33(2), 313\u2013331 (2004)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"9725_CR35","doi-asserted-by":"publisher","first-page":"1048","DOI":"10.1145\/355541.355567","volume":"47","author":"LA Goldberg","year":"2000","unstructured":"Goldberg, L.A., MacKenzie, P.D., Paterson, M., Srinivasan, A.: Contention resolution with constant expected delay. J. ACM 47(6), 1048\u20131096 (2000)","journal-title":"J. ACM"},{"issue":"3","key":"9725_CR36","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1145\/3828.214125","volume":"32","author":"AG Greenberg","year":"1985","unstructured":"Greenberg, A.G., Winograd, S.: A lower bound on the time needed in the worst case to resolve conflicts deterministically in multiple access channels. J. ACM 32(3), 589\u2013596 (1985)","journal-title":"J. ACM"},{"issue":"4","key":"9725_CR37","doi-asserted-by":"publisher","first-page":"740","DOI":"10.1137\/S0097539792233828","volume":"25","author":"J H\u00e5stad","year":"1996","unstructured":"H\u00e5stad, J., Leighton, F.T., Rogoff, B.: Analysis of backoff protocols for multiple access channels. SIAM J. Comput. 25(4), 740\u2013774 (1996)","journal-title":"SIAM J. Comput."},{"key":"9725_CR38","doi-asserted-by":"crossref","unstructured":"Jurdzi\u0144ski, T., Stachowiak, G.: 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, pp. 535\u2013549. Springer (2002)","DOI":"10.1007\/3-540-36136-7_47"},{"issue":"2","key":"9725_CR39","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1109\/TIT.1985.1057020","volume":"31","author":"J Koml\u00f3s","year":"1985","unstructured":"Koml\u00f3s, J., Greenberg, A.G.: An asymptotically fast nonadaptive algorithm for conflict resolution in multiple-access channels. IEEE Trans. Inf. Theory 31(2), 302\u2013306 (1985)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9725_CR40","doi-asserted-by":"crossref","unstructured":"Kowalski, D.R.: On selection problem in radio networks. In: Proceedings of the 24th ACM Symposium on Principles of Distributed Computing (PODC), pp. 158\u2013166. ACM (2005)","DOI":"10.1145\/1073814.1073843"},{"issue":"2","key":"9725_CR41","doi-asserted-by":"publisher","first-page":"286","DOI":"10.1137\/S0097539702413306","volume":"33","author":"Z Lotker","year":"2004","unstructured":"Lotker, Z., Patt-Shamir, B., Ros\u00e9n, A.: New stability results for adversarial queuing. SIAM J. Comput. 33(2), 286\u2013303 (2004)","journal-title":"SIAM J. Comput."},{"issue":"7","key":"9725_CR42","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1145\/360248.360253","volume":"19","author":"R Metcalfe","year":"1976","unstructured":"Metcalfe, R., Boggs, D.: Ethernet: Distributed packet switching for local computer networks. Commun. ACM 19(7), 395\u2013404 (1976)","journal-title":"Commun. ACM"},{"issue":"2","key":"9725_CR43","doi-asserted-by":"publisher","first-page":"709","DOI":"10.1137\/S0097539795285333","volume":"28","author":"P Raghavan","year":"1998","unstructured":"Raghavan, P., Upfal, E.: Stochastic contention resolution with short delays. SIAM J. Comput. 28(2), 709\u2013719 (1998)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"9725_CR44","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/S0020-0190(02)00312-5","volume":"84","author":"A Ros\u00e9n","year":"2002","unstructured":"Ros\u00e9n, A.: A note on models for non-probabilistic analysis of packet switching networks. Inf. Process. Lett. 84(5), 237\u2013240 (2002)","journal-title":"Inf. Process. Lett."},{"issue":"6","key":"9725_CR45","doi-asserted-by":"publisher","first-page":"805","DOI":"10.1007\/s00224-006-1248-4","volume":"39","author":"A Ros\u00e9n","year":"2006","unstructured":"Ros\u00e9n, A., Tsirkin, M.S.: On delivery times in packet networks under adversarial traffic. Theory Comput. Syst. 39(6), 805\u2013827 (2006)","journal-title":"Theory Comput. Syst."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-016-9725-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9725-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9725-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,12]],"date-time":"2025-06-12T22:04:14Z","timestamp":1749765854000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-016-9725-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,11,28]]},"references-count":45,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,10]]}},"alternative-id":["9725"],"URL":"https:\/\/doi.org\/10.1007\/s00224-016-9725-x","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2016,11,28]]},"assertion":[{"value":"28 November 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}