[go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Knowledge in shared memory systems

  • Published:
Distributed Computing Aims and scope Submit manuscript

Summary

We study the relation between knowledge and space. That is, we analyze how much shared memory space is needed in order to learn certain kinds of facts. Such results are useful tools for reasoning about shared memory systems. In addition we generalize a known impossibility result, and show that results about how knowledge can be gained and lost in message passing systems also hold for shared memory systems.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Attiya H, Bar-Noy A, Dolev D, Peleg D, Reischuk R: Renaming in an asynchronous environment. J ACM 37(3): 524–548 (1990)

    Google Scholar 

  2. Chandy KM, Misra J: How processes learn. Distrib Comput 1: 40–52 (1986)

    Google Scholar 

  3. Dwork C, Moses Y: Knowledge and common knowledge in a Byzantine environment I: crash failures. In: Theoretical aspects of reasoning about knowledge: Proceedings of the 1986 Conference, pp 149–169, Morgan Kaufmann 1986

  4. Fagin R, Halpern JY, Vardi M: A model theoretic analysis of knowledge. J ACM 38(2): 382–428 (1991)

    Google Scholar 

  5. Fischer MJ, Immerman, N: Foundations of knowledge for distributed systems. In: Theoretical aspects of reasoning about knowledge: Proceedings of the 1986 Conference, pp 171–185, Morgan Kaufmann 1986

  6. Fischer MJ, Lynch NA, Paterson MS: Impossibility of distributed consensus with one faulty process. J ACM 32(2): 374–382 (1985)

    Google Scholar 

  7. Fischer MJ, Zuck LD: Reasoning about uncertainty in fault-tolerant distributed systems. In: Joseph M (ed), Formal techniques in real-time and fault-tolerant systems. Lect Notes Comput Sci, vol 331. Springer, Berlin Heidelberg New York 1988, pp 142–158

    Google Scholar 

  8. Fischer MJ, Moran S, Rudich S, Taubenfeld G: The wakeup problem. In: Proc 22st ACM Symp on Theory of Computing, pp 106–116, 1990. See also Technion Report #644, Computer Science Department, The Technion 1990

  9. Hadzilacos V: A knowledge theoretic analysis of atomic commitment protocols. In: Proc 6th ACM Symp on Principles of Database Systems, pp 129–134, 1987

  10. Halpern JY: Using reasoning about knowledge to analyze distributed systems. Annu Rev Comput Sci 2: 37–68 (1987)

    Google Scholar 

  11. Halpern JY, Fagin R: A formal model of knowledge, action, and communication in distributed systems: preliminary report. In: Proc 4th ACM Symp on Principles of Distributed Computing, pp 224–236, 1985

  12. Halpern JY, Moses Y: Knowledge and common knowledge in a distributed environment. J ACM 37(3): 549–587 (1990)

    Google Scholar 

  13. Halpern JY, Zuck LD: A little knowledge goes a long way: simple knowledge-based derivations and correctness proofs for a family of protocols. J ACM 39(3): 449–478 (1992)

    Google Scholar 

  14. Katz S, Taubenfeld G: What processes know: definitions and proof methods. In: Proc 5th ACM Symp on Principles of Distributed Computing, pp 249–262, 1986

  15. Lamport L: Time, clocks, and the ordering of events in a distributed system. Commun ACM 21(7): 558–565 (1978)

    Google Scholar 

  16. Lehmann D: Knowledge, common knowledge and related puzzles. In: Proc 3rd ACM Symp on Principles of Distributed Computing, pp 62–67, 1984

  17. Loui MC, Abu-Amara H: Memory requirements for agreement among unreliable asynchronous processes. Advances in Computing Research, 4: 163–183, 1987

    Google Scholar 

  18. Mazer MS: A knowledge-theoretic account of negotiated commitment. Tech Rep CSRI-237, Computer Systems Research Institute, University of Toronto, PhD Thesis 1989

  19. Michel R: A categorical approach to distributed systems expressibility and knowledge. In: Proc 8th ACM Symp on Principles of Distributed Computing, pp 129–143, 1989

  20. Moran S, Wolfsthal Y: An extended impossibility result for asynchronous complete networks. Inf Process Lett 26: 141–151 (1987)

    Google Scholar 

  21. Moses Y, Roth G: On reliable message diffusion. In: Proc 8th ACM Symp on Principles of Distributed Computing, pp 119–127, 1989

  22. Moses Y, Tuttle MR: Programming simultaneous actions using common knowledge. Algorithmica 3: 121–169 (1988)

    Google Scholar 

  23. Neiger G, Toueg S: Substituting for real time and common knowledge in asynchronous distributed system. In: Proc 6th ACM Symp on Principles of Distributed Computing, pp 281–293, 1987

  24. Parikh R, Ramanujam R: Distributed processes and the logic of knowledge. In: Parikh R (ed). Proc Workshop on Logic of Programs, pp 256–268, 1985

  25. Taubenfeld G: Impossibility results for decision protocols. Tech Rep 445, Technion, 1987. Revised version appeared as Technion TR-#506, 1988.

  26. Taubenfeld G: On the nonexistence of resilient consensus protocols. Inf Process Lett 37: 285–289 (1991)

    Google Scholar 

  27. Taubenfeld G, Katz S, Moran S: Impossibility results in the presence of multiple faulty processes. In: 9th FCT-TCS Conference, Bangalore, India, 1989, Lecture Notes Comput Sci, vol 405 Veni Madhavan CE (ed), Springer, Berlin Heidelberg New York, pp 109–120, 1989 (to appear in Inf Comput)

    Google Scholar 

  28. Taubenfeld G, Moran S: Possibility and impossibility results in a shared memory environment. In: 3rd Int Workshop on Distributed Algorithms, 1989. Lect Notes Comput Sci, vol 392, Bermond JC, Raynal M (eds), Springer, Berlin Heidelberg New York, pp 254–267, 1989

    Google Scholar 

  29. Tuttle M: Knowledge and distributed computation. Tech Rep MIT/LCS/TR-477, Department of Computer Science, MIT, 1990. PhD Thesis

  30. Wang D-W, Zuck LD: Tight bounds for the sequence transmission problem. In: Proc 8th ACM Symp on Principles of Distributed Computing, pp 73–83, 1989

Download references

Author information

Authors and Affiliations

  1. AT & T Bell Laboratories, 600 Mountain Avenue, 07974, Murray Hill, NJ, USA

    Michael Merritt & Gadi Taubenfeld

Authors
  1. Michael Merritt
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Gadi Taubenfeld
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Michael Merritt received a B.S. degree in Philosophy and in Computer Science from Yale College in 1978, the M.S. and Ph.D. degrees in Information and Computer Science in 1980 and 1983, respectively, from the Georgia Institute of Technology. Since 1983 he has been a member of technical staff at AT & T Bell Laboratories, and has taught as an adjunct or visiting lecturer at Stevens Institute of Technology, Massachusetts Institute of Technology, and Columbia University. In 1989 he was program chair for the ACM Symposium on Principles of Distributed Computing. His research interests include distributed and concurrent computation, both algorithms and formal methods for verifying their correctness, cryptography, and security. He is an editor for Distributed Computing and for Information and Computation, recently co-authored a book on database concurrency control algorithms, and is a member of the ACM and of Computer Professionals for Social Responsibility.

Gadi Taubenfeld received the B.A., M.Sc. and Ph.D. degrees in Computer Science from the Technion (Israel Institute of Technology), in 1982, 1984 and 1988, respectively. From 1988 to 1990 he was a research scientist at Yale University. Since 1991 he has been a member of technical staff at AT & T Bell Laboratories. His primary research interests are in concurrent and distributed computing.

A preliminary version of this work appeared in the Proceedings of the Tenth Annual ACM Symposium on Principles of Distributed Computing, pages 189–200, Montreal, Canada, August 1991

Rights and permissions

Reprints and permissions

About this article

Cite this article

Merritt, M., Taubenfeld, G. Knowledge in shared memory systems. Distrib Comput 7, 99–109 (1993). https://doi.org/10.1007/BF02280839

Download citation

  • Received:

  • Accepted:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02280839

Key words

Search

Navigation