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łW klasyfikacji struktur wojskowych pluton jest pododdziałem, nie oddziałem, jednak w tym artykule takie rozróżnienie nie jest potrzebne. 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, 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

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 Eiichi Goto (1962) Abraham Waksman (1966) Robert Balzer (1967) Jacques Mazoyer (1987)

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

Przypisy

Bibliografia

Kategoria:Automaty komórkowe