Jump to : Download | Abstract | Contact | BibTex reference | EndNote reference |

genest:hal-01245016

B. Genest, D. Peled, S. Schewe. Knowledge = Observation + Memory + Computation. In FoSSaCS 2015, FoSSaCS 2015, Volume LNCS, Pages 215-229, London, United Kingdom, 2015.

Download [help]

Download paper: Doi page

Download paper: (link)

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.
This page is automatically generated by bib2html v216, © INRIA 2002-2007, Projet Lagadic

Abstract

We compare three notions of knowledge in concurrent system: mem-oryless knowledge, knowledge of perfect recall, and causal knowledge. Mem-oryless 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

Contact

Blaise Genest http://perso.crans.org/~genest/

BibTex Reference

@InProceedings{genest:hal-01245016,
   Author = {Genest, B. and Peled, D. and Schewe, S.},
   Title = {Knowledge = Observation + Memory + Computation},
   BookTitle = {FoSSaCS 2015},
   Volume = {LNCS},
   Number = {9034},
   Pages = {215--229},
   Series = {FoSSaCS 2015},
   Publisher = {Springer},
   Address = {London, United Kingdom},
   Year = {2015}
}

EndNote Reference [help]

Get EndNote Reference (.ref)