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

An Efficient Tree-Based Algorithm for the Distributed Trigger Counting Problem

분산 트리거 계수 문제는 외부로부터 트리거를 수신하는 개의 노드로 구성된 분산 시스템에서 수신한 전체 트리거 수의 합이 에 이르렀을 때 이를 사용자에게 알려주는 문제로 무선 센서 네트워크를 포함한 다양한 분산 시스템 환경에서 모니터링과 전역 스냅샷을 위해 사용된다. 이 논문에서는 분산 트리거 계수 문제를 위한 간단하고 효율적인 알고리즘을 제안한다. 제안 알고리즘은 차수가 이고 높이가 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.