مسئله فرماندهان بیزانسی

مسئله فرماندهان بیزانسی (Byzantine Generals Problem) شرایط فرضی را بحث می‌کند که در آن افراد باید بدون حضور یک نظارت‌گر مرکزی، در مورد یک اقدام به اجماع برسند. دشواری آنجا پیش می‌آید که بازیگران باید در شرایطی تصمیم‌گیری کنند که همراه با عدم قطعیت، اطلاعات نادرست و حتی فریب‌دهنده است. من در این مقاله ابتدا به حالت خاصی از آن، مسئله دو فرمانده (Two Generals Problem) می‌پردازم. سپس بحث را به مسئله اصلی و کاربردهای آن گسترش می‌دهم.

مسئله دو فرمانده

تصور کنید دو فرمانده که از یکدیگر دور هستند می‌خواهند از دو جهت به یک دشمن حمله کنند (شکل-۱). فرمانده اول رهبری کل حمله را به عهده دارد و فرمانده دوم از او پیروی خواهد کرد. نیروهای آنان به‌تنهایی برای شکست دشمن کافی نیست. پس آنان باید به‌طور هم‌زمان به دشمن حمله کنند تا موفق شوند.

برای این‌که فرماندهان با یکدیگر ارتباط برقرار و زمان حمله را هماهنگ کنند، فرمانده اول باید پیکی به فرمانده دوم بفرستد تا زمان حمله را به او اعلام کند. این پیک باید از منطقه دشمن عبور کند. به همین دلیل ممکن است که توسط نیروهای دشمن اسیر شود و پیام هیچ‌گاه به فرمانده دوم نرسد. درنتیجه فرمانده اول ممکن است حمله کند درحالی‌که فرمانده دوم نیروهای خود را گسیل نکرده است.

حتی اگر پیک به فرمانده دوم برسد، فرمانده اول از کجا مطمئن شود که فرمانده دوم پیام را دریافت کرده است. به همین دلیل فرمانده دوم باید پیکی را به‌سوی فرمانده اول بفرستد تا تائید کند که پیام را دریافت کرده است. اما فرمانده دوم از کجا مطمئن شود که پیامش به فرمانده اول رسیده است. دوباره فرمانده اول باید تائید دریافت پیام را بفرستد و این چرخه همین‌طور تا بی‌نهایت ادامه پیدا می‌کند. هر دو فرمانده همواره در این عدم قطعیت باقی می‌مانند که آیا پیک قبلی توانسته سالم به مقصد برسد یا خیر. در چنین شرایطی هیچ‌گاه دو طرف نمی‌توانند مطمئن شوند که روی زمان حمله تفاهم دارند. ازنظر ریاضی نیز ثابت شده این مسئله قابل‌حل نیست.

مسئله فرماندهان بیزانسی

مسئله فرماندهان بیزانسی شکل کلی‌تری از مسئله دو فرمانده است و پیچیدگی‌های بیشتری به مسئله اضافه می‌کند. مسئله به‌این‌ترتیب است که فرماندهان بیزانسی که از نظر مکانی از هم دور هستند، می‌خواهند به قلعه دشمن حمله کنند (امپراتوری بیزانس یا روم شرقی، بین سال‌های ۳۹۵ میلادی تا ۱۴۵۳ میلادی بر قسمتی از خاورمیانه، آفریقا و اروپا تسلط داشت). در این شرایط فرضی به‌جای دو فرمانده، چند فرمانده باید بر روی زمان حمله به دشمن به تفاهم برسند. هر یک از آنان نیروی کافی برای غلبه بر دشمن را ندارد و تنها حمله هم‌زمان به موفقیت ختم خواهد شد. عقب‌نشینی هم‌زمان نیز موجب حفظ همه ارتش خواهد شد، ولی اگر برخی تصمیم به حمله و برخی دیگر تصمیم به عقب‌نشینی بگیرند، ارتش دچار آشوب خواهد شد و از هم می‌پاشد.

