Перколяция начальной загрузки

В статистической механике бутстреп -перколяция — это процесс перколяции , при котором случайная начальная конфигурация активных ячеек выбирается из решетки или другого пространства, а затем ячейки с небольшим количеством активных соседей последовательно удаляются из активного набора до тех пор, пока система не стабилизируется. Порядок, в котором происходит это удаление, не влияет на окончательное стабильное состояние.

Когда порог активных соседей, необходимый для выживания активной ячейки, достаточно высок (в зависимости от решетки), единственными стабильными состояниями являются состояния без активных ячеек или состояния, в которых каждый кластер активных ячеек бесконечно велик. Например, на квадратной решетке с окрестностью фон Неймана существуют конечные кластеры, по крайней мере, с двумя активными соседями на ячейку кластера, но когда требуются три или четыре активных соседа, любой стабильный кластер должен быть бесконечным. Поскольку для того, чтобы оставаться активными, необходимы три активных соседа, бесконечный кластер должен бесконечно растягиваться в трех или четырех возможных кардинальных направлениях, и любые конечные дыры, которые он содержит, обязательно будут прямоугольными. В этом случае критическая вероятность равна 1, а это означает, что когда вероятность того, что каждая ячейка будет активной в начальном состоянии, меньше 1, то почти наверняка бесконечного кластера не существует. Если исходное состояние активно всюду, кроме квадрата n × n , внутри которого неактивна по одной ячейке в каждой строке и столбце, то эти одноклеточные пустоты сольются в пустоту, покрывающую весь квадрат тогда и только тогда, когда неактивные ячейки имеют структуру разделимой перестановки . В любом более высоком измерении и для любого порога существует аналогичная критическая вероятность, ниже которой все ячейки почти наверняка станут неактивными, а выше которой некоторые кластеры почти наверняка выживут.

Бутстрап-перколяцию можно интерпретировать как клеточный автомат , напоминающий «Игру жизни» Конвея , в которой живые клетки умирают, когда у них слишком мало живых соседей. Однако, в отличие от «Жизни» Конвея, мертвые клетки никогда больше не становятся живыми. Ее также можно рассматривать как модель эпидемии , в которой неактивные клетки считаются инфицированными, а активные клетки со слишком большим количеством инфицированных соседей заражаются сами. Наименьший порог, позволяющий некоторым ячейкам исходного кластера выжить, называется вырождением его графа смежности, а остаток кластера, выживший с порогом k, называется k -ядром этого графа.

Одно из применений перколяции начальной загрузки возникает при изучении отказоустойчивости распределенных вычислений . Если некоторые процессоры в большой сетке процессоров выходят из строя (становятся неактивными), то может также потребоваться деактивировать другие процессоры со слишком малым количеством активных соседей, чтобы сохранить высокую связность оставшейся сети. Анализ начальной загрузки можно использовать для определения вероятности отказа, которую может допустить система.