For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
An Efficient Causal Multicast Algorithm for Distributed System
Ik Hyeon JANG Jung Wan CHO Hyunsoo YOON
IEICE TRANSACTIONS on Information and Systems
Publication Date: 1998/01/25
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Computer Systems
causal order, causal relation, causal multicast, distributed system, distributed computation,
Full Text: PDF(958.5KB)>>
Though causal order of message delivery simplifies the design and development of distributed applications, the overhead of enforcing it is not negligible. We claim that a causal order algorithm which does not send any redundant information is efficient in the sense of communication overhead. We characterize and classify the redundant information into four categories: information regarding just delivered, already delivered, just replaced, and already replaced messages. We propose an efficient causal multicast algorithm which prevents propagation of these redundant information. Our algorithm sends less amount of control information needed to ensure causal order than other existing algorithms and can also be applied to systems whose communication channels are not FIFO. Since our algorithm's communication overhead increases relatively slowly as the number of processes increases, it shows good scalability feature. The potential of our algorithm is shown by simulation study.