Distributed dynamic groups on network computers (data replication, dictionary, multicast, communication protocols, weak consistency)
Ariel J. Frank · 1985
Many distributed applications can be solved using mechanisms for selective broadcast communication and data replication within specified subsets of computing hosts, called groups. This dissertation deals with the problem of efficiently organizing dynamic groups on computer networks, especially netcomputers (network computers). Dynamic groups are more effective for large, unreliable communication networks than are static groups. They can be created when required; their membership sets can vary to fit changing needs. Dynamic groups are harder to organize because mechanisms are needed for group creation and termination, and for member recruitment and dismissal. Dynamic groups should be supported by distributed operating systems. Moreover, in distributed systems with a large number of hosts interconnected by an asynchronous communication network, dynamic groups are essential. We develop an architectural framework for a netcomputer. A netcomputer consists of a large number of hosts embedded in a network of interconnected broadcast media. Its addressing conventions support logical addressing of communication resources over the entire network. The key notion in the uniform netcomputer framework is the importance of the broadcast media as the major communication resource. A netcomputer is an effective distributed system architecture for the support of groups and multicast communication. Multicast is the delivery of a packet to a specified subset of hosts. Six general types of multicast techniques are contrasted based on eight defined criteria. Group members may need to multicast to their group several times during an extended interaction period. We show that three multicast techniques are particularly suitable for groups on netcomputers. Dynamic groups are organized using replicated data techniques. A dynamic group is maintained in a decentralized manner using mainly asynchronous messages. We present and prove an original algorithm for efficiently organizing dynamic groups. It has linear storage and communication bandwidth costs per active member and transitory quadratic costs per inactive member. Each member maintains a list of currently known members as replicated data. Members exchange messages frequently enough to keep their local copies consistent. Dynamic groups are shown to provide efficient support for group multicast and maintenance of user replicated data.