טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentMizrahi Tal
SubjectMaintaining Simultaneously Consistent Views of a
Distributed System using Common Knowledge
DepartmentDepartment of Electrical Engineering
Supervisor Professor Yoram Moses
Full Thesis textFull thesis text - English Version


Abstract

In a distributed system it is often necessary for all processes to maintain a consistent view of the world. However, the existence of communication failures in a system may prevent processes from obtaining a consistent view. Continuous consensus is the problem of having each process i maintain at each time k an up-to-date core Mi[k] of information about the past, so that the cores at all processes are guaranteed to be identical. Our analysis assumes an unreliable synchronous system, with an upper bound of t failures. The notion of continuous consensus enables a new perspective on classical problems such as the consensus or the Simultaneous Byzantine Agreement (SBA) problems, and allows for simpler analysis. A simple algorithm for continuous consensus in fault-prone systems with crash and sending omission failures called CONCON is presented, based on a knowledge-based analysis. Continuous consensus is shown to be closely related to common knowledge. Via this connection, the characterization of common knowledge by Moses and Tuttle is used to prove that CONCON is optimal — it produces the largest possible core at any given time. Finally, a second algorithm is presented that provides an optimum uniform solution to continuous consensus, in which all processes (faulty and nonfaulty) maintain the same core information at any given time.