AN EFFICIENT CAUSAL MULTICAST ALGORITHM FOR DISTRIBUTED SYSTEM

Though causal order of message delivery simplifies the design and deve lopment of distributed applications, the overhead of enforcing it is n ot negligible. We claim that a causal order algorithm which does not s end any redundant information is efficient in the sense of communicati on overhead. We characterize and classify the redundant information in to four categories: information regarding just delivered, already deli vered, just replaced, and already replaced messages. We propose an eff icient causal multicast algorithm which prevents propagation of these redundant information. Our algorithm sends less amount of control info rmation needed to ensure causal order than other existing algorithms a nd can also be applied to systems whose communication channels are not FIFO. Since our algorithm's communication overhead increases relative ly slowly as the number of processes increases, it shows good scalabil ity feature. The potential of our algorithm is shown by simulation stu dy.