Header menu link for other important links
X
Verifying epistemic protocols under common knowledge
Y. Wang, , J.V. Eijck
Published in
2009
Pages: 257 - 266
Abstract
Epistemic protocols are communication protocols aiming at transfer of knowledge in a controlled way. Typically, the preconditions or goals for protocol actions depend on the knowledge of agents, often in nested form. Informal epistemic protocol descriptions for muddy children, coordinated attack, dining cryptographers, Russian cards, secret key exchange are well known. The contribution of this paper is a formal study of a natural requirement on epistemic protocols, that the contents of the protocol can be assumed to be common knowledge. By formalizing this requirement we can prove that there can be no unbiased deterministic protocol for the Russian cards problem. For purposes of our formal analysis we introduce an epistemic protocol language, and we show that its model checking problem is decidable.
About the journal
JournalProceedings of the 12th Conference on Theoretical Aspects of Rationality and Knowledge, TARK '09