BROWSE
Detail
Journal Article
분산 망에서 자원발견을 위한 결정 알고리즘
Cited - time in 
Share 
Share
- Issue Date
- 2001-12
- Citation
- 정보과학회논문지 : 시스템 및 이론, v.28, no.4, pp.455-462
- ISSN
- 1229-683X
- Publisher
- 한국정보과학회 (KIISE)
- Language
- Korean
- Type
- Journal Article
- Abstract
- 본 논문에서는 네트웍으로 연결된 일련의 장치들이 서로를 발견하는 문제인 자원 발견 (Resource Discovery)문제를 해결하는 알고리즘을 제안한다. 최근 Harchol등은, 장치의 수를 n이라 할 때, O(nlog² n) 연결 통신복잡도와 O(n²log² n) 포인터 통신복잡도를 가지고 O(log² n) 시간복잡도에 이 문제를 해결하는 알고리즘을 제안하였는데, 이는 임의(randomized) 알고리즘이며 종료시점(convergence)을 식별할 방법이 없다는 단점을 가진다. 본 논문에서 우리는 이러한 단점을 없앤 더욱 효율적인 결정 (deterministic) 알고리즘을 제안한다. 제안 알고리즘은, 총 링크 수를 m이라 할 때, O(mlog n) 연결 통신 복잡도와 O(n²log n) 포인터 통신복잡도를 가지고 O(log n) 시간복잡도에 자원발견 문제를 해결한다.
- KSP Keywords
- Resource Discovery