MIT Department of Electrical Engineering & Computer Science

Cooperative Computing with Fragmentable and Mergable Groups

Chryssis Georgiou
University of Connecticut

Friday, November 5, 1999
1:00 PM
NE43-516
Theory of Distributed Systems Seminars

Abstract

This work considers the complexity of the problem of performing a set of N tasks on a set of P cooperating message-passing processors (P <= N). The processors use a group communication service (GCS) to coordinate their activity. In this setting, due to dynamic changes in the underlying network topology, the processor groups may change over time. GCSs have been recognized as effective building blocks for fault-tolerant applications in this setting. Our results explore the efficiency of fault-tolerant cooperative computation using GCSs. Prior investigation of this area by Dolev et al in [DSS99] focused on competitive lower bounds, non-redundant task allocation schemes and work-efficient algorithms for fragmentation failures. In this work we investigate work-efficient and message-efficient algorithms for fragmentation and merge regroupings.

We present an algorithm that uses GCS and implements a coordinator-based strategy. This algorithm is motivated by the results in [DSS99]. It achieves similar work complexity of O(N.f + N) for fragmentations, where f is the number of new groups created by dynamic fragmentations. Additionally, our algorithm achieves substantially better message complexity of O(N.f + N), and it is able to deal with more general types of group changes. For fragmentations and merges, the work W of the algorithm is O(min{N.f + N, N.P}), and the message complexity M is O(N.f + N + P.m), where f and m denote the number of new groups created by fragmentations and merges respectively. Interestingly, our analysis shows that, while these complexity results depend on f, the work complexity does not depend on the number of groups created as the result of merges.

[DSS99]: S. Dolev, R. Segala, A. Shvartsman, "Dynamic Load Balancing with Group Communication", in Proc. of the 6th International Colloquium on Structural Information and Communication Complexity, 1999.