טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
Ph.D Thesis
Ph.D StudentBurman Janna
SubjectOvercoming the Effect of Asynchrony in Distributed
Algorithms
DepartmentDepartment of Industrial Engineering and Management
Supervisor Professor Shay Kutten
Full Thesis textFull thesis text - English Version


Abstract

This thesis addresses asynchronous, dynamic and unreliable communication networks such as the popular sensor ones. In these networks, components may be inconsistent in their initialization or become inconsistent because of some faults. This phenomenon can be viewed as the “effect of asynchrony”. The main objective of this thesis is to develop distributed basic “building block” algorithms and generic schemes overcoming this effect. Some of the results deal with asynchrony alone. Others involve asynchrony combined with the kind of fault-tolerance, called self-stabilization, which like asynchrony also captures lack of coordination.


Two different asynchronous communication models are considered in the thesis. One is the traditional message-passing model and the other is the model of population protocols (PP) proposed recently for large networks of resource-limited asynchronous mobile sensors (called agents).

PP has certain advantages over alternative models (such as Disruption/Delay-Tolerant Networks). However, the computational power of this model was shown to be rather limited. In the current thesis, the original PP is enhanced by a (weak) notion of a “speed” of the agents. This restricts the asynchrony of the agents’ movements to some (natural) extent, allowing the evaluation of protocols' convergence times. This is impossible in the original model. Using the new model, the thesis studies a basic problem in sensor networks- the problem of information gathering. Protocols are developed step by step, searching for an optimal solution, adapting to the size of the available agents’ memory, making protocols fault-tolerant and, in particular, self-stabilizing. A lower bound on the length of the worst case execution for any information gathering protocol is presented. Next, a generic self-stabilizing transformer is developed. This is an automatic technique to convert a protocol to its self-stabilizing version. As another basic tool, a self-stabilizing phase-clock algorithm is developed. This is a synchronization tool that simulates logical time in an asynchronous system.


In the conventional message-passing model, a self-stabilizing algorithm is designed for the task of a directed spanning tree construction. This is a major task in distributed computing. The previous time optimal algorithm for this task was designed for a model with coarse-grained atomic operations. In the thesis, it is shown that the previous algorithm would not have been correct, if it were to be applied to the “strongly” asynchronous model with fine-grained atomicity. The correctness of the revised version presented here is proven for the more scalable fine-grained asynchronous model.