Problem z synchronizacją plutonu egzekucyjnego

Jedno rozwiązanie FSSP wykorzystujące 15 stanów i 3n jednostek czasu. Czas rośnie od góry do dołu.

Rozwiązanie wykorzystujące 2n-2 jednostki czasu. Czas rośnie od dołu do góry.

Problem synchronizacji plutonu egzekucyjnego to problem w informatyce i automatach komórkowych , w którym celem jest zaprojektowanie automatu komórkowego , który zaczynając od pojedynczej aktywnej komórki, ostatecznie osiąga stan, w którym wszystkie komórki są jednocześnie aktywne. Po raz pierwszy została zaproponowana przez Johna Myhilla w 1957 roku i opublikowana (z rozwiązaniem autorstwa Johna McCarthy'ego i Marvina Minsky'ego ) w 1962 roku przez Edwarda F. Moore'a .

Oświadczenie o problemie

Nazwa problemu wywodzi się z analogii do rzeczywistych plutonów egzekucyjnych : celem jest zaprojektowanie systemu zasad, zgodnie z którymi oficer może nakazać oddziałowi egzekucyjnemu strzelanie, tak aby jego członkowie jednocześnie strzelali ze swoich karabinów.

Bardziej formalnie problem dotyczy automatów komórkowych , tablic maszyn skończonych zwanych „komórkami” ułożonych w linii, tak że w każdym kroku czasowym każda maszyna przechodzi do nowego stanu w funkcji jej poprzedniego stanu i stanów jej dwóch sąsiadów w linii. W przypadku problemu plutonu egzekucyjnego linia składa się ze skończonej liczby komórek, a reguła, zgodnie z którą każda maszyna przechodzi do następnego stanu, powinna być taka sama dla wszystkich komórek znajdujących się wewnątrz linii, ale funkcje przejścia dwóch punkty końcowe linii mogą się różnić, ponieważ w każdej z tych dwóch komórek brakuje sąsiada po jednej ze swoich dwóch stron.

Stany każdej komórki obejmują trzy różne stany: „aktywny”, „spoczynkowy” i „odpalany”, a funkcja przejścia musi być taka, że komórka, która jest w stanie spoczynku i której sąsiedzi są w stanie spoczynku, pozostaje w stanie spoczynku. Początkowo, w chwili $t = 0$ , wszystkie stany są w stanie spoczynku, z wyjątkiem komórki znajdującej się najdalej po lewej stronie (ogólnej), która jest aktywna. Celem jest zaprojektowanie takiego zestawu stanów i funkcji przejścia, że niezależnie od tego, jak długa jest linia komórek, istnieje taki czas $t$ , że każda komórka przechodzi w stan odpalenia w czasie $t$ i taki, że żadna komórka nie należy do do stanu zapłonu przed czasem $t$ .

Rozwiązania

Pierwsze rozwiązanie FSSP zostało znalezione przez Johna McCarthy'ego i Marvina Minsky'ego i zostało opublikowane w Sequential Machines autorstwa Moore'a . Ich rozwiązanie polega na rozprowadzeniu wzdłuż linii żołnierzy dwóch fal: szybkiej i wolnej, poruszającej się trzy razy wolniej. Szybka fala odbija się od drugiego końca linii i spotyka wolną falę w środku. Dwie fale następnie podzieliły się na cztery fale, szybką i wolną falę poruszającą się w dowolnym kierunku od środka, skutecznie dzieląc linię na dwie równe części. Proces ten jest kontynuowany, dzieląc linię, aż każda dywizja będzie miała długość 1. W tym momencie każdy żołnierz strzela. To rozwiązanie wymaga 3 n jednostek czasu dla n żołnierzy.

