Alle Soldaten sollten gleichzeitig schießen

Als ich Student war, sah ich ein Problem in einem Lehrbuch für digitales System- / Logikdesign, in dem es um N Soldaten ging, die in einer Reihe standen und gleichzeitig schießen wollten. Eine schwierigere Version des Problems war, dass die Soldaten in einem allgemeinen Netzwerk statt in einer Reihe stehen. Ich bin mir sicher, dass dies ein klassisches Problem ist, aber ich kann mich nicht an den Namen erinnern. Kannst du mich erinnern?

Das Problem wird als Synchronisierungsproblem für die Einsatzgruppe bezeichnet . Das Problem selbst hängt eng mit Automaten mit endlichen Zuständen zusammen. Hier ist jeder Soldat ein endlicher Automat; Sie wissen, dass der nächste Status eines jeden Soldaten von seinem aktuellen Status und dem aktuellen Status seiner beiden Nachbarn abhängt (mit Ausnahme des ersten und des letzten Soldaten). Der erste Soldat in dieser Situation kann jedoch der General des Soldaten sein, der für den Beginn des Angriffs verantwortlich ist. Der letzte Soldat weiß, dass es der letzte ist. Es ist keine globale Kommunikation verfügbar. Eine globale Uhr kann jedoch verwendet werden, um die Zustandsübergänge der Soldaten zu synchronisieren. Das Problem besteht darin, einen Soldatenautomaten zu entwerfen, dessen Ziel es ist, dass alle Soldaten mit genau derselben Zeitmarke in den Zustand "SCHUSS" versetzt werden. Übrigens kann das Problem in Zeit für n Soldaten gelöst werden .$\Theta(n)$$n$