Когда мои 8-летние племянницы спросили меня, что я делаю на своей новой работе, я рассказала им историю:
«Представьте, что вы встречаете человека, который путешествует по всему миру. Если бы он сказал вам, что начал путешествовать час назад, вы бы предположили, что он начал в том же городе, в котором вы находитесь. Если, однако, он начал день назад, он, возможно, уже путешествовал между городами, но вы все еще можете догадаться, что он начал с страны, в которой вы находитесь. Через неделю он мог бы путешествовать по нескольким странам, но, возможно, не пересек континент. Если человек сказал вам, что он путешествовал в течение года, вам было бы очень трудно догадаться, с чего началось его путешествие. Моя работа состоит в том, чтобы выяснить, сколько времени у вас нет, чтобы понять, где он начал свои путешествия ».
Я был счастлив, что смог упростить концепцию«смешивания времени »для 8-летних, но я ”Я предполагаю, что вы, читатель, можете быть немного старше, чем две мои маленькие племянницы.”
Это упрощение относится как к члену математической теории вероятности времени смешивания (которое мы здесь не будем обсуждать), так и к времени смешивания в контексте сети Путаницы.
Необходимость такого термина в нашем контексте выходит из реальных ограничений производительности. Алгоритм выбора подсказок по умолчанию использует случайный обход, который начинается с данной транзакции, называемой начальной точкой. По мере того, как новые транзакции присоединяются к клубку, расстояние от начальной точки до кончиков постоянно увеличивается. Чем больше это расстояние, тем больше вычислительных ресурсов требуется.
По прошествии времени узел, таким образом, захочет заменить старую отправную точку новой, не ухудшая качество процесса выбора наконечника. Если узел выбирает плохую отправную точку, он может прикрепить транзакции, которые не будут быстро выбраны другими узлами. Выбор новой отправной точки, которая выберет те же подсказки, что и старая, желательна. К счастью, выясняется, что чем старше два кандидата, тем больше у них шансов выбрать одни и те же советы. Итак, у нас это есть: время смешивания Клубка — это то, как далеко вы должны вернуться, прежде чем любые две исходные точки-кандидаты будут вести себя одинаково .
Теперь у нас есть приблизительное определение времени смешивания.
Когда процесс выбора наконечника узла становится слишком ресурсоемким, узел может заменить старую начальную точку любой начальной точкой-кандидатом, которая, по крайней мере, так же стара, как время смешивания! Теперь нам нужно только выяснить, каково время смешивания для любого конкретного клубка.Оказывается, что создание аналитической модели для смешивания времени невозможно из-за сложности задачи. Кроме того, хотя расчет времени смешивания для клубка возможен, он слишком громоздок, чтобы его постоянно выполняли узлы. Однако мы можем проводить численные эксперименты на моделируемых узлах и анализировать результаты, чтобы попытаться понять и предсказать поведение времени смешивания.
Мы создали числовой симулятор для создания Tangles со скоростью поступления транзакций λ в единицу времени и с выбором наконечника, который следует алгоритму случайного блуждания с параметром α , и рассчитали время их смешивания.
Для одной такой Путаницы с λ, равным 512, α, равным 0,00069, и около 100 000 транзакций, мы нанесли каждую его транзакцию на двухмерный график, где ось X показывает возраст транзакции, а ось Y показывает, как близко к старым отправным точкам он ведет себя.(где 1 указывает на то же поведение, а 0 указывает на совершенно другое поведение).
Мы видим, что в этом клубке все транзакции старше 69 лет очень похожи на старую отправную точку, поэтому выбор любой из этих транзакций в качестве новой отправной точки не приведет к заметным изменениям в будущем выборе чаевых!
Тем не менее, не все Tangles так хороши. Например, здесь есть Путаница с λ, равным 32, и α, равный 0,0441:
Здесь не все транзакции достигают вершины сюжета. Внизу мы можем видеть транзакции, которые «остались позади», и, следовательно, становятся очень плохими в качестве отправных точек (так как некуда идти вперед в случайном обходе, который начинается там). К счастью, мы можем легко идентифицировать эти транзакции и исключить их в качестве возможных отправных точек. После исключения время смешивания остается в силе — каждая оставшаяся исходная точка-кандидат старше, чем время смешивания, сохранит поведение нашего выбора наконечника.
Соотношение транзакций, которые остаются действительными кандидатами, уже обсуждалось здесь в блоге « Уровни подтверждения в путанице ». Уровень подтверждения Путаницы на первом графике равен 1 (транзакций не осталось) и 0,95 для второго графика.(Осталось 5% транзакций).
Оценка как времени смешивания, так и скорости подтверждения для более чем 200 Связок с различными значениями λ и α приводит к следующей таблице:
Смешивание времени и подтверждение достоверности для разных Tangles
В этой таблице каждая строка представляет определенное значение, а каждый столбец представляет определенное значение. Каждый клубок представлен двумя числами — скорость подтверждения слева и время смешивания справа. Раскрашивая эти значения, мы можем заметить тенденции и сделать наблюдения об отношениях между α, λ, временем смешивания и скоростью подтверждения:
- Путаницы, построенные с более низкими значениями α, являются «более здоровыми» с точки зрения скорости подтверждения — остается меньше транзакций, которые никогда не будут подтверждены. Это означает, что мы будем рады, если все будут использовать низкие значения α, но здесь есть другие соображения (которые подлежат дальнейшему исследованию и совершенно новому сообщению в блоге).
- Время смешивания растет со скоростью входящих транзакций λ, но гораздо медленнее. Умножение λ на 100 увеличивает время перемешивания примерно на 2, по крайней мере, для более низких значений α. Будущая работа будет включать моделирование с большими значениями λ, чтобы увидеть, как эта тенденция продолжается.
- Наибольшее время смешивания имеет Tangles с высокими значениями λ и умеренными значениями α. Что особенного в этом диапазоне значений? Как это поведение будет выглядеть для еще более высоких значений?
Мы продвинулись далеко за пределы истории о путешественнике, подготовили интересные данные и сложные вопросы. Необходим дальнейший анализ и ответы, чтобы определить метод замены начальной точки, а также улучшить наше понимание запутанного поведения Путаницы.