Rozwiązanie wykorzystujące minimalną ilość czasu (czyli $2 n - 2$ jednostki czasu dla $n$ żołnierzy) zostało po raz pierwszy znalezione przez Eiichi Goto ( 1962 ), ale jego rozwiązanie wykorzystywało tysiące stanów. Waksman (1966) poprawił to do 16 stanów, a Balzer (1967) dalej poprawił to do ośmiu stanów, twierdząc jednocześnie, że udowodnił, że nie istnieje rozwiązanie czterostanowe. Peter Sanders stwierdził później, że procedura wyszukiwania Balzera była niekompletna, ale udało mu się potwierdzić wynik nieistnienia czterech stanów za pomocą poprawionej procedury wyszukiwania. Najbardziej znane obecnie rozwiązanie wykorzystujące sześć stanów wprowadził Jacques Mazoyer ( 1987 ). Nadal nie wiadomo, czy istnieje rozwiązanie pięciopaństwowe.

W rozwiązaniach z minimalnym czasem generał wysyła w prawo sygnały $S 1, S 2, S 3, ..., S i$ z prędkościami $1, 1/3, 1/7, ..., 1/(2 i -1 - 1)$ . Sygnał $S1 n$ odbija się na prawym końcu linii i spotyka się z sygnałem $Si .$ (dla $i \geq 2$ ) w komórce $/ 2i - 1$ Kiedy $S 1$ odbija, tworzy również nowego generała na prawym końcu. Sygnały $Si są konstruowane z wykorzystaniem sygnałów pomocniczych, które rozchodzą się$ w lewo. Co drugi sygnał przesuwa się (w prawo), wysyła sygnał pomocniczy w lewo. $S 1$ porusza się samodzielnie z prędkością 1, podczas gdy każdy z wolniejszych sygnałów porusza się tylko wtedy, gdy otrzyma sygnał pomocniczy.

Uogólnienia

Problem synchronizacji plutonu egzekucyjnego został uogólniony na wiele innych typów automatów komórkowych, w tym wielowymiarowe tablice komórek ( Shinahr 1974 ). Rozważono również warianty problemu z różnymi warunkami początkowymi ( Kobayashi & Goldstein 2005 ).

Rozwiązania problemu plutonu egzekucyjnego można również dostosować do innych problemów. Na przykład Patrick Fischer ( 1965 ) zaprojektował algorytm automatu komórkowego do generowania liczb pierwszych w oparciu o wcześniejsze rozwiązanie problemu synchronizacji plutonu egzekucyjnego.

Balzer, Robert (1967), „An 8-state minimalny czas rozwiązanie problemu synchronizacji plutonu egzekucyjnego”, Information and Control , 10 (1): 22–42, doi : 10.1016 / S0019-9958 (67) 90032-0 .
Fischer, Patrick C. (1965), „Generowanie liczb pierwszych przez jednowymiarową tablicę iteracyjną w czasie rzeczywistym”, Journal of the ACM , 12 (3): 388–394, doi : 10,1145 / 321281,321290 .
Goto, Eiichi (1962), Rozwiązanie problemu plutonu egzekucyjnego w minimalnym czasie , Notatki z kursu Dittoed dla matematyki stosowanej 298, Cambridge, MA: Harvard University, s. 52–59 . Cytowane przez Waksmana (1966) .
Kobayashi, Kojiro; Goldstein, Darin (2005), „O sformułowaniach problemów synchronizacji plutonu egzekucyjnego” , obliczenia niekonwencjonalne (PDF) , notatki z wykładów z informatyki, tom. 3699, Springer-Verlag, s. 157–168, doi : 10.1007/11560319_15 .
Mazoyer, Jacques (1987), „A Six-state minimalny czas rozwiązanie problemu synchronizacji plutonu egzekucyjnego”, Theoretical Computer Science , 50 (2): 183–238, doi : 10.1016/0304-3975 (87) 90124-1 .
Moore, Francja; Langdon, GG (1968), „Uogólniony problem plutonu egzekucyjnego”, Information and Control , 12 (3): 212–220, doi : 10.1016 / S0019-9958 (68) 90309-4 .
Shinahr, Ilka (1974), „Dwu- i trójwymiarowy problem synchronizacji plutonu egzekucyjnego”, Information and Control , 24 (2): 163–180, doi : 10.1016 / S0019-9958 (74) 80055-0 .
Waksman, Abraham (1966), „Optymalne rozwiązanie problemu synchronizacji plutonu egzekucyjnego”, Information and Control , 9 (1): 66–78, doi : 10.1016 / S0019-9958 (66) 90110-0 .

Linki zewnętrzne