چگونه الگوریتم مارزولو شبکه‌های توزیع‌شده را وادار به توافق بر سر زمان می‌کند

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

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

برای تحمیل این توافق، اینترنت به پروتکل زمان شبکه (NTP) متکی است؛ معماری‌ای که توسط دیوید میلز در دانشگاه دلاویر در سال ۱۹۸۵ طراحی شد. همان‌طور که میلز در خلاصه اجرایی خود درباره همگام‌سازی زمان شبکه‌های کامپیوتری بیان می‌کند، این پروتکل به گونه‌ای طراحی شده است که زمان‌سنجی را در یک «ماتریس مسیریابی سلسله‌مراتبی» سازماندهی کند که زمان دقیق را از ساعت‌های اتمی به پایین و تا دستگاه‌های مصرف‌کننده توزیع می‌کند.[2]

این سلسله‌مراتب به سطوح استراتوم (Stratum) تقسیم می‌شود. استراتوم ۰ شامل سخت‌افزارهای زمان‌سنجی با دقت بالا، مانند ساعت‌های اتمی یا گیرنده‌های GPS است که مستقیما به شبکه عمومی متصل نمی‌شوند. سرورهای استراتوم ۱ از طریق کابل‌های اختصاصی مستقیما به این دستگاه‌های استراتوم ۰ متصل شده و به عنوان استانداردهای اصلی زمان شبکه عمل می‌کنند. سرورهای استراتوم ۲ زمان را از استراتوم ۱ دریافت می‌کنند و این روند به همین ترتیب تا لپ‌تاپ‌ها و گوشی‌های هوشمند در لبه شبکه ادامه می‌یابد.[5]

در حالی که فروشندگان سازمانی محیط‌های ابری «بدون تاخیر» را بازاریابی می‌کنند، واقعیت فیزیکی فیبر نوری دیکته می‌کند که انتقال داده زمان می‌برد. وقتی یک کلاینت زمان را از یک سرور استراتوم ۱ درخواست می‌کند، بسته داده باید از روترها، سوییچ‌ها و کابل‌ها عبور کند. تا زمانی که پاسخ سرور برسد، مهر زمانی (timestamp) موجود در آن دیگر به گذشته پیوسته است.[4]

همان‌طور که کوین سوکوچف، مهندس نرم‌افزار، در بررسی فنی خود از این پروتکل اشاره می‌کند، NTP این مشکل را با محاسبه تاخیر رفت و برگشت حل می‌کند. کلاینت دقیقا زمان ارسال درخواست و زمان دریافت پاسخ را ثبت می‌کند. با فرض اینکه تاخیر شبکه تقریبا متقارن است — یعنی زمان رفت با زمان برگشت برابر بوده — کلاینت می‌تواند مهر زمانی سرور را به اندازه نیمی از زمان رفت و برگشت جبران کند. سوکوچف خاطرنشان می‌کند که از طریق این مکانیزم، «NTP دقت‌هایی در حد ده‌ها میلی‌ثانیه را در بستر اینترنت عمومی فراهم می‌کند.»[4]

با این حال، فرض تقارن تاخیر اغلب اشتباه است. مسیریابی اینترنت به شدت نامتقارن است؛ یک بسته ممکن است از طریق یک کابل ترانس‌آتلانتیک از نیویورک به لندن برود و از یک مسیر کاملا متفاوت برگردد. این تاخیر متغیر که به عنوان لرزش شبکه (jitter) شناخته می‌شود، به این معنی است که یک کلاینت نمی‌تواند به یک منبع زمان واحد، حتی یک سرور استراتوم ۱، اعتماد کند، زیرا خود مسیر شبکه اندازه‌گیری را مخدوش می‌کند.[4][6]

اینجاست که هسته ریاضی سیستم، یعنی الگوریتم مارزولو، ضروری می‌شود. این الگوریتم که توسط کیت مارزولو در گزارش فنی سال ۱۹۸۳ دانشگاه استنفورد با عنوان «حفظ زمان در یک سیستم توزیع‌شده» توسعه یافت، ایده یافتن یک زمان واحد و صحیح را کنار می‌گذارد. در عوض، فرض می‌کند که هر منبع زمانی کمی اشتباه است و یک بازه محدود را محاسبه می‌کند که زمان واقعی باید در آن وجود داشته باشد.[1]

