An Efficient Causal Multicast Algorithm for Distributed System

Ik Hyeon JANG; Jung Wan CHO; Hyunsoo YOON

An Efficient Causal Multicast Algorithm for Distributed System

Ik Hyeon JANG, Jung Wan CHO, Hyunsoo YOON

Full Text Views

0

Cite this

Summary :

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.

Publication: IEICE TRANSACTIONS on Information Vol.E81-D No.1 pp.27-36

Publication Date: 1998/01/25

Publicized

Online ISSN

DOI

Type of Manuscript

Category: Computer Systems

Cite this

Copy

Ik Hyeon JANG, Jung Wan CHO, Hyunsoo YOON, "An Efficient Causal Multicast Algorithm for Distributed System" in IEICE TRANSACTIONS on Information, vol. E81-D, no. 1, pp. 27-36, January 1998, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/e81-d_1_27/_p

Copy

@ARTICLE{e81-d_1_27,
author={Ik Hyeon JANG, Jung Wan CHO, Hyunsoo YOON, },
journal={IEICE TRANSACTIONS on Information},
title={An Efficient Causal Multicast Algorithm for Distributed System},
year={1998},
volume={E81-D},
number={1},
pages={27-36},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={January},}

Copy

TY - JOUR
TI - An Efficient Causal Multicast Algorithm for Distributed System
T2 - IEICE TRANSACTIONS on Information
SP - 27
EP - 36
AU - Ik Hyeon JANG
AU - Jung Wan CHO
AU - Hyunsoo YOON
PY - 1998
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E81-D
IS - 1
JA - IEICE TRANSACTIONS on Information
Y1 - January 1998
AB - 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.
ER -