Problem plutonu egzekucyjnego

Problem synchronizacji plutonu egzekucyjnego – zagadnienie z zakresu informatyki, polegające na próbie konstrukcji takiego automatu komórkowego, który zaczynając od pojedynczej nieaktywnej komórki, osiągnie stan, w którym wszystkie komórki osiągną jednocześnie stan aktywności. Problem został sformułowany przez Johna Myhilla w 1957, a pierwsze jego rozwiązanie opublikował w 1962 r. Edward Moore.

Problem

Dowódca plutonu żołnierzy ustawionych w szereg chce wydać rozkaz, który ma być wykonany przez cały oddział^[a] w tym samym momencie. Liczebność plutonu powoduje, że nie wszyscy żołnierze mogą usłyszeć polecenie bezpośrednio od dowódcy. W związku z tym dowódca przekazuje rozkaz pierwszemu żołnierzowi w szeregu. W danej jednostce czasu każdy żołnierz może skontaktować się tylko z jednym ze swoich sąsiadów. Dowódca nie podejmuje żadnych dodatkowych działań. Ponadto z powodu nieznanej liczebności oddziału nie można z góry określić momentu wystrzału.

Bardziej formalnie, problem polega na rozprowadzeniu informacji oraz zsynchronizowaniu rozpoczęcia pewnej akcji. Każdy żołnierz może przechowywać skończoną liczbę informacji. Jego działanie w i+1 jednostce czasu może zależeć tylko od akcji wykonanej w i-tej jednostce przez jego samego oraz obydwu sąsiadów. W danej jednostce czasu każdy żołnierz może skomunikować się tylko z jednym wybranym żołnierzem.

W kategoriach teorii automatów komórkowych, na oddział można spojrzeć jako skończony zbiór komórek ustawionych w jednym rzędzie, które na początku znajdują się w tym samym stanie nieaktywnym. Każda komórka może zmienić swój stan kontaktując się z dwoma sąsiednimi. Rozwiązanie problemu polega na takim zaprogramowaniu automatu aby wszystkie komórki osiągnęły stan aktywności w tym samym momencie, niezależnie od ich liczby.

Rozwiązanie optymalne czasowo

Zakładamy, że mamy n żołnierzy w jednym szeregu (łącznie z dowódcą), oraz sygnały rozchodzą się wzdłuż linii z prędkością co najwyżej jednego żołnierza w każdej jednostce czasu. W związku z tym optymalne rozwiązanie musi zająć co najmniej 2n-2 jednostek czasu – tyle czasu zajmie przejście informacji od pierwszego do ostatniego i z powrotem. Poniższe rozwiązanie zostało zaproponowane w 1966 roku przez Abrahama Waksmana^[1], który używając automatów mogących przyjąć 16 stanów pośrednich skonstruował optymalne rozwiązanie.

Mamy sześć podstawowych stanów, cztery mają podstany:

Q: Startowy stan „spokojny”
T: Końcowy stan „ostrzał”
R: Wyzwalający sygnał dla stanu B
- R0 – Sygnał w lewo
- R1 – Sygnał w prawo
B: Stan generujący stan P
- B0 – Blokuje stan R
- B1 – Przechodzi przez stan R
P: Stan generujący stan A i prowadzi do stanu końcowego jeśli sąsiedzi są w stanie P
- P0 – Generuje A0xx
- P1 – Generuje A1xx
A: Stan sygnalizujący
- A000, A111, A010, A011, A100, A101, A110
- A0xx – generuje stan R bez opóźnienia
- A1xx – Po jednej jednostce opóźnienia generuje stan R
- Każdy Ax00 i Ax01 – Propaguje w lewo
- Każdy Ax10 i Ax11 – Propaguje w prawo

Dodatkowo mamy dwa dodatkowe stany zastępcze:

φ – Zewnętrzny stan, żadna z maszyn nie jest w tym stanie
γ – Sąsiedzi niewymienieni jawnie

Kilka faktów:

Każdy sygnał A może być parzysty lub nieparzysty, w zależności czy jest obecnie na maszynie parzystej czy nieparzystej. Parzystość jest określana od maszyny, która jest źródłem sygnału.
Każda maszyna z parzystym sygnałem A generuje nowy sygnał R, który rozchodzi się w kierunku przeciwnym do sygnału A.
Każdy z B sygnałów zmieni swój typ jeśli przetnie się z sygnałem R. Jeden pozwala na dalszą propagację sygnału R, drugi nie.
Kiedy sygnały A i B się przecinają, ustanawiają nowy generator, lub P sygnał.

Z faktu drugiego wynika, że co druga maszyna w stanie A generuje nowy sygnał R, który zostaje wysłany w przeciwnym kierunku. Mamy 3 jednostki czasu odstępu pomiędzy dwoma sygnałami R przechodzącymi przez każdą maszynę.

Każda maszyna przechodząc do stanu B, pozostanie w tym stanie przez 3 jednostki czasu, zanim otrzyma sygnał R. W tym momencie stan B przejdzie do kolejnej maszyny (w kierunku przeciwnym do sygnału R).

Przykład (11 żołnierzy)

	1	2	3	4	5	6	7	8	9	10	11
