Applications of Knowledge Theory to Distributed Systems

点击翻译按钮获取中文摘要

This project studies the application of the formal theory of knowledge to the theory of distributed systems. The emphasis is on the application of theoretic techniques to gain lower bounds on classical problems in distributed computing, to design knowledge-based protocols that solve other problems, to study further the concept of knowledge based-protocols and to automate stages in deriving implementations of knowledge-based protocols. The project also studies the role of knowledge in probabilistic systems where one has to cope with both random coin flips and nondeterministic adversary behavior of some elements in the system. Another closely related issue is that of capturing the knowledge of agents who do not have perfect reasoning abilities. One of the goals in investigating knowledge in probabilistic systems and knowledge of non-perfect reasoners is us to determine the type of knowledge that arises in zero knowledge interactive proofs. The PI is investigating the concepts of knowledge used by game-theoreticians and trying to apply their methods and results to problems in distributed systems.