پروتکل شایعه

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

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

ارتباطات شایعات

مفهوم ارتباط شایعات را می‌توان به کمک انتشار شایعات توسط کارمندان ادارات نشان داد. فرض کنید هر ساعت کارمندان اداره در اطراف کولر آبی جمع می‌شوند. هر کارمند به‌طور تصادفی با دیگری جفت می‌شود و آخرین شایعات را به اشتراک می‌گذارد؛ مثلاً در ابتدای روز، دیو شایعهٔ جدیدی را شروع می‌کند: او به باب می‌گوید که معتقد است چارلی سبیل خود را رنگ می‌کند. در جلسه بعدی، باب به آلیس می‌گوید و در همین زمان دیو این شایعه را به حوا هم می‌گوید. بعد از هر قرار ملاقات اطراف کولر آبی، تعداد افرادی که این شایعه را شنیده‌اند تقریباً دو برابر می‌شود (هرچند اگر دوبار با یک شخص شایعه پراکنی شود تعداد افراد دو برابر نمی‌شود؛ مثلاً شاید دیو بخواهد داستان را برای فرانک تعریف کند در حالی که فرانک قبلاً آن را از آلیس شنیده‌است). سیستم‌های رایانه‌ای معمولاً این نوع پروتکل‌ها را با نوعی «انتخاب جفت» تصادفی پیاده‌سازی می‌کنند: با یک فرکانس مشخص، هر دستگاه به‌طور تصادفی ماشین دیگری را انتخاب می‌کند و هر گونه شایعه را به اشتراک می‌گذارد.

بسیاری از انواع و سبک‌ها

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

به عنوان مثال، یک پروتکل شایعات ممکن است از برخی از این ایده‌ها استفاده کند:

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

انواع پروتکل شایعات

تشخیص دو سبک غالب پروتکل شایعات مفید است:

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

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

پروتکل‌هایی که توده را محاسبه می‌کنند. این‌ها با نمونه‌برداری اطلاعات در گره‌های شبکه و ترکیب مقادیر برای رسیدن به مقداری در سطح سیستم، یک توده (به انگلیسی: aggregate) در سطح شبکه را محاسبه می‌کنند. لازمهٔ اصلی این است که توده باید با تبادل اطلاعات دو به دو با اندازهٔ ثابت قابل محاسبه باشد. این‌ها معمولاً پس از انجام چندین دور تبادل اطلاعات لگاریتمی در اندازه سیستم خاتمه می‌یابند، که در آن زمان یک الگوی جریان اطلاعات همه به همه ایجاد شده‌است. به عنوان یک اثر فرعی تجمع، می‌توان انواع دیگر مشکلات را با استفاده از شایعات حل کرد. به عنوان مثال، پروتکل‌های شایعات وجود دارد که با استفاده از تبادل اطلاعات به سبک توده می‌تواند در زمان لگاریتمی گره‌های یک پوشش شایعه را دریک لیست مرتب شده بر اساس شناسهٔ گره (به انگلیسی: node-id) (یا برخی ویژگی‌های دیگر) مرتب کنند. به همین ترتیب، الگوریتم‌های شایعات وجود دارد که گره‌ها را درون یک درخت قرار می‌دهند و با شایعه گفتن در الگویی که تمایل به مطابقت با ساختار درخت دارد، جمع‌هایی مانند sum یا count را محاسبه می‌کنند.

بسیاری از پروتکل‌ها که قبل از اولین استفاده از اصطلاح "شایعات " بودند هم از آن استفاده می‌کردند. به عنوان مثال، پروتکل‌های مسیریابی اینترنت اغلب از تبادل اطلاعات شایعات‌مانند استفاده می‌کنند. از یک بستر شایعات می‌توان برای پیاده‌سازی یک شبکهٔ مسیریاب استاندارد استفاده کرد: گره‌ها در مورد پیام‌های قدیمی نقطه به نقطه شایعه پراکنی می‌کنند و به‌طور مؤثر ازدحام را به لایهٔ شایعه هل می‌دهند. اجازهٔ پهنای باند، بدان معنی است که یک سیستم شایعه سازی می‌تواند به‌طور بالقوه از هر پروتکل کلاسیک پشتیبانی کند یا هر سرویس توزیع شدهٔ کلاسیک را پیاده‌سازی کند. با این حال، چنین تعبیر گسترده‌ای به ندرت در نظر گرفته می‌شود. پروتکل‌های شایعات معمولاً پروتکل‌هایی هستند که به‌طور منظم، دوره‌ای، نسبتاً تنبل، متقارن و غیرمتمرکز اجرا می‌شوند؛ بنابراین، در حالی که می‌توان یک پروتکل کامیت دو فازی (به انگلیسی: Two-phase commit protocol) را بر روی یک بستر شایعه اجرا کرد، انجام این کار با معنی تعریف مغایرت دارد.

