‎$n$‎ سرباز در یک صف ایستاده‌اند تا یک زندانی بی‌چاره را تیرباران کنند. در زمانی نامشخص، دستور آغاز فرآیند اعدام به سربازی که در ابتدای صف ایستاده است، می‌رسد. هدف مسئله این است که سربازها طوری با هم هماهنگ شوند که پس از اعلام دستور اعدام به نفر اوّل، همه در یک زمان شلیک کنند ولی متأسفانه هر سرباز تنها می‌تواند با سرباز سمت چپ و سرباز سمت راست خودش در صف (در صورت وجود) ارتباط برقرار کند. مشکل دیگری که این سربازها دارند این است که خیلی باهوش نیستند و‎‎ حافظه‌ای متناهی(‎مستقل از مقدار ‎($n$‎ دارند. به عبارت دیگر، این سربازها عیناً شبیه ‎$DFA$‎ها هستند؛ چون تنها تعداد متناهی‌ای حالتِ داخلی‎($state$)‎ دارند که مستقل از ‎$n$‎ است.

توجّه کنید که حافظه‌ی متناهی خیلی کم است ولی ‎$n$‎ می‌تواند خیلی زیاد باشد. لزومی ندارد گفته شود ولی باید بدانید که سربازان نمی‌توانند حتی عدد ‎$n$‎ را در حافظه‌ی خود جای دهند‎)‎چون نگه‌داشتن آن عدد در حافظه، ‎$\log n$‎ بیت فضا می‌خواهد.)، چه برسد به این که بخواهند نام‌هایی یکتا برای خود داشته باشند.

کمکی که در زمینه‌ی هم‌گام‌سازی سربازان به ما می‌شود، صدای زنگ یک ساعت بزرگ است که از زمان ‎$-\infty$‎، در ابتدای هر ‎«دقیقه»‎ نواخته می‌شود و همه آن را می‌شنوند. در مدت یک ‎«دقیقه»، تنها فرآیندهایی قابل انجام هستند که انجام‌شان ‎$O(1)$‎ زمان می‌برد، ولی بالطّبع ‎$O(n)$‎ فرآیندِ مستقل می‌توانند به طور موازی توسط سربازان مختلف انجام شوند.

الگوریتمی ارائه دهید که اگر سربازها طبق آن رفتار کنند، همگی هم‌زمان شلیک خواهند کرد. اگر در الگوریتم شما زمان شلیک، ‎$O(n)$ «دقیقه»‎ پس از رسیدن دستور اعدام به سرباز اوّل صف باشد، نمره‌ی کامل را خواهید گرفت. در صورت بیش‌تر بودنِ مرتبه‌ی زمانی الگوریتم، متناسب با آن، قسمتی از نمره را خواهید گرفت. دقت کنید که الگوریتم باید طوری باشد که سربازان مدّت نامعلومی منتظر باشند (و فقط زنگ ساعت را بشنوند) تا این که به طور ناگهانی دستور اعدام به سرباز اوّل صف می‌رسد.

راهنمایی: سعی کنید برای ‎$n$‎های فرد، کاری کنید که نفر وسط بفهمد که نفر وسط است.

• سوال قبل