Почему для распространения сердцебиения требуется время O(log N)
Я читал об обнаружении сбоев в стиле сплетен.
В заметках, которые я читал, говорится, что: a single heartbeat takes O(log(N)) time to propagate но это утверждение не объясняется
Есть идеи, почему это так?
2 ответа
Потому что наиболее эффективным способом распространения в таком случае является использование структуры двоичного дерева (или любого k-арного дерева). Первый узел отправляет сообщение своим дочерним элементам, они отправляют сообщение своим дочерним элементам и т. Д. Двоичное дерево имеет высоту log nкаждый уровень в дереве представляет один этап распространения сообщений, поэтому общее время равно O(log n),
Вы начинаете с отправки сообщения на k узлов. Каждый из них отправляет сообщение k узлам и собирает их ответы. Каждый переход умножает количество узлов, которые получили сообщение, на k. Все узлы получили сообщение, когда k^t >= N. Время часов, необходимое для того, чтобы это произошло, пропорционально t, числу прыжков.
k ^ t = N => log_k (N) = t
Мы знаем, что время на часах пропорционально t, поэтому оно должно быть пропорционально log_k(N).
В частности, я не знаком со сплетнями, но этот ответ относится к большинству широковещательных сообщений на большинстве кластерных структур.