Concurrent common knowledge: defining agreement for asynchronous systems Export

@article{citeulike:6051909, abstract = {In this paper we present a new, knowledgetheoretic definition of agreement designed for asynchronous systems. In analogy with common knowledge, it is calledconcurrent common knowledge. Unlike common knowledge, it is a form of agreement that is attainable asynchronously. In defining concurrent common knowledge, we give a logic with new modal operators and a formal semantics, both of which are based on causality and consequently capture only the relevant structure of purely asynchronous systems. We give general conditions by which protocols attain concurrent common knowledge and prove that two simple and efficient protocols do so. We also present several applications of our logic. We show that concurrent common knowledge is a necessary and sufficient condition for the concurrent performance of distributed actions. We also demonstrate the role of knowledge in taking snapshots for stable property detection and asynchronous broadcasts. In general, applications that involve all processes reaching agreement about some porperty of a consistent global state can be understood in terms of concurrent common knowledge.}, author = {Panangaden, Prakash and Taylor, Kim}, citeulike-article-id = {6051909}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/BF02252679}, citeulike-linkout-1 = {http://www.springerlink.com/content/f31t2771p6082537}, day = {23}, doi = {10.1007/BF02252679}, journal = {Distributed Computing}, month = {September}, number = {2}, pages = {73--93}, posted-at = {2009-10-31 22:22:46}, priority = {4}, title = {Concurrent common knowledge: defining agreement for asynchronous systems}, url = {http://dx.doi.org/10.1007/BF02252679}, volume = {6}, year = {1992} }

TY - JOUR ID - citeulike:6051909 L3 - citeulike-article-id:6051909 N2 - In this paper we present a new, knowledgetheoretic definition of agreement designed for asynchronous systems. In analogy with common knowledge, it is calledconcurrent common knowledge. Unlike common knowledge, it is a form of agreement that is attainable asynchronously. In defining concurrent common knowledge, we give a logic with new modal operators and a formal semantics, both of which are based on causality and consequently capture only the relevant structure of purely asynchronous systems. We give general conditions by which protocols attain concurrent common knowledge and prove that two simple and efficient protocols do so. We also present several applications of our logic. We show that concurrent common knowledge is a necessary and sufficient condition for the concurrent performance of distributed actions. We also demonstrate the role of knowledge in taking snapshots for stable property detection and asynchronous broadcasts. In general, applications that involve all processes reaching agreement about some porperty of a consistent global state can be understood in terms of concurrent common knowledge. IS - 2 JF - Distributed Computing EP - 93 TI - Concurrent common knowledge: defining agreement for asynchronous systems VL - 6 SP - 73 AU - Panangaden, Prakash AU - Taylor, Kim PY - 1992/09/23/ UR - http://dx.doi.org/10.1007/BF02252679 ER -