GROUP ROUTING WITHOUT GROUP ROUTING TABLES - AN EXERCISE IN PROTOCOL DESIGN

We present a group routing protocol for a network of processes. The ta sk of the protocol is to route data messages to each member of a proce ss group. To this end, a tree of processes is constructed in the netwo rk, ensuring that each group member is included in the tree. To build this tree, the group routing protocol relies upon the local unicast ro uting tables of each process. Thus, group routing is accomplished by c omposing two protocols: an underlying unicast routing protocol, whose detailed behavior is unknown but its basic properties are given, and a protocol that builds a group tree based upon the unicast routing tabl es. The group routing protocol is developed in three steps. First, a s imple protocol is obtained, and is proven correct. Then, the protocol is refined twice. Each refined protocol improves upon its predecessor by satisfying all of the predecessor's properties plus some additional stronger properties. The final protocol has the property of adapting the group tree to changes in the unicast routing tables without compro mising the integrity of the group tree, even in the presence of unicas t routing loops.