فرمانده ارشد پیک‌هایی به سایر فرماندهان می‌فرستد تا تصمیم خود را به آن‌ها اعلام کند. ولی این پیک‌ها از منطقه دشمن عبور می‌کنند. ممکن است برخی از این پیک‌ها توسط دشمن کشته یا اسیر شوند و پیام به آن‌ها نرسد. ممکن است دشمن پیک‌های جعلی را با پیک‌های واقعی جابجا کند. بدتر آنکه تعداد اندکی از فرماندهان ممکن است خیانت کنند. به این معنی که برای مثال پیام بفرستند که با برنامه حمله در صبح زود موافق هستند ولی نیت اصلی‌شان این باشد که عقب‌نشینی کنند. کسی نمی‌داند کدام‌یک از آن‌ها ممکن است خیانت کند (فرمانده ارشد نیز خود ممکن است خیانت‌کار باشد). در این شرایط چطور فرماندهان وفادار می‌توانند مطمئن شوند که هم‌زمان به یک اقدام مشترک دست خواهند زد؟

خطاهای بیزانسی به خطاهای غیرقابل‌پیش‌بینی در سیستم‌ها گفته می‌شود که نه‌تنها خطا یا خرابی ممکن است باعث شود سیستم خروجی نداشته باشد بلکه می‌تواند موجب تولید خروجی گمراه‌کننده شود. خطای بیزانسی از بدترین نوع خطاها در یک سیستم محسوب می‌شود. وقتی یک قسمت از سیستم خراب می‌شود، از کار می‌افتد و ارتباطش را با بخش‌های دیگر از دست می‌دهد، شما بلافاصله متوجه نقصان در سیستم می‌شوید. ولی اگر یک بخش از سیستم که دچار نقصان است در ظاهر مانند یک بخش سالم عمل کند، با بخش‌های دیگر در ارتباط باشد و پیام‌های اشتباه به آنان ارسال کند، به‌راحتی نمی‌توان متوجه خطا در سیستم شد. مشابه وضعیتی که در مقاله دیگری بحث کردم؛ حالتی که ما نمی‌دانیم چه چیزهایی را نمی‌دانیم. در این حالت خطا ممکن است در طول سیستم گسترش یابد و عواقب فاجعه‌آمیزی بیافریند.

سیستم‌هایی که بتوانند در برابر خطاهای بیزانسی تاب‌آوری داشته باشند، خطاتاب بیزانسی (Byzantine Fault Tolerant) نامیده می‌شوند. مسئله فرماندهان بیزانسی ازنظر ریاضی حل قطعی ندارد ولی راه‌حل‌های تقریبی که برای آن ارائه شده می‌تواند سیستم را در مواجهه با این نوع خطاها با احتمال بالایی محافظت کند.

خطاتابی بیزانسی

در سال ۱۹۸۲، لزلی لمپورت (Leslie Lamport) و همکارانش در مقاله‌ای حل تقریبی برای این مسئله ارائه می‌دهند. راه‌حلی که آنان برای مسئله پیشنهاد می‌دهند استفاده از اجماع است. هدف مقاله این است الگوریتمی ارائه کند که همه فرماندهان وفادار بر روی یک اقدام مشترک اجماع کنند، صرف‌نظر از این‌که فرماندهان خائن چه می‌کنند.

برای توضیح الگوریتم خطاتابی بیزانسی حالتی را در نظر بگیرید که چهار فرمانده وجود دارد (شکل-۲). یکی از فرماندهان (فرمانده ۲) خیانت‌کار است. البته هیچ‌کس از این مسئله آگاهی ندارد. در گام اول فرمانده ارشد تصمیم خود را به دیگران اعلام می‌کند. فرض کنیم این تصمیم حمله باشد. به علت عدم قطعیت‌هایی که در مسئله وجود دارد هر فرمانده نمی‌تواند مطمئن باشد که پیامی که از فرمانده ارشد دریافت می‌کند، صحیح است. در این حالت الگوریتم پیشنهاد می‌دهد که همه فرماندهان پیامی را که از فرمانده ارشد دریافت می‌کنند به سایرین نیز انتقال دهند. برای مثال فرمانده ۱ فرمان حمله دریافت کرده، چون او فرمانده وفاداری است، عین همان پیام را به دیگران انتقال می‌دهد. فرمانده ۲ خائن است پس به‌جای پیام حمله، به دیگران اعلام می‌کند پیام عقب‌نشینی از فرمانده ارشد دریافت کرده است.

