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

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

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

Впервые предложена Джоном Майхиллом в 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}$ единиц времени. Время нарастает сверху вниз.

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

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

Первое решение этой задачи было найдено Джоном Маккарти и Марвином Мински и было опубликовано в 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]

Примечания

1. Источник  (неопр.). Дата обращения: 15 августа 2022. Архивировано 15 августа 2022 года.
2. F. R. Moore, G. G. Langdon, A generalized firing squad problem. Information and Control, Volume 12, Issue 3, March 1968, Pages 212—220. DOI
3. Confetti — Firing Squad synchronization problem — YouTube Архивная копия от 26 августа 2022 на Wayback Machine
4. Goto E. A minimal time solution of the firing squad problem. Dittoed course notes for Applied Mathematics, vol.298,pp.52-59. Harvard University, Cambridge(1962)
5. Jacques Mazoyer, A six-state minimal time solution to the firing squad synchronization problem. Theoretical Computer Science, 1987, vol. 50 pp 183—238 DOI
6. Robert Balzer, An 8-state Minimal Time Solution to the Firing Squad Synchronization Problem. Information and Control, 1967, vol.10, pp.22—42 DOI
7. Accueil — Archive ouverte HAL  (неопр.). Дата обращения: 15 августа 2022. Архивировано 15 августа 2022 года.
8. Abraham Waksman, An Optimum Solution to the Firing Squad Synchronization Problem. Information and Control, 1966, vol.9, pp.66—78 DOI
9. The Firing Squad Problem  (неопр.). Дата обращения: 15 августа 2022. Архивировано 15 августа 2022 года.
10. Источник  (неопр.). Дата обращения: 20 августа 2022. Архивировано 20 августа 2022 года.
11. В. И. Варшавский, В. Б. Мараховский, В. А. Песчанский, «Некоторые варианты задачи о синхронизации цепи автоматов», Пробл. передачи информ., 4:3 (1968), 73-83; Problems Inform….
12. Источник  (неопр.). Дата обращения: 2 июня 2023. Архивировано 2 июня 2023 года.
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.

Литература

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