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.
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.
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).
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.
