Implementation and evaluation of an algorithm for the omni-do problem using the ensemble group communication service

Abstract

A lot of research has been conducted for studying cooperation in distributed systems. The abstract problem of performing a set of tasks by a set of distributed fault-prone processors is generally known as DO-ALL. In partitionable networks DO-ALL is known as OMNI-DO. Despite the active research on this subject, a lot of it remains theoretical and there are not any empirical studies on proposed solutions and their behaviour in realistic environments. We investigate recent research on this subject and implement an algorithm proposed for solving the OMNI-DO problem. The algorithm uses a group communication service to handle processor coordination when regroupings occur due to dynamic changes in the underlying network structure. In this thesis Ensemble GCS is studied and used in the implementation. A coordinator based approach is used for dissemination of knowledge, regarding completed tasks, within a group. A naturally random load balancing rule is used for inter-group task scheduling. Finally, we empirically evaluate the algorithm with respect to work, message and execution time metrics. The algorithm performs well and our results fall within the results of the theoretical analysis. An additional overhead during regroupings is identified (caused by the way new groups are formed by the group communication service) and an implementation solution is proposed.