Semua prajurit harus menembak pada saat bersamaan

Ketika saya masih mahasiswa, saya melihat masalah dalam buku digital sistem / desain logika, tentang tentara N berdiri berturut-turut, dan ingin menembak pada saat yang sama. Versi yang lebih sulit dari masalah ini adalah bahwa tentara berdiri di jaringan umum alih-alih berbaris. Saya yakin ini adalah masalah klasik, tetapi saya tidak dapat mengingat namanya. Bisakah Anda mengingatkan saya?

Masalahnya dikenal sebagai masalah sinkronisasi regu tembak . Masalahnya sendiri, sangat terkait dengan automata keadaan terbatas. Di sini, setiap prajurit adalah otomat terbatas; Anda tahu bahwa keadaan selanjutnya dari setiap prajurit tergantung pada keadaan saat ini dan keadaan saat ini dari kedua tetangganya (kecuali untuk prajurit pertama dan terakhir). Prajurit pertama dalam pengaturan ini dapat dianggap sebagai jenderal tentara yang bertugas memulai serangan. Prajurit terakhir tahu itu yang terakhir. Tidak ada komunikasi global yang tersedia; namun, jam global dapat digunakan untuk menyinkronkan transisi negara para prajurit. Masalahnya mengharuskan mendesain otomat prajurit yang tujuannya adalah agar semua prajurit memasuki keadaan "TEMBAK" pada detak jam yang sama persis. Ngomong-ngomong, masalahnya bisa diselesaikan dalam waktu untuk tentara.$\Theta(n)$$n$