0	P0	Q	Q	Q	Q	Q	Q	Q	Q	Q	Q
1	P0	A010	Q	Q	Q	Q	Q	Q	Q	Q	Q
2	P0	B0	A011	Q	Q	Q	Q	Q	Q	Q	Q
3	P0	B0	Q	A010	Q	Q	Q	Q	Q	Q	Q
4	P0	B0	R0	Q	A011	Q	Q	Q	Q	Q	Q
5	P0	B0	B1	Q	Q	A010	Q	Q	Q	Q	Q
6	P0	B0	B1	Q	R0	Q	A011	Q	Q	Q	Q
7	P0	B0	B1	R0	Q	Q	Q	A010	Q	Q	Q
8	P0	B0	Q	B0	Q	Q	R0	Q	A011	Q	Q
9	P0	B0	Q	B0	Q	R0	Q	Q	Q	A010	Q
10	P0	B0	Q	B0	R0	Q	Q	Q	R0	Q	P0
11	P0	B0	Q	B0	B1	Q	Q	R0	Q	A000	P0
12	P0	B0	R0	Q	B1	Q	R0	Q	A001	B0	P0
13	P0	B0	B1	Q	B1	R0	Q	A000	Q	B0	P0
14	P0	B0	B1	Q	Q	B0	A001	Q	R1	B0	P0
15	P0	B0	B1	Q	Q	P1	Q	Q	B1	B1	P0
16	P0	B0	B1	Q	A100	P1	A110	Q	B1	B0	P0
17	P0	B0	B1	A101	R1	P1	R0	A111	B1	B0	P0
18	P0	B0	P0	P0	B0	P1	B0	P0	P0	B0	P0
19	P0	P0	P0	P0	P0	P1	P0	P0	P0	P0	P0
20	T	T	T	T	T	T	T	T	T	T	T

Funkcja przejścia

$\delta :\langle Stan,Stan,Stan\rangle \to Stan$

Kolumna najbardziej po lewej stronie oznacza stan lewego sąsiada. Pierwszy wiersz oznacza stan prawego sąsiada.

Stan Q

	A000	A001	A100	A101	A010	A011	A110	A111
Q	A001	A000	A101	A100	R0	Q	Q	Q
B	A001	A000	A101	A100	R0	Q	Q	Q
R0	A001	A000	A101	A100	Q	Q	Q	Q
R1	A001	A000	A101	A100
P0						B0
P1							B0
φ	P0	P1	P0	P1

	Q	B	R0	R1	P0	P1	φ
A000	R1	R1
A001	Q	Q		Q	B0
A100	Q	Q
A101	Q	Q
A010	A011	A011					P0
A011	A010	A010					P1
A110	A111	A111					P0
A111	A110	A110					P1
Q	Q	Q	R0	Q	A000	A100	Q
γ					A000

	Q	B	R0	R1	P0	P1	φ	γ
B	Q	Q	R0	Q	Q	Q
R0	Q	Q			A000			Q
R1	R1	R1			R1	R1
P0	A010	Q	R0	Q	P0	P0
P1	A110	Q	R0	Q	P0	P0
φ	Q

Stan B0

	γ	P	A000	A100	A001	A101	R0
γ	B0	B0	P0	P1	P1	P0	R0
P	B0	P0					R0
A010	P0
A110	P1
A011	P1
A111	P0
R1	R1

Stan B1

	γ	P	A000	A100	A001	A101	R0
γ	B1		P0	P1	P1	P0	Q
P		P0
A010	P0
A110	P1
A011	P1
A111	P0
R1	Q

Stan R0

	γ
γ	Q
B0	B1
B1	B0
P	B0

Stan R1

	nie B, P	B0	B1	P
γ	Q	B1	B0	B0

Stan P0

	nie P, φ	P	φ
nie P, φ	P0	P0	P0
P	P0	T	T
φ	P0	T

Stan P1

	nie P, φ	P	φ
nie P, φ	P1	P1	P1
P	P1	T	T
φ	P1	T

Stan A000

	nie P0	P0
γ	Q	B0

Stan A001

	γ
γ	Q

Stan A100

	γ
nie B	R1
B	P1

Stan A101

	γ
nie B	Q
B	P0

Stan A010

	γ
nie P0	Q
P0	B0

Stan A011

	γ
γ	Q

Stan A110

	nie B	B
γ	R0	P1

Stan A111

	nie B	B
γ	Q	P0

Inne rezultaty

Autorzy	Czas [n – liczba żołnierzy]	Liczba stanów
John McCarthy, Marvin Minsky	$3n$	$13$
Eiichi Goto (1962)^[2]	$2n-2$
Abraham Waksman (1966)	$2n-2$	$16$
Robert Balzer (1967)^[3]	$2n-2$	$8$
Jacques Mazoyer (1987)^[4]	$2n-2$	$6$

Robert Balzer i Peter Sanders udowodnili, że nie istnieje rozwiązanie optymalne korzystające tylko z czterech stanów. Nie wiadomo, czy problem można rozwiązać używając pięciu stanów.

Uwagi

↑ W klasyfikacji struktur wojskowych pluton jest pododdziałem, nie oddziałem, jednak w tym artykule takie rozróżnienie nie jest potrzebne.

Przypisy

↑ Abraham Waksman: An optimum solution to the firing squad synchronization problem. 1966.
↑ Eiichi Goto: A Minimum Time Solution of the Firing Squad Problem. 1962.
↑ Robert Balzer: An 8-state minimal time solution to the firing squad synchronization problem. 1967.
↑ Jacques Mazoyer: A six-state minimal time solution to the firing squad synchronization problem. 1987.

Bibliografia

Amal Dar Aziz, Joe Cackler, Raylene Yung: The Firing Squad Problem. 2004.

[1] W klasyfikacji struktur wojskowych pluton jest pododdziałem, nie oddziałem, jednak w tym artykule takie rozróżnienie nie jest potrzebne.

[2] Abraham Waksman: An optimum solution to the firing squad synchronization problem. 1966.

[3] Eiichi Goto: A Minimum Time Solution of the Firing Squad Problem. 1962.

[4] Robert Balzer: An 8-state minimal time solution to the firing squad synchronization problem. 1967.

[5] Jacques Mazoyer: A six-state minimal time solution to the firing squad synchronization problem. 1987.

[a]

[1]

[2]

[3]

[4]