{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T05:20:09Z","timestamp":1759814409986,"version":"3.41.0"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2012,10,1]],"date-time":"2012-10-01T00:00:00Z","timestamp":1349049600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004963","name":"Seventh Framework Programme","doi-asserted-by":"publisher","award":["ICT2007216676 ECRYPT II"],"award-info":[{"award-number":["ICT2007216676 ECRYPT II"]}],"id":[{"id":"10.13039\/501100004963","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/I03126X\/1"],"award-info":[{"award-number":["EP\/I03126X\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2012,10]]},"abstract":"<jats:p>\n            Perfectly reliable message transmission (PRMT) is one of the fundamental problems in distributed computing. It allows a sender to reliably transmit a message to a receiver in an unreliable network, even in the presence of a computationally unbounded adversary. In this article, we study the inherent trade-off between the three important parameters of the PRMT protocols, namely, the network connectivity (\n            <jats:italic>n<\/jats:italic>\n            ), the round complexity (\n            <jats:italic>r<\/jats:italic>\n            ), and the communication complexity by considering the following generic question (which can be considered as the holy grail problem) in the context of the PRMT protocols.\n          <\/jats:p>\n          <jats:p>\n            Given an\n            <jats:italic>n<\/jats:italic>\n            -connected network, a message of size \u2113 (to be reliably communicated) and a limit\n            <jats:bold>c<\/jats:bold>\n            for the total communication allowed between the sender and the receiver, what is the minimum number of communication rounds required by a PRMT protocol to send the message, such that the communication complexity of the protocol is O(\n            <jats:bold>c<\/jats:bold>\n            )?\n          <\/jats:p>\n          <jats:p>We answer this interesting question by deriving a nontrivial lower bound on the round complexity. Moreover, we show that the lower bound is tight in the amortized sense, by designing a PRMT protocol whose round complexity matches the lower bound. The lower bound is the first of its kind, that simultaneously captures the inherent tradeoff between the three important parameters of a PRMT protocol.<\/jats:p>","DOI":"10.1145\/2371656.2371657","type":"journal-article","created":{"date-parts":[[2012,11,13]],"date-time":"2012-11-13T15:03:58Z","timestamp":1352819038000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["On the trade-off between network connectivity, round complexity, and communication complexity of reliable message transmission"],"prefix":"10.1145","volume":"59","author":[{"given":"Ashwinkumar","family":"Badanidiyuru","sequence":"first","affiliation":[{"name":"Cornell University, Ithaca, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arpita","family":"Patra","sequence":"additional","affiliation":[{"name":"University of Bristol, Clifton, Bristol"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ashish","family":"Choudhury","sequence":"additional","affiliation":[{"name":"University of Bristol, Clifton, Bristol"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kannan","family":"Srinathan","sequence":"additional","affiliation":[{"name":"IIIT Hyderabad, Gachibowli Hyderabad, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"C. Pandu","family":"Rangan","sequence":"additional","affiliation":[{"name":"IIT Madras, Chennai, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,11,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1400751.1400804"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Altmann B. Fitzi M. and \n      Maurer U. M\n  . \n  1999\n  . Byzantine agreement secure against general adversaries in the dual failure model. In Proceedings of the 13th International Symposium on Distributed Computing (DISC'99). P. Jayanti Lecture Notes in Computer Science Series vol. \n  1693 Springer-Verlag 123--137.   Altmann B. Fitzi M. and Maurer U. M. 1999. Byzantine agreement secure against general adversaries in the dual failure model. In Proceedings of the 13th International Symposium on Distributed Computing (DISC'99). P. Jayanti Lecture Notes in Computer Science Series vol. 1693 Springer-Verlag 123--137.","DOI":"10.1007\/3-540-48169-9_9"},{"volume-title":"Proceedings of the International Conference on Dependable Systems and Networks (DSN). IEEE Computer Scciety","author":"Backes M.","key":"e_1_2_1_3_1","unstructured":"Backes , M. and Cachin , C . 2003. Reliable broadcast in a computational hybrid model with Byzantine faults, crashes, and recoveries . In Proceedings of the International Conference on Dependable Systems and Networks (DSN). IEEE Computer Scciety , Los Alamitos, CA, 37--46. Backes, M. and Cachin, C. 2003. Reliable broadcast in a computational hybrid model with Byzantine faults, crashes, and recoveries. In Proceedings of the International Conference on Dependable Systems and Networks (DSN). IEEE Computer Scciety, Los Alamitos, CA, 37--46."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90035-E"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of Advances in Cryptology, 11th Annual International Cryptology Conference (CRYPTO'91)","volume":"576","author":"Beaver D.","year":"1991","unstructured":"Beaver , D. 1991 . Efficient multiparty protocols using circuit randomization . In Proceedings of Advances in Cryptology, 11th Annual International Cryptology Conference (CRYPTO'91) . J. Feigenbaum, Ed., Lecture Notes in Computer Science Series , vol. 576 , Springer-Verlag, 420--432. Beaver, D. 1991. Efficient multiparty protocols using circuit randomization. In Proceedings of Advances in Cryptology, 11th Annual International Cryptology Conference (CRYPTO'91). J. Feigenbaum, Ed., Lecture Notes in Computer Science Series, vol. 576, Springer-Verlag, 420--432."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/11681878_16"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Beerliov\u00e1-Trub\u00edniov\u00e1 Z.\n     and \n      Hirt M\n  . \n  2008\n  . Perfectly secure MPC with linear communication complexity. In Proceedings of the 5th Theory of Cryptography Conference (TCC'08) R. Canetti Ed. Lecture Notes in Computer Science Series vol. \n  4948 Springer-Verlag New York 213--230.   Beerliov\u00e1-Trub\u00edniov\u00e1 Z. and Hirt M. 2008. Perfectly secure MPC with linear communication complexity. In Proceedings of the 5th Theory of Cryptography Conference (TCC'08) R. Canetti Ed. Lecture Notes in Computer Science Series vol. 4948 Springer-Verlag New York 213--230.","DOI":"10.1007\/978-3-540-78524-8_13"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62213"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01187072"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167105"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62214"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.64"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85093-9_15"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92295-7_19"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Desmedt Y.\n     and \n      Wang Y\n  . \n  2003\n  . Perfectly secure message transmission revisited. In Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT'03) E. Biham Ed. Lecture Notes in Computer Science Series vol. \n  2656 Springer-Verlag 502--517.   Desmedt Y. and Wang Y. 2003. Perfectly secure message transmission revisited. In Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT'03) E. Biham Ed. Lecture Notes in Computer Science Series vol. 2656 Springer-Verlag 502--517.","DOI":"10.1007\/3-540-46035-7_33"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(82)90004-9"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/138027.138036"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3149.214121"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Fitzi M. Hirt M. and \n      Maurer U. M\n  . \n  1998\n  . Trading correctness for privacy in unconditional multi-Party computation (extended abstract). In Proceedings of the 18th Annual International Cryptology Conference (CRYPTO'98). H. Krawczyk Ed. Lecture Notes in Computer Science\n  . \n  Springer-Verlag\n  .   Fitzi M. Hirt M. and Maurer U. M. 1998. Trading correctness for privacy in unconditional multi-Party computation (extended abstract). In Proceedings of the 18th Annual International Cryptology Conference (CRYPTO'98). H. Krawczyk Ed. Lecture Notes in Computer Science. Springer-Verlag.","DOI":"10.1007\/BFb0055724"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Fitzi M. Hirt M. and \n      Maurer U. M\n  . \n  1999\n  . General adversaries in unconditional multi-party computation. In Proceedings of the International Conference on the Theory and Applications of Cryptology and Information Security (ASIACRYPT'99) K. Lam E. Okamoto and C. Xing Eds. Lecture Notes in Computer Science Series vol. \n  1716 Springer Verlag\n  .   Fitzi M. Hirt M. and Maurer U. M. 1999. General adversaries in unconditional multi-party computation. In Proceedings of the International Conference on the Theory and Applications of Cryptology and Information Security (ASIACRYPT'99) K. Lam E. Okamoto and C. Xing Eds. Lecture Notes in Computer Science Series vol. 1716 Springer Verlag.","DOI":"10.1007\/978-3-540-48000-6_19"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794265232"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 6th International Workshop on Distributed Algorithms (WDAG). Lecture Notes in Computer Science Series","volume":"647","author":"Garay J. A.","unstructured":"Garay , J. A. and Perry , K. J . 1992. A continuum of failure models for distributed computing . In Proceedings of the 6th International Workshop on Distributed Algorithms (WDAG). Lecture Notes in Computer Science Series , vol. 647 , Springer-Verlag, 153--165. Garay, J. A. and Perry, K. J. 1992. A continuum of failure models for distributed computing. In Proceedings of the 6th International Workshop on Distributed Algorithms (WDAG). Lecture Notes in Computer Science Series, vol. 647, Springer-Verlag, 153--165."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380853"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28420"},{"volume-title":"Proceedings of the International Conference on Dependable Systems and Networks (DSN). IEEE Computer Scciety","author":"Goodson G. R.","key":"e_1_2_1_25_1","unstructured":"Goodson , G. R. , Wylie , J. J. , Ganger , G. R. , and Reiter , M. K . 2004. Efficient Byzantine-tolerant erasure-coded storage . In Proceedings of the International Conference on Dependable Systems and Networks (DSN). IEEE Computer Scciety , Los Alamitos, CA, 135--144. Goodson, G. R., Wylie, J. J., Ganger, G. R., and Reiter, M. K. 2004. Efficient Byzantine-tolerant erasure-coded storage. In Proceedings of the International Conference on Dependable Systems and Networks (DSN). IEEE Computer Scciety, Los Alamitos, CA, 135--144."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/571825.571858"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Kurosawa K.\n     and \n      Suzuki K\n  . \n  2008\n  . Truly efficient 2-round perfectly secure message transmission scheme. In Proceedings of the 27th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT'08). N. P. Smart Ed. Lecture Notes in Computer Science Series vol. \n  4965 Springer-Verlag 324--340.   Kurosawa K. and Suzuki K. 2008. Truly efficient 2-round perfectly secure message transmission scheme. In Proceedings of the 27th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT'08). N. P. Smart Ed. Lecture Notes in Computer Science Series vol. 4965 Springer-Verlag 324--340.","DOI":"10.1007\/978-3-540-78967-3_19"},{"key":"e_1_2_1_28_1","unstructured":"Lynch N. A. 1996. Distributed Algorithms. Morgan-Kaufmann.   Lynch N. A. 1996. Distributed Algorithms. Morgan-Kaufmann."},{"key":"e_1_2_1_29_1","unstructured":"MacWilliams F. J. and Sloane N. J. A. 1978. The Theory of Error Correcting Codes. North-Holland Publishing Company.  MacWilliams F. J. and Sloane N. J. A. 1978. The Theory of Error Correcting Codes. North-Holland Publishing Company."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1029"},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","unstructured":"Patra A. Choudhary A. and \n      Rangan C. P\n  . \n  2010\n  . On communication complexity of secure message transmission in directed networks. In Proceedings of the 11th International Conference on Distributed Computing and Networking (ICDCN'10). K. Kant S. V. Premmaraju K. M. Sivalingam and J. Wu Eds. Lecture Notes in Computer Science Series vol. \n  5935 Springer-Verlag 42--53.   Patra A. Choudhary A. and Rangan C. P. 2010. On communication complexity of secure message transmission in directed networks. In Proceedings of the 11th International Conference on Distributed Computing and Networking (ICDCN'10). K. Kant S. V. Premmaraju K. M. Sivalingam and J. Wu Eds. Lecture Notes in Computer Science Series vol. 5935 Springer-Verlag 42--53.","DOI":"10.1007\/978-3-642-11322-2_9"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/11941378_16"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70500-0_13"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/1778554.1778562"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/322186.322188"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73014"},{"volume-title":"Proceedings of 7th IEEE International Symposium on Parallel and Distributed Processing (IPDPS). IEEE Computer Society.","author":"Sayeed H.","key":"e_1_2_1_37_1","unstructured":"Sayeed , H. and Abu-Amara , H . 1995. Perfectly secure message transmission in asynchronous networks . In Proceedings of 7th IEEE International Symposium on Parallel and Distributed Processing (IPDPS). IEEE Computer Society. Sayeed, H. and Abu-Amara, H. 1995. Perfectly secure message transmission in asynchronous networks. In Proceedings of 7th IEEE International Symposium on Parallel and Distributed Processing (IPDPS). IEEE Computer Society."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1996.0033"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/647098.717160"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-28628-8_33"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/1777898.1777911"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2007.31"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/1382436.1382751"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2371656.2371657","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2371656.2371657","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:21:18Z","timestamp":1750238478000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2371656.2371657"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,10]]},"references-count":43,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2012,10]]}},"alternative-id":["10.1145\/2371656.2371657"],"URL":"https:\/\/doi.org\/10.1145\/2371656.2371657","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2012,10]]},"assertion":[{"value":"2010-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-11-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}