טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
Ph.D Thesis
Ph.D StudentBen-Zvi Ido
SubjectCausality, Knowledge and Coordination in Distributed
Systems
DepartmentDepartment of Computer Science
Supervisor Professor Yoram Moses
Full Thesis textFull thesis text - English Version


Abstract

Effecting coordination across remote sites in a distributed system is an essential part of distributed computing, and also an inherent challenge as the processes must rely on message passing in order to achieve it.

In 1978, an analysis of communication in asynchronous systems was suggested by Leslie Lamport. Yet Lamport’s analysis, and the reliant body of research that has been conducted since, is  limited to systems that are asynchronous. In this thesis we go beyond the existing body of literature by investigating causality in synchronous systems. In such systems, the boundaries of causal influence are not charted out exclusively by message passing. Here time itself, passing at a uniform (or almost uniform) rate for all processes, is also a medium by which causal influence may fan out. This thesis characterizes the combinations of time and message passing that govern causal influence in synchronous systems.

Formally, the thesis makes use of knowledge based analysis. The formal notion of knowledge is highly appropriate for characterizing causal influence in terms of information flow. The idea of using knowledge in such circumstance was first brought up by Chandy and Misra in. We broaden their analysis and deepen its methodological infrastructure.

We define several generic classes of coordination problems, that pose various temporal ordering requirements on the participating processes. These coordination problems provide natural generalizations of real life requirements. We then analyze the causal conditions that underly suitable solutions to these problems. The analysis is conducted in two stages: first, the temporal ordering requirements are reduced to epistemic conditions. Then, these epistemic conditions are characterized in terms of the causal communication patterns that are necessary and sufficient to bring them about.

Whilst in asynchronous systems causal influence is characterized by a straightforward application of the  Lamport's temporal precedence order, in synchronous systems the causal communication patterns are more complex. We identify several such patterns, each of them being a minimal requirement in some class of coordination problems: we start with syncausality, an immediate generalization of Lamport’s ordering, and move on to centipedes and centibrooms, structures that combine message passing and timing constraints. These latter two are shown to be special cases of the generalized centipede. These patterns lead us up in an increasingly complex hierarchy of ordering requirements, culminating in a characterization of the minimal communication pattern that is necessary to ensure any specification given as a partial ordering on the temporal precedence of events.