분산 트리거 계수 문제를 위한 효율적인 트리 기반 알고리즘

• 영문명: An Efficient Tree-Based Algorithm for the Distributed Trigger Counting Problem
• 발행기관: 한국스마트미디어학회
• 저자명: 이재흥(Jae Heung Lee)
• 간행물 정보: 『스마트미디어저널』Vol10, No.4, 15~20쪽, 전체 6쪽
• 주제분류: 공학 > 컴퓨터학
• 파일형태: PDF
• 발행일자: 2021.12.31

국문 초록

분산 트리거 계수 문제는 외부로부터 트리거를 수신하는 개의 노드로 구성된 분산 시스템에서 수신한 전체 트리거 수의 합이 에 이르렀을 때 이를 사용자에게 알려주는 문제로 무선 센서 네트워크를 포함한 다양한 분산 시스템 환경에서 모니터링과 전역 스냅샷을 위해 사용된다. 이 논문에서는 분산 트리거 계수 문제를 위한 간단하고 효율적인 알고리즘을 제안한다. 제안 알고리즘은 차수가 이고 높이가 2인 트리 구조를 기반으로 동작하며, 남은 트리거 수에 따라 세 단계의 서로 다른 방식으로 동작한다. 제안 알고리즘에서 수신한 전체 트리거 수의 합이 에 이르렀을 때 이를 사용자에게 알려주지 않을 확률이 0임을 증명하였고, 실험을 통해 제안 알고리즘이 CoinRand에 비해 더 작은 메시지 복잡도를 가지며 노드 수가 많지 않을 때는 MaxRcv 또한 더 작음을 보여주었다.

영문 초록

The distributed trigger counting problem is to notify the user when the total number of triggers received from a distributed system consisting of nodes reaches a predefined value . The distributed trigger counting problem is used for monitoring and global snapshots in various distributed systems. In this paper, we propose a simple and efficient algorithm for the distributed trigger counting problem. The proposed algorithm operates based on a tree structure of degree and height 2. The proposed algorithm operates in three different phases based on the remaining number of triggers. Experimental results show that the proposed algorithm has a smaller message complexity than CoinRand, and MaxRcv also performed better when the number of nodes is not large.

목차

Ⅰ. 서론

Ⅱ. 관련 연구

Ⅲ. 제안 알고리즘

Ⅳ. 실험 결과

Ⅴ. 결론

키워드

분산 트리거 계수 문제 분산 시스템 분산 모니터링 전역 스냅샷 Distributed trigger counting problem distributed system distributed monitoring global snapshot