×

On interactive knowledge with bounded communication. (English) Zbl 1242.03035

Summary: The effect of upper bounds on message delivery times in a computer network upon the dynamics of knowledge gain is investigated. Recent work has identified centipedes and brooms-causal structures that combine message chains with time bound information-as necessary conditions for knowledge gain and common knowledge gain, respectively. This paper shows that, under the full-information protocol, these structures are both necessary and sufficient for such epistemic gain. We then apply this analysis to gain insights into the relation between “everyone knows” and common knowledge. We prove a tight threshold on the depth \(k\), beyond which \(E^{k} _{G}\) (everyone in \(G\) knows nested to depth \(k\)) collapses into \(C_{G}\) (common knowledge), when this knowledge concerns the occurrence of a spontaneous event. The threshold depends on the size of the group \(G\) of agents, as well as the time that has elapsed since the event of interest occurred. The existence of such a threshold is not guaranteed for all protocols, which is demonstrated here by presenting a counterexample in which no such threshold exists.

MSC:

03B42 Logics of knowledge and belief (including belief change)
68M12 Network protocols
68T42 Agent technology and artificial intelligence
94A05 Communication theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alur R., J. ACM 41 (1) pp 181– (1994) · Zbl 0807.68065 · doi:10.1145/174644.174651
[2] Baltag A., Proceedings of the 7th conference on Theoretical aspects of rationality and knowledge, TARK ’98
[3] Barwise J., Proc. Second Conference on Theoretical Aspects of Reasoning about Knowledge pp 365–
[4] van Benthem J., TARK ’07: Proceedings of the 11th conference on Theoretical aspects of rationality and knowledge pp 72–
[5] Ben-Zvi I., Causality, Knowledge and Coordination in Distributed Systems (2011)
[6] Ben-Zvi I., DISC 2010 (2010)
[7] Ben-Zvi I., Proceedings of the 13th Conference on Theoretical Aspects of Rationality and Knowledge, TARK XIII
[8] Chandy K. M., Distributed Computing 1 (1) pp 40– (1986) · Zbl 0602.68026 · doi:10.1007/BF01843569
[9] Clark H. H., Elements of Discourse Understanding pp 10– (1981)
[10] Conway J. H., Een pak met een korte broek: Papers presented to H. W. Lenstra on the occasion of the publication of his ”Euclidische Getallenlichamen” (1977)
[11] DOI: 10.1007/978-1-4020-5839-4 · Zbl 1156.03015 · doi:10.1007/978-1-4020-5839-4
[12] Fagin R., Reasoning about Knowledge (2003)
[13] Fischer M. J., Theoretical Aspects of Reasoning about Knowledge: Proc. 1986 Conference pp 171–
[14] DOI: 10.1145/79147.79161 · Zbl 0699.68115 · doi:10.1145/79147.79161
[15] DOI: 10.1145/359545.359563 · Zbl 0378.68027 · doi:10.1145/359545.359563
[16] Lamport L., ACM Trans. Program. Lang. Syst. 6 (2) pp 254– (1984) · doi:10.1145/2993.2994
[17] Lewis D., Convention, A Philosophical Study (1969)
[18] Lohrey M., Information and Computation 189 pp 160– (2004) · Zbl 1091.68006 · doi:10.1016/j.ic.2003.10.002
[19] Mazurkiewicz A., Concurrent program schemes and their interpretations (1977)
[20] Moses Y., TARK ’92: Proceedings of the 4th conference on Theoretical aspects of reasoning about knowledge pp 1–
[21] Parikh R., Research in Economics 57 (3) pp 267– (2003) · doi:10.1016/S1090-9443(03)00030-9
[22] Parikh R., Proc. Workshop on Logics of Programs pp 256–
[23] Parikh R., Journal of Logic, Language and Information 12 (4) pp 453– (2003) · Zbl 1031.03021 · doi:10.1023/A:1025007018583
[24] Rubinstein A., American Economic Review 79 (3) pp 385– (1989)
[25] Wang Y., Epistemic Modelling And Protocol Dynamics (2010)
[26] Zielonka W., Theoretical Informatics and Applications 21 (1987) · Zbl 0623.68055 · doi:10.1051/ita/1987210200991
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.