در گام بعد الگوریتم پیشنهاد می‌دهد که هر فرمانده وفادار بر اساس اکثریت پیام‌هایی که از دیگران دریافت کرده، تصمیم‌گیری کند. فرمانده ۱ دو پیام حمله و یک پیام عقب‌نشینی دریافت کرده، پس تصمیم او حمله است. مشابه همین وضعیت برای فرمانده ۳ وجود دارد. به‌این‌ترتیب برای چنین حالتی بین سه فرمانده وفادار اجماع برای اقدام مشترک به وجود می‌آید.

حال فرض کنید فرمانده ارشد، خیانت‌کار است. در این حالت اگر فرمانده ارشد برای همه یک پیام (عقب‌نشینی یا حمله) ارسال کند، آنگاه به‌راحتی اجماع تشکیل می‌شود. پس او باید به برخی پیام حمله و به برخی پیام عقب‌نشینی ارسال کند (شکل-۳). در این حالت مشاهده می‌کنید که بازهم بین فرماندهان وفادار اجماع تشکیل می‌شود.

لازم به ذکر است الگوریتم پیشنهاد می‌دهد برای حالتی که از فرمانده‌ای پیامی دریافت نمی‌شود (برای مثال فرمانده خائن تصمیم می‌گیرد پیامی را منتقل نکند)، یک مقدار اولیه (برای مثال عقب‌نشینی) که از قبل روی آن توافق شده، جایگزین پیام شود.

نشان داده شده تا زمانی که حداکثر یک‌سوم فرماندهان خائن باشند، از طریق این الگوریتم اجماع به وجود می‌آید. به همین دلیل در مثال بالا، اگر دو فرمانده خائن باشند، اجماع ممکن نیست. در حالتی که پیام‌ها قابل جعل کردن نباشد (برای مثال با استفاده از امضای معتبر)، محدودیت تعداد فرماندهان خائن از بین می‌رود.

کاربردها

سیستم‌هایی که در هواپیماها، زیردریایی‌ها و نیروگاه‌های هسته‌ای بکار می‌روند که در آن‌ها بسیاری از فعالیت‌ها تابع اطلاعاتی است که از تعداد زیادی حسگر گرفته می‌شود، باید دارای خطاتابی بیزانسی باشند.

برای مثال پردازنده‌ها در هواپیماهای مسافربری با قابلیت پرواز خودکار (Autopilot) به منابع مختلف داده‌ای برای تصمیم‌گیری رجوع می‌کنند. آن‌ها داده‌ها را از حسگرهای هواپیما که در بخش‌های مختلف نصب‌ شده می‌گیرند. همچنین داده‌هایی از خلبان و کمک‌خلبان به‌عنوان ورودی دریافت می‌کنند. رویکرد اصلی در طراحی، قرار دادن ظرفیت اضافی در سخت‌افزارهای کامپیوتری به‌منظور حداکثر کردن ایمنی است. استانداردهای طراحی (FAR/CS 25. 1309) در این خصوص این است که هر ترکیبی از خطا که منجر به نتایج فاجعه‌بار شود باید احتمال وقوع کمتر از ۱ در ۱۰ میلیارد به ازای هر ساعت پرواز داشته باشد.

به‌عنوان نمونه دیگر در طراحی، شکل-۴ ساختار کامپیوترهای هدایت‌کننده بوئینگ ۷۷۷ را نشان می‌دهد. در این ساختار از رویکرد سه-سه‌ای استفاده شده است. به این معنی که سه کانال محاسباتی جدا و متمایز (بخش راست، مرکزی و چپ) هرکدام به‌طور موازی یک فعالیت را انجام می‌دهند. هر یک از این بخش‌ها خود از سه کانال محاسباتی تشکیل شده است که به‌صورت موازی یک فعالیت را انجام می‌دهند. در هر یک از این سه کانال، از پردازنده‌هایی که توسط سه شرکت مختلف ساخته‌شده‌اند، بهره گرفته می‌شود. این مسئله کمک می‌کند تا اگر پردازنده‌ها با چالش یکسانی مواجه شدند، همگی باهم دچار یک خطای محاسباتی نشوند.

