분산 트리거 계수 문제를 위한 효율적인 트리 기반 알고리즘
An Efficient Tree-Based Algorithm for the Distributed Trigger Counting Problem
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
분산 트리거 계수 문제는 외부로부터 트리거를 수신하는 개의 노드로 구성된 분산 시스템에서 수신한 전체 트리거 수의 합이 에 이르렀을 때 이를 사용자에게 알려주는 문제로 무선 센서 네트워크를 포함한 다양한 분산 시스템 환경에서 모니터링과 전역 스냅샷을 위해 사용된다. 이 논문에서는 분산 트리거 계수 문제를 위한 간단하고 효율적인 알고리즘을 제안한다. 제안 알고리즘은 차수가 이고 높이가 2인 트리 구조를 기반으로 동작하며, 남은 트리거 수에 따라 세 단계의 서로 다른 방식으로 동작한다. 제안 알고리즘에서 수신한 전체 트리거 수의 합이 에 이르렀을 때 이를 사용자에게 알려주지 않을 확률이 0임을 증명하였고, 실험을 통해 제안 알고리즘이 CoinRand에 비해 더 작은 메시지 복잡도를 가지며 노드 수가 많지 않을 때는 MaxRcv 또한 더 작음을 보여주었다.
Abstract
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.
참고문헌 (15)
- V. T. Chakaravarthy, "Efficient Decentralized Algorithms for the Distributed Trigger Counting Problem", Theory Computing Systems, 51(4), pp.447~473 (2012)
- M. K. Singh, "A Survey of Wireless Sensor Network and its types", Proc. of the 2018 International Conference on Advances in Computing, Communication Control and Networking (ICACCCN), pp.326~330 (2018)
- 이진우, "무선 센서 네트워크를 위한 효율적인 클러스터링 기법", 스마트미디어저널, 6(4), pp.24~31 (2017), (사)한국스마트미디어학회
- 김영관, "기계학습 분산 환경을 위한 부하 분산 기법", 스마트미디어저널, 10(1), pp.25~31 (2021), (사)한국스마트미디어학회[DOI]
- C. Hsin, "A distributed monitoring mechanism for wireless sensor networks", Proc. of the 1st ACM workshop on Wireless security(WiSE '02), pp.57~66 (2002)
- 안성열, "오픈소스 Prometheus 모니터링 시스템의 사전연구", 스마트미디어저널, 10(2), pp.110~118 (2021), (사)한국스마트미디어학회[DOI]
- K. M. Chandy, "Distributed snapshots : determining global states of distributed systems", ACM Transactions on Computer Systems, 3(1), pp.63~75 (1985)
- A. D. Kshemkalyani, "Fast and Message-Efficient Global Snapshot Algorithms for Large-Scale Distributed Systems", IEEE Transactions on Parallel and Distributed Systems, 21(9), pp.1281~1289 (2010)
- R. Garg, "Efficient Algorithms for Global Snapshots in Large Distributed Systems", IEEE Transactions on Parallel Distributed Systems, 21(5), pp.620~630 (2010)
- V. T. Chakaravarthy, "Improved Algorithms for the Distributed Trigger Counting Problem", 2011 IEEE International Parallel & Distributed Processing Symposium, pp.515~523 (2011)
- S. Kim, "An optimal distributed trigger counting algorithm for large-scale networked systems", Simulation, 89, pp.846~859 (2013)
- Y. Emek, "Efficient Threshold Detection in a Distributed Environment : Extended Abstract", Proc. of the 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, pp.183~191 (2010)
- C. Chang, "Distributed Trigger Counting Algorithms for Arbitrary Network Topology", Wireless Communication Mobile Computing, 16(16), pp.2463~2476 (2016)
- S. Kim, "DDR-coin : An Efficient Probabilistic Distributed Trigger Counting Algorithm", Sensors, 20(22), pp.1~24 (2020)
- "Distributed Trigger Counting" (2021)[URL]