טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentAsa Dan
SubjectUsing Time Without Clocks
DepartmentDepartment of Electrical Engineering
Supervisor Full Professor Moses Yoram
Full Thesis textFull thesis text - English Version


Abstract

Even in the absence of clocks, time bounds on the duration of actions enable to deduce information concerning the relative timing of distinct events.This information can be used for distributed coordination, where the relative timing of events at different sites has to be finely tuned. This thesis initiates an investigation of coordination in such a setting. Without bounds, the only timing information that can be deduced is based on the order of actions with prescribed order (such as a message sending and receiving, where the receiving must come only after the sending). In our model, where bounds are introduced, additional timing information can be obtained. For that cause, a new communication structure called a zigzag pattern is introduced, and shown to guarantee bounds on the relative timing of events in this clockless model. Indeed, we prove that zigzag patterns are necessary and sufficient for establishing that events occur in a manner that satisfies prescribed bounds. In a precise sense, zigzag patterns generalize the notion of a message chain, which plays a central role in asynchronous systems, in which no bounds are available. We capture when a process can know that an appropriate zigzag pattern exists, and use this to provide

necessary and sufficient conditions for timed coordination of events using a full-information protocol in the clockless model.