اگر یک کلاینت از سه سرور زمان مختلف پرس‌وجو کند، سه مهر زمانی متفاوت دریافت می‌کند که هر کدام عدم قطعیت محاسبه‌شده خود را بر اساس تاخیر شبکه دارند. سرور الف ممکن است ادعا کند زمان ۱۲:۰۰:۰۰ با خطای مثبت و منفی ۱۰ میلی‌ثانیه است. سرور ب ادعا می‌کند ۱۲:۰۰:۰۱ با خطای مثبت و منفی ۲۰ میلی‌ثانیه است. سرور ج ادعا می‌کند ۱۱:۵۹:۵۹ با خطای مثبت و منفی ۵ میلی‌ثانیه است.[1]

الگوریتم مارزولو این بازه‌ها را روی یک خط زمانی رسم کرده و به دنبال بزرگترین تقاطع هم‌پوشان می‌گردد. این الگوریتم به طور سیستماتیک داده‌های پرت — که در اصطلاحات NTP به آن‌ها «دروغ‌گو» (falsetickers) می‌گویند — را کنار می‌گذارد و «راست‌گوها» (truechimers) را جدا می‌کند. از نظر ریاضی تضمین می‌شود که زمان واقعی در همان پنجره باریکی قرار دارد که بازه‌های قابل اعتماد با هم هم‌پوشانی دارند، و این به کلاینت اجازه می‌دهد تا یک اجماع با احتمال بالا ایجاد کند.[1][2]

همان‌طور که شرکت ادکس اینترنشنال در تحلیل خود از اصلاح انحراف ساعت به تفصیل بیان می‌کند، این منطق اشتراک‌گیری به NTP اجازه می‌دهد تا فرکانس ساعت محلی را به صورت پویا تنظیم کند. این پروتکل به جای اینکه ساعت را به طور ناگهانی به جلو یا عقب بپرد — کاری که باعث از کار افتادن برنامه‌های در حال اجرا یا رد شدن وظایف زمان‌بندی‌شده می‌شود — نوسان‌ساز کوارتز محلی را کمی تندتر یا کندتر می‌کند تا به نرمی با زمان توافق‌شده همگام شود.[5]

مقیاس این همگام‌سازی به سرعت در حال گسترش است و محدودیت‌های فیزیکی جدیدی را به همراه دارد. مقاله‌ای در سال ۲۰۱۸ که در arXiv با عنوان «سیستمی برای همگام‌سازی ساعت در اینترنت اشیا» منتشر شد، فشار وارد بر معماری‌های سنتی NTP را به دلیل انفجار دستگاه‌های کم‌مصرف محاسبات لبه‌ای (edge-computing) برجسته می‌کند. این سنسورهای IoT اغلب فاقد ظرفیت باتری یا پایداری شبکه برای حفظ ارتباط مداوم با سرورهای استراتوم هستند و به توپولوژی‌های همگام‌سازی اصلاح‌شده‌ای نیاز دارند که با بودجه انرژی محدودتر کار کنند.[3]

تقاضا برای همگام‌سازی زمان روز به روز در حال افزایش است. در حالی که NTP استاندارد دقت کافی را برای وب‌گردی فراهم می‌کند، پلتفرم‌های مدرن معاملات مالی و شبکه‌های سلولی 5G به دقت میکروثانیه‌ای نیاز دارند که این امر باعث پذیرش پروتکل زمان دقیق (PTP) مبتنی بر سخت‌افزار شده است. با این حال، حتی با تکامل پروتکل‌ها برای دور زدن تاخیرهای سیستم‌عامل، منطق بنیادین اشتراک‌گیری که در سال ۱۹۸۳ در استنفورد تعریف شد، همچنان مکانیزم پایه‌ای است که یک شبکه پرآشوب را وادار به توافق بر سر زمان حال می‌کند.[6]