Задача синхронизации стрелков

Зада́ча синхрониза́ции стрелко́в — задача из области информатики и теории клеточных автоматов.

Неполное решение: $2^{m}$ роботов с 4 состояниями синхронизируются за $2^{m}-1$ тактов (на такт дольше оптимума). Видна волна сигналов, прошедшая через весь строй и отразившаяся обратно. Сигнал к выстрелу — у тебя флаг, у соседей ружьё (или наоборот).

Впервые предложена Джоном Майхиллом в 1957 году и опубликована (с решением) в 1962 году Эдвардом Муром. Название связано с поведением солдат при расстреле или ружейном салюте — все солдаты стреляют одновременно по сигналу.

Формулируется следующим образом: можно ли так запрограммировать одномерный клеточный автомат конечной длины, чтобы из стартового состояния G●●…●●● все клетки одновременно перешли в состояние FFF…FFF, независимо от длины цепочки, если обязательно правило перехода ●●●→● и его аналоги для концов цепочки ⌀●●→●, ●●⌀→●? Простым языком:

• $n\geqslant 2$ роботов (конечных автоматов) с ружьями стоят шеренгой. У автоматов как минимум три состояния ●, G и F — «исходное», «командир» и «выстрел». Помимо этих трёх, можно добавить сколько угодно промежуточных состояний.
• Роботы действуют независимо по одной программе и общаются только по цепочке: по сигналам барабана (синхронизатора) в зависимости от своего состояния в момент $t-1$ и состояния двух соседей переходят в новое состояние. Исключение — крайние роботы, у которых только один сосед; у них собственные программы.
• Все три программы, если робот и его соседи в исходном состоянии, ничего не должны делать.
• Все роботы стоят в исходном состоянии и ничего не делают. В момент $t=0$ крайнего левого переводят в состояние «командир».
• Существуют ли такие три программы (набор состояний и три комплекта правил перехода — для командира, замыкающего и остальных роботов), чтобы при любом $n$ они передали по цепочке приказ командира и одновременно (на одном ударе барабана) перешли в состояние «выстрел»?

Поскольку сигнал распространяется по шеренге со скоростью 1 позиция за такт (в теории клеточных автоматов это называется «скорость света»), очевидно, время синхронизации будет возрастать с возрастанием $n$.

Программист, чтобы решить задачу на строях разумной длины, добавил бы роботу несколько счётчиков — но это означает, что у робота, оснащённого 16-битным счётчиком, 65536 состояний. А в теории роботы должны работать на строях любой конечной длины — и миллионы, и миллиарды.

История

Одно из решений задачи с использованием 15 состояний у каждого стрелка и $3n$ единиц времени. Время нарастает сверху вниз.

Решение продолжительностью $2n-2$ единиц времени. Время нарастает сверху вниз.

Открытая математическая проблема

Существует ли решение задачи синхронизации стрелков в пять состояний — для любого $n$, не обязательно оптимальное по времени?

Первое решение этой задачи было найдено Джоном Маккарти и Марвином Мински и было опубликовано в Sequential Machines Эдвардом Муром.

Решение, требующее минимальное время, было найдено в 1962 профессором Эйити Гото из МТИ. Оно использует несколько тысяч состояний и требует ровно $2n-2$ единиц времени для $n$ роботов. Легко доказывается (см. ниже), что более эффективных по времени решений не существует.

Оптимальное решение, использующее всего шесть состояний (включая конечное «выстрел»), было найдено Жаком Мазойером в 1987 году. Ранее Роберт Бальцер компьютерным перебором доказал, что решений с четырьмя состояниями клеток не существует. Питер Сандерс позднее выяснил, что поисковая процедура Бальцера была неполной, однако исправив процедуру, получил тот же результат. В 2010-е эволюционным перебором получены сотни разных решений с шестью состояниями. До сих пор неизвестно, существует ли решение с пятью состояниями клеток.

