Все солдаты должны стрелять одновременно

15

Когда я был студентом, я увидел проблему в учебнике по цифровым системам / логическому проектированию, когда N солдат стоят в ряду и хотят одновременно стрелять. Более сложной версией проблемы было то, что солдаты стоят в общей сети, а не в ряду. Я уверен, что это классическая проблема, но я не могу вспомнить ее название. Можешь напомнить мне?

Эрель Сегал-Халеви
источник

Ответы:

21

Эта проблема известна как проблема синхронизации отряда стрельбы . Сама проблема, строго связана с конечными автоматами, Здесь каждый солдат является конечным автоматом; Вы знаете, что следующее состояние каждого солдата зависит от его текущего состояния и текущих состояний двух его соседей (за исключением первого и последнего солдата). Первым солдатом в этой обстановке может быть генерал-солдат, отвечающий за начало атаки. Последний солдат знает, что это последний. Глобальное общение недоступно; однако глобальные часы могут использоваться для синхронизации переходов состояний солдат. Задача состоит в том, чтобы разработать солдатский автомат, цель которого состоит в том, чтобы все солдаты входили в состояние «СНИМКА» в один и тот же такт. Кстати, проблему можно решить за время для солдат.Θ(N)N

Массимо Кафаро
источник