Abstract
We compare three notions of knowledge in concurrent system: memoryless knowledge, knowledge of perfect recall, and causal knowledge. Memoryless knowledge is based only on the current state of a process, knowledge of perfect recall can take into account the local history of a process, and causal knowledge depends on the causal past of a process, which comprises the information a process can obtain when all processes exchange the information they have when performing joint transitions. We compare these notions in terms of knowledge strength, number of bits required to store this information, and the complexity of checking if a given process has a given knowledge. We show that all three notions of knowledge can be implemented using finite memory. Causal knowledge proves to be strictly more powerful than knowledge with perfect recall, which in turn proves to be strictly more powerful than memoryless knowledge. We show that keeping track of causal knowledge is cheaper than keeping track of knowledge of perfect recall.
The work of the second author was partly supported by ISF grant 126-12 ”Practical Synthesis of Control for Distributed Systems”, and partly done while invited professor in University of Rennes 1.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Basu, A., Bensalem, S., Peled, D., Sifakis, J.: Priority scheduling of distributed systems based on model checking. Formal Methods in System Design 39(3), 229–245 (2011)
Diekert, V., Rozenberg, G.: In particular. In: Diekert, V., Muscholl, A. (eds.) The Book of Traces, ch. 8, World Scientific, Singapore (1995)
Fagin, R., Halpern, J.Y., Moses, Y., Vardi, M.: Reasoning About Knowledge. MIT Press, Cambridge (1995)
Gastin, P., Lerman, B., Zeitoun, M.: Distributed Games with Causal Memory Are Decidable for Series-Parallel Systems. In: Lodaya, K., Mahajan, M. (eds.) FSTTCS 2004. LNCS, vol. 3328, pp. 275–286. Springer, Heidelberg (2004)
Genest, B., Gimbert, H., Muscholl, A., Walukiewicz, I.: Optimal zielonka-type construction of deterministic asynchronous automata. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010, Part II. LNCS, vol. 6199, pp. 52–63. Springer, Heidelberg (2010)
Genest, B., Gimbert, H., Muscholl, A., Walukiewicz, I.: Asynchronous Games over Tree Architectures. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part II. LNCS, vol. 7966, pp. 275–286. Springer, Heidelberg (2013)
Genest, B., Muscholl, A.: Constructing Exponential-size Deterministic Zielonka Automata. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006, Part II. LNCS, vol. 4052, pp. 565–576. Springer, Heidelberg (2006)
Graf, S., Peled, D., Quinton, S.: Monitoring Distributed Systems Using Knowledge. In: Bruni, R., Dingel, J. (eds.) FORTE 2011 and FMOODS 2011. LNCS, vol. 6722, pp. 183–197. Springer, Heidelberg (2011)
Krishnan, R., Venkatesh, S.: Optimizing the gossip automaton, Report TCS-94-3, School of Mathematics, SPIC Science Foundation, Madras, India (1994)
Mazurkiewicz, A.: Concurrent program schemes and their interpretation. Technical report, DAIMI Report PB-78, Aarhus University (1977)
van der Meyden, R.: Common Knowledge and Update in Finite Environment. Information and Computation 140(2), 115–157 (1998)
van der Meyden, R., Shilov, N.V.: Model Checking Knowledge and Time in Systems with Perfect Recall. In: Pandu Rangan, C., Raman, V., Sarukkai, S. (eds.) FST TCS 1999. LNCS, vol. 1738, pp. 432–445. Springer, Heidelberg (1999)
Meyer, A.R., Stockmeyer, L.J.: The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space. In: Proc. of STOC 1973, pp. 1–9 (1973)
Mukund, M., Sohoni, M.: Keeping Track of the Latest Gossip in a Distributed System. Distr. Computing 10(3), 137–148 (1997)
Madhusudan, P., Thiagarajan, P.S., Yang, S.: The MSO Theory of Connectedly Communicating Processes. In: Sarukkai, S., Sen, S. (eds.) FSTTCS 2005. LNCS, vol. 3821, pp. 201–212. Springer, Heidelberg (2005)
Ricker, S.L., Rudie, K.: Know means no: Incorporating knowledge into discrete-event control systems. IEEE Trans. Automat. Contr. 45(9), 1656–1668 (2000)
Zielonka, W.: Notes on finite asynchronous automata. R.A.I.R.O. - Informatique Théorique et Applications 21, 99–135 (1987)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Genest, B., Peled, D., Schewe, S. (2015). Knowledge = Observation + Memory + Computation. In: Pitts, A. (eds) Foundations of Software Science and Computation Structures. FoSSaCS 2015. Lecture Notes in Computer Science(), vol 9034. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-46678-0_14
Download citation
DOI: https://doi.org/10.1007/978-3-662-46678-0_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-46677-3
Online ISBN: 978-3-662-46678-0
eBook Packages: Computer ScienceComputer Science (R0)