멀티 트라이얼 기법

슈나이더 외 연구진에 의한 다중 트라이얼 기법은 분산 알고리즘에 채택되어 대칭의 균열이 효율적으로 가능하다.예를 들어, 많은 기업들이 동일한 자원에 동시에 접근하기를 원하는 자원 할당 문제에서 대칭 분리가 필요하다.많은 메시지 전달 알고리즘은 일반적으로 메시지 교환당 대칭을 깨기 위해 하나의 시도를 사용한다.다중 트라이얼 기법은 모든 메시지 교환에 더 많은 시도를 채택함으로써 이러한 접근방식을 초월한다.^[1]

예를 들어, Δ가 그래프에서 최대 정도를 나타내는 O(Δ) 정점 색상을 계산하기 위한 간단한 알고리즘에서, 모든 무색 노드는 임의로 사용 가능한 색상을 선택하고 이웃(현재의 색상)이 동일한 색을 선택하지 않을 경우 이를 유지한다.멀티 트라이얼 기법의 경우, 노드는 모든 통신 라운드에서 선택한 색의 수를 점진적으로 증가시킨다.이 기법은 필요한 통신 회전에서 지수 이상의 감소를 산출할 수 있다.그러나 최대도 Δ가 작은 경우, 예를 들어 리차드 콜과 우지 비슈킨의 (확장) 코인토싱 기법이 존재한다.^[2]

메모들

참조

• Schneider, J. (2010), "A new technique for distributed symmetry breaking" (PDF), Proceedings of the Symposium on Principles of Distributed Computing
• Schneider, J. (2008), "A log-star distributed maximal independent set algorithm for growth-bounded graphs" (PDF), Proceedings of the Symposium on Principles of Distributed Computing