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

در یک محیط محاسباتی همگام — مانند یک پردازنده ۶۴ هسته‌ای که به ساعت ۴ گیگاهرتزی یک مادربرد متصل است — تشخیص خرابی کار ساده‌ای است: اگر یک قطعه مهلت زمانی دقیق ۲۵۰ پیکوثانیه‌ای را از دست بدهد، مرده تلقی می‌شود. اما شبکه‌های ناهمگامی که اینترنت مدرن را می‌چرخانند، دقیقاً در یک جنبه تفاوت دارند: هیچ ساعت جهانی و هیچ حداکثر تاخیر تضمین‌شده‌ای برای یک پیام وجود ندارد. همین یک محدودیتِ غایب، تله‌ای ریاضیاتی می‌سازد که بر تمام پایگاه‌های داده ابری امروزی حاکم است.[6]

این تله با نام «قضیه محال بودن اف‌ال‌پی» (FLP Impossibility Theorem) شناخته می‌شود که از نام پژوهشگران آن، مایکل فیشر، نانسی لینچ و مایکل پترسون گرفته شده است. آن‌ها در مقاله آوریل ۱۹۸۵ خود با عنوان «محال بودن اجماع توزیع‌شده با یک فرآیند معیوب» که در نشریه ACM منتشر شد، ثابت کردند که در یک شبکه کاملاً ناهمگام، هیچ الگوریتم قطعی نمی‌تواند تضمین کند که گروهی از کامپیوترها به اجماع می‌رسند، حتی اگر احتمال خرابی تنها ۱ ماشین از ۱۰۰۰ ماشین وجود داشته باشد.[1]

برای درک این مرز، ابتدا باید اصطلاحات را تعریف کنیم. «اجماع» ایجاب می‌کند که ۱۰۰ درصد از گره‌های سالم در یک شبکه بر سر یک مقدار باینری واحد — یعنی ۰ یا ۱ — توافق کنند و این تصمیم نهایی باشد. «قطعی» (Deterministic) به این معناست که الگوریتم بر تصادف تکیه نمی‌کند؛ با ورودی‌های یکسان، دقیقاً خروجی‌های یکسانی تولید می‌کند. «ناهمگام» (Asynchronous) نیز یعنی پیام‌ها ممکن است ۵ میلی‌ثانیه یا ۵ روز تاخیر داشته باشند، اما هرگز گم نمی‌شوند.[1][4]

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

فیشر، لینچ و پترسون این موضوع را با معرفی مفهوم وضعیت «دوظرفیتی» (bivalent) نشان دادند. یک سیستم زمانی دوظرفیتی است که مقدار نهاییِ توافق‌شده، بسته به ترتیبی که پیام‌های آینده تحویل داده می‌شوند، همچنان بتواند ۰ یا ۱ باشد. در مقابل، وضعیت «تک‌ظرفیتی» (univalent) وضعیتی است که در آن تصمیم نهایی قفل شده است، فارغ از اینکه در آینده چه اتفاقی بیفتد.[1][2]

اثبات ریاضی این قضیه بر یک سناریوی خصمانه به شدت ساده استوار است. این پژوهشگران نشان دادند که اگر یک سیستم در یک وضعیت دوظرفیتی کار خود را آغاز کند، یک تاخیر با زمان‌بندی دقیق در تحویل پیام می‌تواند همیشه سیستم را به یک وضعیت دوظرفیتی دیگر سوق دهد و شبکه را در یک حلقه بی‌نهایت از بلاتکلیفی گرفتار کند.[1][5]

تحلیل موسسه ماکس پلانک از این قضیه خاطرنشان می‌کند: «در یک سیستم ناهمگام، غیرممکن است تضمین کنیم که یک پروتکل اجماع روزی به پایان می‌رسد.» یک عامل مخرب که تاخیرهای شبکه را کنترل می‌کند، می‌تواند دنباله‌ای بی‌نهایت از وضعیت‌های دوظرفیتی را به هم پیوند دهد و مانع از آن شود که سیستم هرگز به یک نتیجه تک‌ظرفیتی برسد.[5]

این بدان معنا نیست که اجماع در دنیای واقعی عملاً غیرممکن است، بلکه نشان می‌دهد نمی‌توان از نظر ریاضی تضمین کرد که این فرآیند در یک زمان محدود به پایان برسد. سیستم ممکن است در همان تلاش اول به توافق برسد، یا ممکن است برای همیشه به تاخیر بیفتد.[3]

برای مهندسانی که زیرساخت‌های جهانی را می‌سازند، این مطلق‌گرایی نظری نیازمند سازش‌های عملی است. رایج‌ترین راهکار، کنار گذاشتن تعریف دقیق و سخت‌گیرانه یک سیستم ناهمگام از طریق معرفی مفهوم «همگامی نسبی» (partial synchrony) است.[4]

تحت شرایط همگامی نسبی، مهندسان فرض را بر این می‌گذارند که اگرچه شبکه ممکن است تاخیرهای غیرقابل پیش‌بینی را تجربه کند، اما در نهایت به ثبات می‌رسد و پیام‌ها را در یک بازه زمانی مشخص تحویل می‌دهد. این امر اجازه استفاده از وقفه‌های زمانی (تایم‌اوت) را می‌دهد. اگر یک گره در یک پنجره ۵۰ میلی‌ثانیه‌ای پاسخ ندهد، مرده فرض می‌شود و سیستم به مسیر خود ادامه می‌دهد.[4][6]

جزوات درسی دانشگاه ییل در این باره توضیح می‌دهند: «نتیجه اف‌ال‌پی نشان می‌دهد که ما نمی‌توانیم یک الگوریتم اجماع قطعی در یک مدل کاملاً ناهمگام داشته باشیم.» با افزودن وقفه‌های زمانی، سیستم‌هایی مانند پروتکل پکسوس (منتشر شده در ۱۹۹۸) و رفت (منتشر شده در ۲۰۱۴) شرایط سخت‌گیرانه این قضیه را دور می‌زنند.[4]

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

میراث مقاله سال ۱۹۸۵ این نیست که توسعه سیستم‌های توزیع‌شده را متوقف کرد، بلکه این است که مرزهای دقیقِ آنچه را که امکان‌پذیر است، ترسیم نمود. این قضیه، صنعت را وادار کرد تا بپذیرد که قطعیت مطلق در یک دنیای شبکه‌ای، تنها یک افسانه ریاضیاتی است.[2][6]

هر بار که یک پایگاه داده ابری برای انتخاب یک رهبر جدید مکث می‌کند، یا تایید یک تراکنش در سراسر یک شبکه جهانی ۲۰۰ میلی‌ثانیه بیشتر طول می‌کشد، سیستم در حال مسیریابی فعالانه در میان محدودیت‌هایی است که فیشر، لینچ و پترسون ترسیم کرده‌اند. این قضیه همچنان به عنوان بستر بنیادینی که تمام معماری‌های توزیع‌شده مدرن بر روی آن بنا شده‌اند باقی می‌ماند و ثابت می‌کند که در علوم کامپیوتر، دانستن اینکه چه کاری را نمی‌توان انجام داد، به همان اندازه ارزشمند است که بدانیم چه کاری امکان‌پذیر است.[6]