A Load Balancing Algorithm of Distributed System on SBIBD Networked
김성열, 이옥빈 · 한국전자통신학회 학술대회지 · 2013
분산된 시스템에서 부하균형을 유지하기 위해서는 네트워크상의 각 노드는 다른 노드들과 워크로드정보를 공유하게 된다. 네트워크상의 노드의 수를 v라 할 때, 상호정보교환은 O(v²)의 트래픽을 발생시킨다. 이 논문에서는 SBIBD의 부분집합인 (v,p+1,1)디자인을 이용한 부하균형 알고리즘을 제안한다. 여기에서 노드의 수 v에 대하여 v=p²+p+1이 성립한다. 이 알고리즘의 동작은 각각의 노드에 분산 되어 수행되는데, 각 노드가 모든 노드로부터 정보를 수신하기 위해서 오직 2라운드의 정보교환을 요구하며 이를 위한 통신 복잡도는 O(v√v)가 된다. 2라운드의 정보교환을 통하여 각각의 노드는 O(√v)의 통신 복잡도를 갖는다.