در خصوص ایمنی، کامپیوترهای هدایت‌گر هواپیمای بوئینگ ۷۷۷ با دو هدف اصلی طراحی شدند:

اول، هیچ خطایی در بخش‌های مختلف سیستم، صرف‌نظر از احتمال وقوع آن، منجر به خروجی خطا از سیستم نشود، بدون آنکه سیستم خطا را بفهمد. درواقع هدف از بین بردن فرماندهان خائن است.

دوم، هیچ خطایی در بخش‌های مختلف سیستم، صرف‌نظر از احتمال وقوع آن، منجر به نقص در عملکرد بیش از یک کانال از سه کانال محاسباتی نشود.

دو پیام اصلی در طراحی کامپیوترهای هدایت‌گر هواپیماهای مسافربری وجود دارد. پیام نخست، پردازنده‌ها تنها به یک منبع داده به‌عنوان ورودی متکی نیستند. آنان داده‌ها را از حسگرها مختلف، خلبان و کمک‌خلبان جمع‌آوری می‌کنند. به‌این‌ترتیب یک یا ترکیبی از خطاهای بیزانسی نمی‌تواند منجر به خروجی اشتباه از آنان شود. پیام دوم، تعداد زیادی ظرفیت اضافه (برای مثال استفاده از پردازنده‌های شرکت‌های مختلف به شکل موازی) برای سیستم در نظر گرفته شده است تا جلوی خطاهای احتمالی پنهان گرفته شود. به این معنی که اگر در حالتی نتوانستیم فرماندهان خائن را از بین ببریم، تعداد فرماندهان وفادار را در سیستم افزایش دهیم.

کاربرد دیگر این بحث به فن‌آوری‌های مبتنی بر زنجیره بلوک (Blockchain) که در آن‌ها نظارت‌گر مرکزی وجود ندارد، برمی‌گردد.  این سیستم‌ها باید در برابر خطای بیزانسی تاب‌آوری داشته باشند. برای مثال در مورد رمزارزهایی مانند بیت‌کوین (Bitcoin)، هیچ بانک مرکزی وجود ندارد که صحت اطلاعات را در آن تائید کند. اطلاعات موجود در شبکه بیت‌کوین باید توسط خود اعضای شبکه تائید شود. ضمن این‌که فرمانده ارشدی هم وجود ندارد و همه اعضای شبکه در یک سطح هستند. اگر تعدادی از اعضای شبکه قصد ضربه به آن را داشته باشند (مانند فرماندهان خائن) و یا برخی پیام‌های نادرست در شبکه مبادله شود، شبکه باید مکانیزمی داشته باشد که همچنان بتواند در مورد صحت اطلاعات مبادله‌شده توافق داشته باشد. در مقاله دیگری توضیح خواهم داد، چگونه در بیت‌کوین پروتکلی مبتنی بر اجماع مشابه آنچه در این مقاله بحث کردم، باعث می‌شود تا سیستم در برابر خطای بیزانسی تاب‌آوری داشته باشد.

پیام این بحث برای مدیران چیست؟

نکته جالبی که با مرور ادبیات این حوزه متوجه شدم این بود که به نظر می‌رسد تا به امروز بحث خطای بیزانسی به حوزه علوم کامپیوتر و مهندسی محدود مانده است. درحالی‌که فضای تصمیم‌گیری که مسئله ترسیم می‌کند احتمالاً برای بسیاری از مدیران ارشد و اجرایی شرکت‌ها آشنا به نظر برسد. گرچه این مسئله و الگوریتم‌های پیشنهادی برای مواجهه با چالش‌های شبکه‌های توزیع‌شده (Distributed Networks)، مطرح شده‌اند، از دیدگاه من نوع نگاه محققان این حوزه می‌تواند برای تصمیم‌گیری‌های مدیریتی الهام‌بخش باشد.

من در اینجا به برخی مواردی که به ذهنم می‌رسد، اشاره می‌کنم. امیدوارم خوانندگان بر اساس تجارب خود این بحث را تکمیل کنند.

