0
가십 스타일 오류 감지에 대해 읽었습니다. 내가 읽고 있던 노트에서 하트 비트가 전파되는 데 O (로그 N) 시간이 걸리는 이유
는 밝혔다 것 :a single heartbeat takes O(log(N)) time to propagate 그러나이 문은
이 왜 어떤 생각을 설명되지 않는 이유는 무엇입니까?
A
답변
2
그런 경우 가장 효과적인 전파 방법은 이진 트리 구조 (또는 임의의 k- 트리)를 사용하기 때문입니다. 첫 번째 노드는 자식에게 메시지를 보내고 자식에게 메시지를 보냅니다. 이진 트리의 높이는 log n입니다. 트리의 모든 수준은 전파 메시지의 한 단계를 나타내므로 전체 시간은 O(log n)과 같습니다.
1
k 노드로 메시지를 보내십시오. 각각은 k 노드에 메시지를 보내고 응답을 수집합니다. 각 홉은 메시지를 수신 한 노드의 수를 k로 곱합니다. 모든 노드는 k^t> = N 일 때 메시지를 수신했습니다.이 작업을 수행하는 데 걸리는 시간은 t, 즉 홉 수에 비례합니다.
K^t는 = N은 => log_k (N)는 t
우리가 log_k (N)에 비례해야하므로, 클록 시간이 t에 비례한다는 것을 알고있는 =.
특히 가십에 익숙하지 않지만이 대답은 대부분의 클러스터 패브릭에서 대부분의 브로드 캐스트 메시지에 적용됩니다.