Также пытаются побить рекорд по количеству задействованных правил перехода (включая требуемое, но неиспользуемое правило для командира ⌀●●→●. В решении Мазойера 119 правил. Существует неоптимальное по времени решение с шестью состояниями и 78-ю правилами, и оптимальное — с 80-ю.

Находят неполные решения с четырьмя состояниями — например, синхронизирующие шеренгу из $2^{m}$ роботов.

Простейшее решение

Простейшее решение задачи описывает две волны состояний, распространяющиеся по шеренге роботов, одна из которых движется в три раза быстрее другой. Быстрая волна отражается от дальнего края ряда и встречается с медленной в центре. После этого две волны разделяются на четыре, движущиеся в разные стороны от центра. Процесс продолжается, каждый раз удваивая число волн, пока длина отрезков ряда не станет равной 1. В этот момент все роботы стреляют. Это решение требует $3n$ единиц времени для $n$ солдат.

Решение, требующее минимального времени

Здесь описано достаточно простое решение из 16 состояний, описанное Абрахамом Ваксманом в 1966 году. Командир посылает соседнему роботу сигналы $S_{1},~~S_{2},~~S_{3}~~\dots ~~S_{i}\dots$ с частотами $1,~{\frac {1}{3}},~{\frac {1}{7}},~\dots ~{\frac {1}{2^{i-1}-1}}\dots$ Сигнал $S_{1}$ отражается от правого края ряда и встречает сигнал $S_{i}$ (для $i\geq 2$) в ячейке $n/2^{i-1}.$ Когда $S_{1}$ отражается, он также создает нового командира на правом конце.

Сигналы $S_{i}$ генерируются с использованием вспомогательных сигналов, распространяющихся влево. Каждый второй момент времени обычный сигнал генерирует вспомогательный сигнал, распространяющийся влево. $S_{1}$ движется самостоятельно со скоростью 1, тогда как более медленные сигналы движутся только при получении вспомогательных сигналов.

Доказательство минимального времени

Если между командиром (инициатором стрельбы) и ближайшим концом $k$ роботов, на синхронизацию нужно не менее $2n-2-k$ шагов.

Частный случай: если командир на краю — то $2n-2$ шага.

Доказательство. Допустим, существует тройка программ, которая решает задачу синхронизации, и для некоторых $n$ и $k$ сумеет выстрелить за $t<2n-2-k$. Считаем, что командир ближе к левому концу.

Любой сигнал проходит от робота к роботу не быстрее, чем с так называемой «скоростью света» — 1 позиция за шаг времени. Действия первого робота в момент $t$ зависят от первых двух роботов на момент $t-1$, от первых трёх на момент $t-2$, …, от всех $n$ роботов на момент $t_{1}=t-(n-1)\leqslant n-2-k$. В этот момент последний робот всё ещё в исходном состоянии (сигнал к нему приходит к моменту $n-1-k$).

А значит, если добавить к правому концу ещё $(n+2)$-х роботов, в момент $t_{1}$ состояние первых $n$ роботов будет таким же, для первого робота ничего не изменится, и он выстрелит на том же шаге $t$. Последний $(2n+2)$-й на шаге $t$ останется в исходном состоянии — до него сигнал не успеет дойти. Так что данная тройка программ — не решение. Противоречие.

Точно так же доказывается и другая нижняя грань, $n-1+k$ шагов, но число $2n-2-k$ не меньше.

Примечание. Дополнительные требования к $n$ и $k$, если $n$ не ограничено сверху, могут дать выигрыш по количеству состояний, но не по времени, и действительно существует обобщение решения Ваксмана из 17 состояний, работающее для любых $n$ и $k$ за $2n-2-k$ шагов.

Обобщения

Было предложено и изучено несколько более общих формулировок задачи, включая ряды с произвольным расположением командира, замкнутые кольца, квадраты, кубы, графы Кэли и графы общего вида.

Удалось найти существование решения для линейного строя, если каждый робот должен дать сигнал за $\tau _{i}$ тактов до выстрела, робот знает максимальное и своё $\tau _{i}$, и соответственно программируется, при этом роботы с одинаковой задержкой будут иметь одинаковые программы. Простейшее решение — дать роботам $\max \tau _{i}$ дополнительных состояний и столько же тактов на синхронизацию, но можно обойтись и без этой задержки, если строй достаточно длинный. Сложность каждой отдельной программы $a^{2\max \tau _{i}+1}$ (по сути, он помнит состояние $2\max \tau _{i}+1$ робота из классической задачи).

Разновидность задачи византийских генералов, когда все исправные процессоры должны синхронизироваться в отсутствие сигналов точного времени, независимо от работы процессоров-вредителей, обозвали «византийской задачей синхронизации стрелков».

Точное минимальное время синхронизации на разных строях
(найдено решение и доказано, что быстрее не бывает)

Форма строя	Минимальное время
Шеренга, между командиром и ближним краем $k$ роботов	$2n-2-k$
Кольцо	$n-1$
Кольцо с односторонним распространением информации	$2n-2$
Каре $m\times n$ с командиром на углу	$m+n+\operatorname {max} \{m,n\}-3$
Квадрат $n\times n$ с командиром на углу	$2n-2$
Куб $n\times n\times n$ с командиром в вершине	$3n-3$

Литература

• Shinahr, Ilka. Two- and three-dimensional firing-squad synchronization problem (англ.) // Information and Control : journal. — Academic Press, 1974. — Vol. 24. — P. 163—180. — doi:10.1016/S0019-9958(74)80055-0.

Ссылки

• «Firing Squad Problem»
• «On Formulations of Firing Squad Synchronization Problems»
• «Firing squad synchronization»