Nested group communication for wide-area networks

Group communication concerns sending messages to receiver groups in distributed systems. A process group comprises a set of processes and encapsulates their internal interactions, thereby simplifying the interactions between user programs and groups of receiving processes. Although the basic idea was proposed a few years ago, few systems or applications take advantage of it due to a lack of a comprehensive understanding of the requirements of group communication with respect to different classes of applications, and a lack of operating system support to meet those requirements. This dissertation consists of two parts that address these deficiencies. The first part provides a comprehensive understanding of process groups by examining their potential applications, and the requirements to the system support expected by these applications. Groups are classified based on their structure and behavior. Also, a uniform treatment of grouping transparency is presented. The second part of this dissertation focuses on a particularly important aspect of group communication — group naming in an internet. For the purposes of maintaining subnet autonomy and reducing traffic on internet links, a nested group model is proposed to allow internet groups to contain other groups as members. By formalizing this nested group model using a name graph, two problems in group name resolutions are identified: resolution loops and resolution duplications. After analyzing existing methods (centralized vs. distributed dynamic methods) and identifying their deficiencies, we propose a novel distributed static method. Instead of detecting loops at the time of name resolution, the static method transforms the system view of the name graph into a special structure which is updated whenever there is a change in group membership. To guarantee correctness, the name graph transformation preserves the property that name resolutions based on the system's view of the name graph are consistent with respect to the users' view. Based on the assumption that name graph updates occur much less frequently than name resolutions, static method trades a higher overhead of name graph updates for a better performance of name resolution to gain an improved over all group message transport performance. In this part of the dissertation, a static shadow tree algorithm is designed and analyzed. The correctness arguments for the algorithm are provided and aspects such as concurrency control and failure handling in name graph updates are investigated as well. A prototype implementation of the algorithm is conducted as an existence proof to demonstrate implementation feasibility and to test the behavior of the algorithm.Science, Faculty ofComputer Science, Department ofGraduat