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