실시간 환경을 위한 효율적인 인과순서 알고리즘
An Efficient Causal Order Algorithm for Real-Time Enviroment
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
인과순서 메시지 전달 알고리즘은 모든 전송되는 메시지가 인과순서로 전달되도록 한다. 인과순서를 유지하기 위해서는 전송되는 모든 메시지가 제어정보를 가지고 다녀야 하고, 제어정보의 크기는 관련된 프로세스의 수에 비례하여 커지게 되므로 제어정보의 크기를 줄이는 것은 분산시스템의 주요한 관심사가 되어 왔다. 본 논문에서는 실시간 성질을 가지는 멀티미디어 자료를 위한 효율적인 △-인과순서 알고리즘을 제안하고 평가하였다. 제안된 알고리즘은 전송 부하를 줄이기 위하여 인과순서를 유지하는데 필수적이지 않은 정보를 가능한 이른 시기에 찾아내어 제거하며, 기존 알고리즘보다 훨씬 적은 전송부하를 가지게 된다.An Efficient Causal Order Algorithm for Real-Time EnvironmentIk-hyeon Jang†
Abstract
Causal order of message delivery algorithm ensures that every transmitted message is delivered in causal order. It should be noted that control information should be transmitted with each message in order to enforce causal order. Hence, it is important to reduce this communication overhead because the impact of the overhead increases proportionally with the number of related processes. In this paper we propose and evaluate effective △-causal order algorithm for multimedia data which have real-time property. To reduce transmission overhead, proposed algorithm eliminates redundant information as early as possible which is not explicitly required for preserving causal order. Average communication overhead of our algorithm is much smaller than other existing algorithms.
참고문헌 (14)
- F. Adelstein, "Real-Time Causal Message Ordering in Multimedia Systems", pp.36~43
- R. Baldoni, "On the Minimal Information to Encode Timestamps in Distributed Computations", 84(3), pp.159~166
- R. Baldoni, "Efficient △-Causal Broadcasting", pp.263~271
- K. Birman, "Reliable Communication in the Presence of Failure", pp.47~76 (1987)
- W. Cai, "Causal Order Delivery in a Multicast Environment: An Improved Algorithm", 62(1), pp.111~131
- D. Ferrari, "Client Requirements for Real-Time Communication Services", pp.65~72 (1990)
- I. Jang, "An Efficient Causal Multicast Algorithm for Distributed System", E81-D(1), pp.27~36 (1998)
- A. Kshemkalyani, "An Optimal Algorithm for Generalized Causal Message Ordering", pp.87~94
- L. Lamport, "and the Ordering of Events in a Distributed System Comm. of the ACM", 21(7), pp.558~564 (1978)
- R. Prakash, "An Efficient Causal Ordering Algorithm for Mobile Computing Environments", pp.744~751
- M. Raynal,A. Schiper,, "The Causal Ordering Abstraction and a Simple Way to Implement It", 39, pp.343~350 (1991)
- L. Rodrigues, "Deadline-Constrained Causal Order", pp.234~243
- A Generic Model, "Causal Delivery Protocols in Real-Time Systems: A Generic Model", 10(1), pp.45~73 (1996)
- R. Yavatkar, "A Protocol for Coordination and Temporal Synchronization in Multimedia Collaborative Applications", pp.606~613 (1992)