{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,5]],"date-time":"2026-06-05T12:40:17Z","timestamp":1780663217659,"version":"3.54.1"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2015,4,24]],"date-time":"2015-04-24T00:00:00Z","timestamp":1429833600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2015,10]]},"DOI":"10.1007\/s00446-015-0244-9","type":"journal-article","created":{"date-parts":[[2015,4,23]],"date-time":"2015-04-23T05:13:08Z","timestamp":1429765988000},"page":"297-308","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Bounded-Contention Coding for the additive network model"],"prefix":"10.1007","volume":"28","author":[{"given":"Keren","family":"Censor-Hillel","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bernhard","family":"Haeupler","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nancy","family":"Lynch","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Muriel","family":"M\u00e9dard","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2015,4,24]]},"reference":[{"key":"244_CR1","doi-asserted-by":"crossref","first-page":"290","DOI":"10.1016\/0022-0000(91)90015-W","volume":"43","author":"N Alon","year":"1991","unstructured":"Alon, N., Bar-Noy, A., Linial, N., Peleg, D.: A lower bound for radio broadcast. J. Comput. Syst. Sci. 43, 290\u2013298 (1991)","journal-title":"J. Comput. Syst. Sci."},{"key":"244_CR2","doi-asserted-by":"crossref","unstructured":"Amaudruz, A., Fragouli, C.: Combinatorial algorithms for wireless information flow. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 555\u2013564 (2009)","DOI":"10.1137\/1.9781611973068.61"},{"issue":"4","key":"244_CR3","doi-asserted-by":"crossref","first-page":"1872","DOI":"10.1109\/TIT.2011.2110110","volume":"57","author":"AS Avestimehr","year":"2011","unstructured":"Avestimehr, A.S., Diggavi, S.N., Tse, D.N.C.: Wireless network information flow: a deterministic approach. IEEE Trans. Inf. Theory 57(4), 1872\u20131905 (2011)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"1","key":"244_CR4","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1016\/0022-0000(92)90042-H","volume":"45","author":"R Bar-Yehuda","year":"1992","unstructured":"Bar-Yehuda, R., Goldreich, O., Itai, A.: On the time-complexity of broadcast in multi-hop radio networks: an exponential gap between determinism and randomization. J. Comput. Syst. Sci. 45(1), 104\u2013126 (1992)","journal-title":"J. Comput. Syst. Sci."},{"key":"244_CR5","doi-asserted-by":"crossref","first-page":"875","DOI":"10.1137\/0222055","volume":"22","author":"R Bar-Yehuda","year":"1993","unstructured":"Bar-Yehuda, R., Israeli, A., Itai, A.: Multiple communication in multi-hop radio networks. SIAM J. Comput. 22, 875\u2013887 (1993)","journal-title":"SIAM J. Comput."},{"issue":"7","key":"244_CR6","doi-asserted-by":"crossref","first-page":"769","DOI":"10.1109\/TCOM.1984.1096146","volume":"32","author":"T Berger","year":"1984","unstructured":"Berger, T., Mehravari, N., Towsley, D., Wolf, J.: Random multiple-access communication and group testing. IEEE Trans. Commun. 32(7), 769\u2013779 (1984)","journal-title":"IEEE Trans. Commun."},{"key":"244_CR7","unstructured":"Bienkowski, M., Klonowski, M., Korzeniowski, M., Kowalski, D.R.: Dynamic sharing of a multiple access channel. In 27th International Symposium on Theoretical Aspects of Computer Science (STACS), pp. 83\u201394 (2010)"},{"key":"244_CR8","doi-asserted-by":"crossref","unstructured":"Chlebus, B.S., Kowalski, D.R., Pelc, A., Rokicki, M.A.: Efficient distributed communication in ad-hoc radio networks. In Proceedings of the 38th International Colloquium on Automata, Languages, and Programming (ICALP), pp. 613\u2013624 (2011)","DOI":"10.1007\/978-3-642-22012-8_49"},{"issue":"4","key":"244_CR9","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1016\/j.jcss.2008.10.004","volume":"75","author":"AEF Clementi","year":"2009","unstructured":"Clementi, A.E.F., Monti, A., Pasquale, F., Silvestri, R.: Broadcasting in dynamic radio networks. J. Comput. Syst. Sci. 75(4), 213\u2013230 (2009)","journal-title":"J. Comput. Syst. Sci."},{"key":"244_CR10","doi-asserted-by":"crossref","unstructured":"Cornejo, A., Newport, C.: Prioritized gossip in vehicular networks. In Proceedings of the 6th ACM SIGACT\/SIGMOBILE International Workshop on Foundations of Mobile Computing (DIALM-POMC 2010) (2010)","DOI":"10.1145\/1860684.1860697"},{"key":"244_CR11","doi-asserted-by":"crossref","unstructured":"Czumaj, A., Rytter, W.: Broadcasting algorithms in radio networks with unknown topology. In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS), p. 492 (2003)","DOI":"10.1109\/SFCS.2003.1238222"},{"issue":"7","key":"244_CR12","doi-asserted-by":"crossref","first-page":"1092","DOI":"10.1109\/TPDS.2010.162","volume":"22","author":"J Czyzowicz","year":"2011","unstructured":"Czyzowicz, 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":"244_CR13","doi-asserted-by":"crossref","first-page":"2162","DOI":"10.1137\/080733826","volume":"39","author":"G Marco De","year":"2010","unstructured":"De Marco, G.: Distributed broadcast in unknown radio networks. SIAM J. Comput. 39, 2162\u20132175 (2010)","journal-title":"SIAM J. Comput."},{"key":"244_CR14","doi-asserted-by":"crossref","unstructured":"Effros, M., M\u00e9dard, M., Ho, T., Ray, S., Karger, D., Koetter, R.: Linear network codes: A unified framework for source channel, and network coding. In Proceedings of the DIMACS Workshop on Network Information Theory (Invited paper) (2003)","DOI":"10.1090\/dimacs\/066\/13"},{"issue":"8","key":"244_CR15","doi-asserted-by":"crossref","first-page":"4867","DOI":"10.1109\/TIT.2014.2329840","volume":"60","author":"E Erez","year":"2014","unstructured":"Erez, E., Kim, M., Xu, Y., Yeh, E.M., M\u00e9dard, M.: Deterministic network model revisited: an algebraic network coding approach. IEEE Trans. Inf. Theory 60(8), 4867\u20134879 (2014)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"244_CR16","doi-asserted-by":"crossref","unstructured":"Erez, E., Xu, Y., Yeh, E.M.: Coding for the deterministic network model. In Allerton Conference on Communication, Control and Computing (2010)","DOI":"10.1109\/ALLERTON.2010.5707095"},{"key":"244_CR17","doi-asserted-by":"crossref","unstructured":"Goemans, M.X., Iwata, S., Zenklusen, R.: An algorithmic framework for wireless information flow. In Proceedings of Allerton Conference on Communication, Control, and Computing (2009)","DOI":"10.1109\/ALLERTON.2009.5394810"},{"key":"244_CR18","doi-asserted-by":"crossref","unstructured":"Gollakota, S., Katabi, D.: Zigzag decoding: combating hidden terminals in wireless networks. In Proceedings of the ACM SIGCOMM Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM), pp. 159\u2013170 (2008)","DOI":"10.1145\/1402958.1402977"},{"key":"244_CR19","doi-asserted-by":"crossref","unstructured":"Haeupler, B.: Analyzing network coding gossip made easy. In Proceedings of the 43rd annual ACM symposium on Theory of computing (STOC), pp. 293\u2013302 (2011)","DOI":"10.1145\/1993636.1993676"},{"key":"244_CR20","doi-asserted-by":"crossref","unstructured":"Haeupler, B., Karger, D.: Faster information dissemination in dynamic networks via network coding. In Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 381\u2013390 (2011)","DOI":"10.1145\/1993806.1993885"},{"issue":"10","key":"244_CR21","doi-asserted-by":"crossref","first-page":"4413","DOI":"10.1109\/TIT.2006.881746","volume":"52","author":"T Ho","year":"2006","unstructured":"Ho, T., M\u00e9dard, M., Koetter, R., Karger, D.R., Effros, M., Shi, J., Leong, B.: A random linear network coding approach to multicast. IEEE Trans. Inf. Theory 52(10), 4413\u20134430 (2006)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"2","key":"244_CR22","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1109\/TIT.1985.1057012","volume":"31","author":"J Hui","year":"1985","unstructured":"Hui, J., Humblet, P.: The capacity region of the totally asynchronous multiple-access channel. IEEE Trans. Inf. Theory 31(2), 207\u2013216 (1985)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"244_CR23","doi-asserted-by":"crossref","unstructured":"Jurdzinski, 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), pp. 535\u2013549 (2002)","DOI":"10.1007\/3-540-36136-7_47"},{"key":"244_CR24","doi-asserted-by":"crossref","unstructured":"Khabbazian, M., Kowalski, D.: Time-efficient randomized multiple-message broadcast in radio networks. In Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing (PODC) (2011)","DOI":"10.1145\/1993806.1993884"},{"key":"244_CR25","doi-asserted-by":"crossref","unstructured":"Khabbazian, M., Kowalski, D., Kuhn, F., Lynch, N.: Decomposing broadcast algorithms using Abstract MAC layers. In Proceedings of Sixth ACM SIGACT\/SIGMOBILE International Workshop on Foundations of Mobile Computing (DIALM-POMC) (2010)","DOI":"10.1145\/1860684.1860690"},{"key":"244_CR26","doi-asserted-by":"crossref","unstructured":"Kim, M., M\u00e9dard, M.: Algebraic network coding approach to deterministic wireless relay network. In Allerton Conference on Communication, Control and Computing (2010)","DOI":"10.1109\/ALLERTON.2010.5707093"},{"key":"244_CR27","doi-asserted-by":"crossref","first-page":"782","DOI":"10.1109\/TNET.2003.818197","volume":"11","author":"R Koetter","year":"2003","unstructured":"Koetter, R., M\u00e9dard, M.: An algebraic approach to network coding. IEEE\/ACM Trans. Netw. 11, 782\u2013795 (2003)","journal-title":"IEEE\/ACM Trans. Netw."},{"issue":"2","key":"244_CR28","doi-asserted-by":"crossref","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":"244_CR29","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1007\/s00446-005-0126-7","volume":"18","author":"DR Kowalski","year":"2005","unstructured":"Kowalski, D.R., Pelc, A.: Broadcasting in undirected ad hoc radio networks. Distrib. Comput. 18, 43\u201357 (2005)","journal-title":"Distrib. Comput."},{"key":"244_CR30","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Lynch, N.A., Oshman. R.: Distributed computation in dynamic networks. In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC), pp. 513\u2013522 (2010)","DOI":"10.1145\/1806689.1806760"},{"key":"244_CR31","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moses, Y., Oshman, R.: Coordinated consensus in dynamic networks. In Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 1\u201310 (2011)","DOI":"10.1145\/1993806.1993808"},{"key":"244_CR32","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Oshman, R.: The complexity of data aggregation in directed networks. In Distributed Computing: 25th International Symposium on Distributed Computing (DISC), pp. 416\u2013431 (2011)","DOI":"10.1007\/978-3-642-24100-0_40"},{"key":"244_CR33","doi-asserted-by":"crossref","unstructured":"Kushilevitz, E., Mansour, Y.: An $$\\varOmega (D\\log (N\/D))$$ \u03a9 ( D log ( N \/ D ) ) lower bound for broadcast in radio networks. In Proceedings of the 12th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 65\u201374 (1993)","DOI":"10.1145\/164051.164059"},{"issue":"1","key":"244_CR34","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1016\/0020-0190(94)90133-3","volume":"52","author":"CU Martel","year":"1994","unstructured":"Martel, C.U.: Maximum finding on a multiple access broadcast network. Inf. Process. Lett. 52(1), 7\u201315 (1994)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"244_CR35","doi-asserted-by":"crossref","first-page":"486","DOI":"10.1109\/TWC.2003.821175","volume":"3","author":"M Medard","year":"2004","unstructured":"Medard, M., Huang, J., Goldsmith, A., Meyn, S., Coleman, T.: Capacity of time-slotted ALOHA packetized multiple-access systems over the AWGN channel. IEEE Trans. Wirel. Commun. 3(2), 486\u2013499 (2004)","journal-title":"IEEE Trans. Wirel. Commun."},{"key":"244_CR36","doi-asserted-by":"crossref","unstructured":"O\u2019Dell, R., Wattenhofer, R.: Information dissemination in highly dynamic graphs. In Proceedings of the 2005 Joint Workshop on Foundations of Mobile Computing (DIALM-POMC), pp. 104\u2013110 (2005)","DOI":"10.1145\/1080810.1080828"},{"key":"244_CR37","doi-asserted-by":"crossref","unstructured":"ParandehGheibi, A., Sundararajan, J.-K., M\u00e9dard, M.: Collision helps\u2014algebraic collision recovery for wireless erasure networks. In Proceedings of the Wireless Network Coding workshop (WiNC) (2010)","DOI":"10.1109\/WINC.2010.5507938"},{"key":"244_CR38","doi-asserted-by":"crossref","unstructured":"Peleg, D.: Time-efficient broadcasting in radio networks: a review. In Proceedings of the 4th International Conference on Distributed Computing and Internet Technology (ICDCIT), pp. 1\u201318 (2007)","DOI":"10.1007\/978-3-540-77115-9_1"},{"key":"244_CR39","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511808968","volume-title":"Introduction to Coding Theory","author":"RM Roth","year":"2006","unstructured":"Roth, R.M.: Introduction to Coding Theory. Cambridge University Press, Cambridge (2006)"},{"key":"244_CR40","doi-asserted-by":"crossref","unstructured":"Shi, C., Ramamoorthy, A.: Improved combinatorial algorithms for wireless information flow. In Proceedings of Allerton Conference on Communication, Control, and Computing (2010)","DOI":"10.1109\/ALLERTON.2010.5707000"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-015-0244-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-015-0244-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-015-0244-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,24]],"date-time":"2019-08-24T00:33:00Z","timestamp":1566606780000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-015-0244-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,4,24]]},"references-count":40,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2015,10]]}},"alternative-id":["244"],"URL":"https:\/\/doi.org\/10.1007\/s00446-015-0244-9","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,4,24]]}}}