본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

정보과학회논문지. Journal of KIISE. 정보통신 v.30 no.2, 2003년, pp.143 - 154   피인용횟수: 1

분산 이동 시스템에서 인과적 메시지 전달을 위한 효율적인 프로토콜
An Efficient Protocol for Causal Message Delivery in Distributed Mobile Systems

노성주   (고려대학교 컴퓨터학과UU0000159  ); 정광식   (고려대학교 컴퓨터학과UU0000159  ); 이화민   (고려대학교 컴퓨터교육과UU0000159  ); 유헌창   (고려대학교 컴퓨터교육과UU0000159  ); 황종선   (고려대학교 컴퓨터학과UU0000159  );
  • 초록

    분산 이동 시스템은 단순한 통신 기능에서 작업 흐름 관리, 화상회의, 복제 데이터의 관리, 자원 할당 둥의 서비스를 제공하는 시스템으로 급속히 확대.발전하고 있으며, 이러한 서비스를 제공하는 어플리케이션들은 사용자의 요구를 반영하기 위해 메시지를 인과적 순서로 전달해야 한다. 인과적 메시지 전달을 제공하는 기존의 방법들은 많은 피기백(piggyback) 정보로 인한 통신 오버헤드 혹은 어플리케이션으로 전달하는 메시지의 지연, 이동 호스트의 증가에 대한 확장성, 이동 호스트가 계산의 대부분을 수행하는 둥의 문제점이 있다. 이 논문은 기지국과 이동 호스트 사이의 종속 정보 행렬을 기지국이 유지하며, 즉각 선행자 메시지(immediate predecessor message)에 대한 종속 정보만을 각 메시지에 피기백 하는 방법을 통해 기존 기법의 문제점을 해결하는 효율적인 인과적 메시지 전달 기법을 제안한다. 제안하는 알고리즘은 이전의 알고리즘들과 비교해서 낮은 메시지 오버헤드를 가지며, 메시지를 전달할 때 불필요한 지연(inhibition)을 발생시키지 않는다. 또한 기지국에서 알고리즘의 대부분을 수행하도록 함으로써 이동 호스트의 자원제약과 무선 통신의 낮은 대역폭을 고려하고, 이동 호스트 단위로 인과적 메시지 전달을 이행함으로써 발생하는 처리 지연(processing delay)을 줄여준다.


    There is a growing trend in developing system for distributed mobile system that supports services - job flow management, video conference, replicated data management and resource allocation. Supporting these services, applications have to use causally ordered message delivery. Previous proposals that provide causally ordered message delivery have problems such as communication overhead, message delaying, scalability, computing overload of mobile host. In this paper, we proposed efficient protocol for causally ordered message delivery using the methods that MSS maintains dependency information matrix between MSS and MH, Piggybacking dependency information about each immediate predecessor message. Proposed algorithm, when compared with previous proposals, provides a low message overhead, and low probability of unnecessary inhibition in delivering messages. Also, it consider resource restriction of MH and low bandwidth of wireless communication by computing most of algorithm at MSS, and reduce processing delay by executing causally ordered message delivery a unit of MH.


  • 주제어

    분산 이동 시스템 .   인과적 메시지 전달 .   인과적 장벽 벡터.  

  • 참고문헌 (18)

    1. L. Lamport, 'Time, Clocks and the Ordering of Events in a Distributed System,' Communications of the ACM, pp. 558-565, Vol. 21, No. 7, July 1978 
    2. R. Bagrodia and W-L. Liao. 'Maisie: A Language for Design of Efficient Discrete-Event Simulations,' IEEE Transactions on Software Engineering, April 1994 
    3. Khawar M. Zuberi and Kang G. Shin, 'A Causal Message Ordering Scheme for Distributed Embedded Real-time Systems,' Proceedings of Symposium on Reliable and Distributed Systems, pp. 210-219, October 1996 
    4. Frank Adelstein and Mukesh Singhal, 'Real-Time Causal Message Ordering in Multimedia Systems,' Proceedings of the 15th IEEE International Conference on Distributed Computing Systems, pp. 36-43, June 1995 
    5. Luis Rodrigues and Paulo Verissimo, 'How to Avoid the Cost of Causal Communication in Large-scale Systems,' Proceedings of the Ifh SIGOPS European Workshop, September 1994 
    6. Friedemann Mattern and Stefan Funfrocken, 'A Non-Blocking Lightweight Implementation of Causal Order Message Delivery,' Dagstuhl Seminar on Distributed Systems, pp. 197-213, 1994 
    7. Rosario Aiello, Elena Pagani, and Gian Paolo Rossi, 'Causal Ordering in Reliable Group Communications,' Proceedings ACM SIGCOMM '93 Conference, In Computer Communication Review, pp. 106-115, Vol. 23, No. 4, October 1993 
    8. Kenneth P. Birman and Thomas A. Joseph, 'Reliable Communication in the Presence of Failures,' ACM Transactions on Computer Systems, pp. 47-76, Vol. 5, No. 1, February 1987 
    9. A. Schiper, J Eggli, and A. Sandoz, 'A New Algorithm To Implement Causal Ordering,' Proceedings of the 15th IEEE International Conference on Distributed Computing Systems, pp. 83-91, June 1995 
    10. M. Raynal, A. Schiper, and S. Toueg, 'The causal ordering abstraction and a simple way to implement it,' Information Processing Letters, pp. 343-350, Vol. 39, No. 6, 1991 
    11. Sridhar Alagar and S. Venkatesan, 'Causal Ordering in Distributed Mobile Systems,' IEEE Transactions on Computers, Vol. 46, No. 3, March 1997 
    12. B.R. Badrinath, A. Acharya, and T. Imielinski, 'Impact of Mobility on Distributed Computations,' Operating Systems Review, pp. 15-20, Vol. 27, No. 2, April 1993 
    13. B. R. Badrinath, A. Acharya, and T. Imielinski, 'Structuring Distributed Algorithms for Mobile Hosts,' Proceedings of the 14th International Conference on Distributed Computing Systems, pp. 21-28, June 1994 
    14. R. Prakash and M. Singhal, 'Dependency Sequences and Hierarchical Clocks: Efficient Alternatives to Vector Clocks for Mobile Computing Systems,' ACM/Baltzer Journal on Wireless Networks, pp. 349-360, 1997 
    15. George Coulouris, Jean Dollimore, and Tim Kindberg, Distributed Systems, 2nd ed. New York: Addison-Wesley, 1994 
    16. R. Prakash, M. Raynal, and M. Singhal, 'An Adaptive Causal Ordering Algorithm Suited to Mobile Computing Environments,' Journal of Parallel and Distributed Computing, pp. 190-204, Vol. 42, No.2, March 1997 
    17. A. Acharya and B.R. Badrinath, 'A Framework for Delivering Multicast Messages in Networks with Mobile Hosts,' ACM-Baltzer Journal on Mobile Networks and Applications, pp. 199-219, Vol. 1, No. II, 1996 
    18. Maisie: A Language for Design of Efficient Discrete-Event Simulations , R.Bagrodia;W-L.Liao , IEEE Transactions on Software Engineering / v.,pp.,
  • 이 논문을 인용한 문헌 (1)

    1. Cho, Poong-Youn ; Park, Jae-Won ; Choi, Jae-Hyun ; Lee, Nam-Yong 2009. "An Implementation of Large Scale JMS(Java Message System) for Transmission Time Minimization" 정보과학회논문지. Journal of KIISE. 컴퓨팅의 실제 및 레터, 15(1): 29~37     

 저자의 다른 논문

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기