{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T19:55:49Z","timestamp":1742932549272,"version":"3.40.3"},"publisher-location":"Cham","reference-count":31,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030897154"},{"type":"electronic","value":"9783030897161"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-89716-1_9","type":"book-chapter","created":{"date-parts":[[2021,10,25]],"date-time":"2021-10-25T13:08:02Z","timestamp":1635167282000},"page":"132-148","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Minimal Number of Calls in Propositional Protocols"],"prefix":"10.1007","author":[{"given":"Joseph","family":"Livesey","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5560-0546","authenticated-orcid":false,"given":"Dominik","family":"Wojtczak","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,10,22]]},"reference":[{"key":"9_CR1","doi-asserted-by":"crossref","unstructured":"Anderson, C.J., et al.: NetKAT: semantic foundations for networks. In: The 41st Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2014, pp. 113\u2013126. ACM (2014)","DOI":"10.1145\/2535838.2535862"},{"key":"9_CR2","doi-asserted-by":"crossref","unstructured":"Apt, K.R., Grossi, D., van der Hoek, W.: Epistemic protocols for distributed gossiping. In: Proceedings of the 15th Conference on Theoretical Aspects of Rationality and Knowledge (TARK 2015), volume 215 of EPTCS, pp. 51\u201366 (2016)","DOI":"10.4204\/EPTCS.215.5"},{"key":"9_CR3","doi-asserted-by":"crossref","unstructured":"Apt, K.R., Grossi, D., van der Hoek, W.: When are two gossips the same? In: Barthe, G., Sutcliffe, G., Veanes, M. (eds.) LPAR-22. 22nd International Conference on Logic for Programming, Artificial Intelligence and Reasoning, volume 57 of EPiC Series in Computing, pp. 36\u201355. EasyChair (2018)","DOI":"10.29007\/ww65"},{"key":"9_CR4","doi-asserted-by":"crossref","unstructured":"Apt, K.R., Kopczy\u0144ski, E., Wojtczak, D.: On the computational complexity of gossip protocols. In: Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, pp. 765\u2013771 (2017)","DOI":"10.24963\/ijcai.2017\/106"},{"key":"9_CR5","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1007\/978-3-319-48758-8_2","volume-title":"Logics in Artificial Intelligence","author":"KR Apt","year":"2016","unstructured":"Apt, K.R., Wojtczak, D.: On decidability of a logic of gossips. In: Michael, L., Kakas, A. (eds.) JELIA 2016. LNCS (LNAI), vol. 10021, pp. 18\u201333. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-48758-8_2"},{"key":"9_CR6","doi-asserted-by":"crossref","unstructured":"Apt, K.R., Wojtczak, D.: Common knowledge in a logic of gossips. In: Proceedings of the 16th Conference on Theoretical Aspects of Rationality and Knowledge (TARK 2017), volume 251 of EPTCS, pp. 10\u201327 (2017)","DOI":"10.4204\/EPTCS.251.2"},{"key":"9_CR7","doi-asserted-by":"crossref","unstructured":"Apt, K.R., Wojtczak, D.: Decidability of fair termination of gossip protocols. In: Proceedings of the 21st International Conference on Logic for Programming, Artificial Intelligence and Reasoning (LPAR 21), volume 1 of Kalpa Publications in Computing, pp. 73\u201385 (2017)","DOI":"10.29007\/62s4"},{"key":"9_CR8","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1613\/jair.1.11204","volume":"62","author":"KR Apt","year":"2018","unstructured":"Apt, K.R., Wojtczak, D.: Verification of distributed epistemic gossip protocols. J. Artif. Intell. Res. (JAIR) 62, 101\u2013132 (2018)","journal-title":"J. Artif. Intell. Res. (JAIR)"},{"key":"9_CR9","doi-asserted-by":"crossref","unstructured":"Apt, K.R., Wojtczak, D.: Open problems in a logic of gossips. In: Proceedings Seventeenth Conference on Theoretical Aspects of Rationality and Knowledge (TARK 2019), volume 297 of EPTCS, pp. 1\u201318 (2019)","DOI":"10.4204\/EPTCS.297.1"},{"key":"9_CR10","unstructured":"Attamah, M., Van Ditmarsch, H., Grossi, D., van der Hoek, W.: Knowledge and gossip. In: Proceedings of ECAI 2014, pp. 21\u201326. IOS Press (2014)"},{"issue":"1","key":"9_CR11","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1137\/0602002","volume":"2","author":"RT Bumby","year":"1981","unstructured":"Bumby, R.T.: A problem with telephones. SIAM J. Algebr. Discrete. Methods 2(1), 13\u201318 (1981)","journal-title":"SIAM J. Algebr. Discrete. Methods"},{"key":"9_CR12","unstructured":"Cooper, M.C., Herzig, A., Maffre, F., Maris, F., R\u00e9gnier, P.: Simple epistemic planning: generalised gossiping. In: Proceedings of ECAI 2016, volume 285 of Frontiers in Artificial Intelligence and Applications, pp. 1563\u20131564. IOS Press (2016)"},{"key":"9_CR13","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-030-14174-5_1","volume-title":"Multi-Agent Systems","author":"MC Cooper","year":"2019","unstructured":"Cooper, M.C., Herzig, A., Maris, F., Vianey, J.: Temporal epistemic gossip problems. In: Slavkovik, M. (ed.) EUMAS 2018. LNCS (LNAI), vol. 11450, pp. 1\u201314. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-14174-5_1"},{"issue":"4","key":"9_CR14","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/s004460050038","volume":"10","author":"R Fagin","year":"1997","unstructured":"Fagin, R., Halpern, J.Y., Moses, Y., Vardi, M.Y.: Knowledge-based programs. Distrib. Comput. 10(4), 199\u2013225 (1997)","journal-title":"Distrib. Comput."},{"key":"9_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1007\/978-3-030-02149-8_17","volume-title":"Relational and Algebraic Methods in Computer Science","author":"M Gattinger","year":"2018","unstructured":"Gattinger, M., Wagemaker, J.: Towards an analysis of dynamic gossip in NetKAT. In: Desharnais, J., Guttmann, W., Joosten, S. (eds.) RAMiCS 2018. LNCS, vol. 11194, pp. 280\u2013297. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-030-02149-8_17"},{"key":"9_CR16","doi-asserted-by":"crossref","unstructured":"Harary, F., Schwenk, A.J.: The communication problem on graphs and digraphs (1974)","DOI":"10.1016\/0016-0032(74)90126-4"},{"issue":"4","key":"9_CR17","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1002\/net.3230180406","volume":"18","author":"SM Hedetniemi","year":"1988","unstructured":"Hedetniemi, S.M., Hedetniemi, S.T., Liestman, A.L.: A survey of gossiping and broadcasting in communication networks. Networks 18(4), 319\u2013349 (1988)","journal-title":"Networks"},{"key":"9_CR18","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/978-3-319-33509-4_20","volume-title":"Multi-Agent Systems and Agreement Technologies","author":"A Herzig","year":"2016","unstructured":"Herzig, A., Maffre, F.: How to share knowledge by gossiping. In: Rovatsos, M., Vouros, G., Julian, V. (eds.) EUMAS\/AT -2015. LNCS (LNAI), vol. 9571, pp. 249\u2013263. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-33509-4_20"},{"issue":"1","key":"9_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.3233\/AIC-170723","volume":"30","author":"A Herzig","year":"2017","unstructured":"Herzig, A., Maffre, F.: How to share knowledge by gossiping. AI Commun. 30(1), 1\u201317 (2017)","journal-title":"AI Commun."},{"key":"9_CR20","unstructured":"Hromkovi\u010d, J., Klasing, R., Pelc, A., Ruzicka, P., Unger, W.: Dissemination of Information in Communication Networks - Broadcasting, Gossiping, Leader Election, and Fault-Tolerance. Texts in Theoretical Computer Science. An EATCS Series. Springer, Heidelberg (2005)"},{"key":"9_CR21","unstructured":"Kempe, D., Dobra, A., Gehrke, J.: Gossip-based computation of aggregate information. In: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003, pp. 482\u2013491. IEEE (2003)"},{"issue":"5","key":"9_CR22","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/1317379.1317381","volume":"41","author":"A Kermarrec","year":"2007","unstructured":"Kermarrec, A., van Steen, M.: Gossiping in distributed systems. Oper. Syst. Rev. 41(5), 2\u20137 (2007)","journal-title":"Oper. Syst. Rev."},{"issue":"4","key":"9_CR23","doi-asserted-by":"publisher","first-page":"360","DOI":"10.1145\/138873.138877","volume":"10","author":"R Ladin","year":"1992","unstructured":"Ladin, R., Liskov, B., Shrira, L., Ghemawat, S.: Providing high availability using lazy replication. ACM Trans. Comput. Syst. (TOCS) 10(4), 360\u2013391 (1992)","journal-title":"ACM Trans. Comput. Syst. (TOCS)"},{"key":"9_CR24","doi-asserted-by":"crossref","unstructured":"Livesey, J., Wojtczak, D.: Propositional gossip protocols. In: Proceedings of the 23rd International Symposium on Fundamentals of Computation Theory (FCT 2021), (to appear) (2021)","DOI":"10.1007\/978-3-030-86593-1_25"},{"key":"9_CR25","unstructured":"Tijdeman, R.: On a telephone problem. Nieuw Archief voor Wiskunde 3(XIX), 188\u2013192 (1971)"},{"key":"9_CR26","unstructured":"Ditmarsch, H., Grossi, D., Herzig, A., van der Hoek, W., Kuijer, L. B.: Parameters for epistemic gossip problems. In: Proceedings of the 12th Conference on Logic and the Foundations of Game and Decision Theory (LOFT 2016) (2016)"},{"key":"9_CR27","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/978-3-030-01713-2_10","volume-title":"Multi-Agent Systems and Agreement Technologies","author":"H van Ditmarsch","year":"2018","unstructured":"van Ditmarsch, H., Kokkinis, I.: The expected duration of sequential gossiping. In: Belardinelli, F., Argente, E. (eds.) EUMAS\/AT -2017. LNCS (LNAI), vol. 10767, pp. 131\u2013146. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-030-01713-2_10"},{"key":"9_CR28","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/978-3-319-69131-2_6","volume-title":"PRIMA 2017: Principles and Practice of Multi-Agent Systems","author":"H van Ditmarsch","year":"2017","unstructured":"van Ditmarsch, H., Kokkinis, I., Stockmarr, A.: Reachability and expectation in gossiping. In: An, B., Bazzan, A., Leite, J., Villata, S., van der Torre, L. (eds.) PRIMA 2017. LNCS (LNAI), vol. 10621, pp. 93\u2013109. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-69131-2_6"},{"key":"9_CR29","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2020.103306","volume":"286","author":"H van Ditmarsch","year":"2020","unstructured":"van Ditmarsch, H., van Der Hoek, W., Kuijer, L.B.: The logic of gossiping. Artif. Intell. 286, 103306 (2020)","journal-title":"Artif. Intell."},{"key":"9_CR30","doi-asserted-by":"crossref","unstructured":"van Ditmarsch, H., van Eijck, J., Pardo, P., Ramezanian, R., Schwarzentruber, F.: Epistemic protocols for dynamic gossip. J. Appl. Log. 20(C), 1\u201331 (2017)","DOI":"10.1016\/j.jal.2016.12.001"},{"key":"9_CR31","doi-asserted-by":"crossref","unstructured":"van Ditmarsch, H., van Eijck, J., Pardo, P., Ramezanian, R., Schwarzentruber, F.: Dynamic gossip. Bull. Iran. Math. Soc. 1\u201328 (2018)","DOI":"10.1016\/j.jal.2016.12.001"}],"container-title":["Lecture Notes in Computer Science","Reachability Problems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-89716-1_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,10]],"date-time":"2024-09-10T19:08:51Z","timestamp":1725995331000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-89716-1_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030897154","9783030897161"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-89716-1_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"22 October 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"RP","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Reachability Problems","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Liverpool","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"United Kingdom","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25 October 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 October 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"rp2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/rp2021.csc.liv.ac.uk\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}