مدیران ارشد به‌ویژه در تصمیم‌گیری‌های پیچیده و کلان باید بتوانند خطاهای بیزانسی را مدیریت کنند. گزارش‌های دپارتمان‌های مختلف سازمان، داده‌های مربوط به تحقیقات بازار، اخبار و اطلاعاتی که در مجلات و روزنامه‌ها منتشر می‌شود، اطلاعاتی که شرکت‌های رقیب از خود ارائه می‌دهند، نظرات مدیران میانی، مشاوران، خبرگان صنعت، مدیران سایر شرکت‌ها و مشتریان همگی ممکن است خود همراه با خطا باشند و یا در فهم آن‌ها خطا وجود داشته باشد که ممکن است تصمیم‌گیر را گمراه کنند.

تصمیم‌گیر باید آگاه باشد که تمامی منابع اطلاعاتی تا حدی غیرقابل اطمینان هستند و می‌توانند گمراه‌کننده باشند. البته همه منابع اطلاعاتی به یک‌میزان غیرقابل اطمینان نیستند. برای مثال نظرسنجی که به شکل آنلاین و بیشتر توسط مخاطبانی که به وب‌سایت شرکت سرزده‌اند پر شده، نمی‌تواند نمایانگر سلیقه و نظر همه مشتریان بالقوه شرکت باشد و اطلاعات به‌شدت سوگیری دارند. اگر فرآیند نمونه‌گیری با رویکرد علمی انجام شود، نتایج قابل‌اطمینان‌تر است ولی همچنان ممکن است در استنباط از نتایج نظرسنجی خطا وجود داشته باشد.

فرآیند تصمیم‌گیری، به‌ویژه در مواردی که همراه با پیامدهای مهمی برای سازمان است، نباید به یک خطا وابسته شود. اگر فرآیند به‌گونه‌ای باشد که قسمتی از آن یا کل فرآیند تنها به یک منبع اطلاعاتی متکی باشد، در صورت وجود خطا در آن منبع یا خطا در تفسیر اطلاعات آن، کل تصمیم تحت تأثیر قرار می‌گیرد.

در حالتی که تصمیم‌گیر با تصمیمات دشوار مواجه است و نمی‌تواند به یک تصمیم مشخص برسد، در مدت‌زمانی که با چالش مواجه است باید همواره فرضیات رقیب را در نظر بگیرد و سعی کند آن‌ها را آزمایش کند. در مقاله “با آزمایش کردن در کسب‌وکار، هوشمندانه ریسک کنید” در این مورد بحث کردم.

مدیران باید بدانند همه انسان‌ها در معرض خطاهای تصمیم‌گیری قرار دارند. همه ما در قضاوت‌های خود دارای ضعف و نقصان هستیم و ممکن است بدان آگاه نباشیم. این آگاه نبودن به ضعف‌های خود بسیار خطرناک است. مانند فرماندهان خائن که در ظاهر خطایشان بر سیستم مشخص نیست، خطاهای رفتاری ما نیز پنهان هستند. راه‌حلی که در الگوریتم خطاتابی بیزانسی پیشنهاد می‌شود استفاده از منابع اطلاعاتی مختلف و تکیه بر اجماع است. هر فرمانده تنها به یک پیام اکتفا نمی‌کند، سعی می‌کند اطلاعات متنوعی را به دست آورد و برآیند آن‌ها را ملاک قرار دهد. مدیر هوشمند تنها به قضاوت خود اکتفا نمی‌کند؛ با روش‌های مختلف حدسیات خود را محک می‌زند.

در مقاله “ریسک و ندانسته‌های ناشناخته” بیشتر به این پرداختم که چگونه می‌توان بر این ندانسته‌ها در تصمیم‌گیری غلبه کرد.

منابع:

Balakrishnan, N. (2015). “Dependability in Medicine and Neurology. In Using Engineering and Management Principles for Better Patient Care”, Springer International Publishing

Lamport, L., Shostak, R., & Pease, M. (1982). “The Byzantine Generals Problem”, ACM Transactions on Programming Languages and Systems (TOPLAS), 4(3), 382-401