Technical Report PHD-2011-09

TR#:PHD-2011-09
Class:PHD
Title: Causality, Knowledge and Coordination in Distributed Systems
Authors: Ido Ben-Zvi
Supervisors: Yoram Moses
PDFPHD-2011-09.pdf
Abstract: Effecting coordination across remote sites in a distributed system is an essential part of distributed computing, and also an inherent challenge. Bereft of telepathy and other extrasensory perceptional powers, the processes must rely on message passing in order to achieve it.

In 1978, a fascinating analysis of communication in asynchronous systems was suggested by Leslie Lamport \cite{Lamclocks}. Lamport takes his cue from the theory of special relativity, where the bounded expansion of light through space and time marks the limits of causal affectability: nothing can travel faster than light, and so causal influence too must be limited by the speed of light. Of course, in typical distributed systems nothing as exotic as traveling at near the speed of light ever comes up. But here, in analogy to light, causal influence cannot travel faster than the messages that traverse the inter-process void do. The import of Lamport's paper for distributed computing cannot be over estimated. The causal analysis determines a notion of temporal precedence, a sort of weak notion of time, which is otherwise missing in asynchronous systems. This notion has been extensively utilized in various applications.

Yet Lamport's analysis, and the reliant body of research that has been conducted since, is mostly 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 studies, and characterizes, the intricate combinations of time and message passing that govern causal influence in synchronous systems.

It turns out that knowledge based analysis [FHMV] provides a well tailored formal framework within which causal notions can be studied. As we show, 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 [ChM]. We broaden their analysis and deepen its methodological infrastructure.

In order to study coordination rigorously, 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 underlie 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 temporal precedence order defined by Lamport, 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.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/2011/PHD/PHD-2011-09), rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the PHD technical reports of 2011
To the main CS technical reports page

Computer science department, Technion
admin