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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• 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»