اصطلاح همگرایی ثابت (به انگلیسی: convergently consistent) گاهی برای توصیف پروتکل‌هایی استفاده می‌شود که به انتشار سریع نمایی اطلاعات دست یافته‌اند. برای این منظور، یک پروتکل باید هر اطلاعات جدیدی را به همهٔ گره‌هایی که تحت تأثیر اطلاعات قرار می‌گیرند، در زمانی لگاریتمی در اندازهٔ سیستم منتشر کند. ("زمان مخلوط کردن" باید در اندازه سیستم لگاریتمی باشد).

مثال‌ها

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

برای شروع جستجو، یک کاربر از نمایندهٔ محلی می‌خواهد شروع به شایعه‌سازی در مورد رشتهٔ جستجو کند. (ما فرض می‌کنیم نمایندگان یا با لیست شناخته شده‌ای از همتایان (به انگلیسی: peers) شروع می‌کنند یا این اطلاعات را از نوعی انبار مشترک بازیابی می‌کنند)
به صورت دوره ای، با هر سرعتی (بگذارید برای سادگی بگوییم ده بار در ثانیه)، هر یک از عوامل به‌طور تصادفی برخی از عوامل دیگر را انتخاب می‌کند و با آن‌ها شایعه می‌پراکند. رشته‌های جستجوی شناخته شده برای A اکنون برای B نیز شناخته خواهند شد و بالعکس. در «دور» شایعات بعدی، A و B هم جفت‌های تصادفی بعدی را انتخاب می‌کنند، شاید C و D. این پدیدهٔ دو برابر شدن دور به دور پروتکل را بسیار مقاوم می‌کند، حتی اگر برخی از پیام‌ها از بین بروند یا برخی از جفت‌های انتخاب شده تکراری باشند و در مورد رشتهٔ جستجو بدانند.
با دریافت رشتهٔ جستجو برای اولین بار، هر نماینده دستگاه محلی خود را برای مطابقت اسناد بررسی می‌کند.
همچنین نمایندگان در مورد بهترین تطابق تا به امروز غیبت می‌کنند؛ بنابراین، اگر A با B غیبت کند، پس از تعامل، A از بهترین تطابق‌های شناخته شده برای B اطلاع خواهد داشت و بالعکس. بهترین تطابق‌ها از طریق شبکه «گسترش» می‌یابند.

اگر ممکن است پیام‌ها بزرگ شوند (به عنوان مثال، اگر بسیاری از جستجوها همزمان فعال باشند)، باید محدودیت اندازه را تعیین کنید. همچنین، جستجوها باید از شبکه خارج شوند. به این ترتیب که در مدت زمان لگاریتمی در اندازهٔ شبکه (تعداد عوامل)، هر رشتهٔ جستجوی جدید به همهٔ عوامل رسیده‌است. با یک تأخیر اضافی با همان طول تقریبی، هر نماینده می‌آموزد که بهترین تطابق را از کجا می‌تواند پیدا کند. به‌طور خاص، نماینده‌ای که جستجو را شروع کرده بهترین نتیجه را پیدا کرده‌است. به عنوان مثال، در شبکهای با ۲۵۰۰۰ ماشین، می‌توانیم بهترین تطابق را پس از حدود ۳۰ دور شایعه پیدا کنیم؛ ۱۵ مورد برای گسترش رشته جستجو و ۱۵ مورد دیگر برای کشف بهترین تطبیق. تبادل شایعات می‌تواند هر بار در هر دهم ثانیه بدون تحمیل بار ناخواسته رخ دهد، از این رو این شکل از جستجوی شبکه می‌تواند در مدت زمان ۳ ثانیه یک مرکز دادهٔ بزرگ را جستجو کند. در این سناریو، جستجوها ممکن است بعد از مثلاً ۱۰ ثانیه به‌طور خودکار از شبکه خارج شوند. در آن زمان، آغازگر پاسخ را می‌داند و شایعات بیشتر در مورد آن جستجو معنایی ندارد. پروتکل‌های شایعات همچنین برای دستیابی و حفظ انسجام پایگاه دادهٔ توزیع شده یا با انواع دیگر داده‌ها در حالت‌های سازگار (منسجم)، شمارش تعداد گره‌ها در شبکه‌ای با اندازهٔ ناشناخته،انتشار قوی اخبار، سازماندهی گره‌ها بر اساس برخی سیاست‌های ساختاری، ساخت شبکه‌های overlay، محاسبهٔ توده، مرتب‌سازی گره‌ها در یک شبکه، انتخاب رهبران و غیره استفاده می‌شوند.

الگوریتم‌های اپیدمیک

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

همچنین ملاحظه کنید

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