Publications

Detailed Information

대규모 분산 시스템을 위한 효율적인 분산 트리거 계수 알고리즘

Cited 0 time in Web of Science Cited 0 time in Scopus
Authors

김석현

Advisor
조유근
Major
공과대학 전기·컴퓨터공학부
Issue Date
2013-08
Publisher
서울대학교 대학원
Keywords
분산 트리거 계수 알고리즘분산 시스템분산 알고리즘분산 모니터링전역 스냅샷
Description
학위논문 (박사)-- 서울대학교 대학원 : 전기·컴퓨터공학부, 2013. 8. 조유근.
Abstract
시스템에 참여한 노드의 수가 n이고 검출해야 하는 트리거의 수가 w라 하자. 분산 트리거 계수 알고리즘은 n개 노드가 검출한 전체 트리거의 수가 w가 될 때 이를 사용자에게 알려준다. 트리거의 분포에 대한 어떤 통계적 정보도 미리 주어지지 않으며 트리거의 수는 노드의 수에 비해 매우 많다고 가정한다.

분산 트리거 계수 알고리즘은 분산 모니터링 및 전역 스냅샷 알고리즘에 응용 가능하다. 분산 모니터링은 다양한 분산 시스템에서 시스템의 내부 및 외부를 감시하는데 사용된다. 전역 스냅샷 알고리즘은 분산 시스템 전체의 상태를 저장하여 시스템 복구를 위한 체크 포인트를 (check point) 만드는 용도로 사용된다.

본 논문에서는 대규모 분산 시스템을 위한 효율적인 분산 트리거 계수 알고리즘인 TreeFill과 TreeFill-p를 제시한다. 이들 알고리즘은 라운드를 (rounds) 기반으로 트리거를 검출한다. 각 라운드에서 전체 트리거 중 일부를 검출하고 검출된 트리거의 수가 w가 되면 사용자에게 이를 알려준다. TreeFill은 분산 트리거 계수를 위해 높은 확률로 O(n log(w/n) 개의 메시지를 사용한다. 이는 분산 트리거 계수를 위한 정확한 알고리즘들의 (exact algorithms) 메시지 하한을 만족한다. 또한 TreeFill 알고리즘이 구동할 때 각 메시지가 수신하는 최대 메시지의 수는 높은 확률로 O(log(w/n))이 된다. TreeFill-p는 확률적 알고리즘으로써 낮은 실패 확률을 갖지만, w=O(n^m)인 경우 (m>0) 분산 트리거 계수를 위해 높은 확률로 O(n)개의 메시지를 사용한다. 또한 TreeFill-p 에서 각 노드가 수신하는 메시지의 수는 높은 확률로 O(1)이다. 본 논문에서는 TreeFill 및 TreeFill-p 알고리즘의 성능을 증명하고 다양한 시뮬레이션을 통해 이들 알고리즘의 성능을 검토 하였다.
Language
Korean
URI
https://hdl.handle.net/10371/118925
Files in This Item:
Appears in Collections:

Altmetrics

Item View & Download Count

  • mendeley

Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.

Share