موضوع مقاله: پروتکل شایعه | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # پروتکل شایعه | مقدمه: پروتکل شایعه یک روش یا فرایند ارتباط رایانه‌ای نظیر به نظیر است که براساس روش گسترش اپیدمی‌ها بنا شده‌است. | ## بخش 1: پروتکل شایعه | برخی از سیستم‌های توزیع شده برای اطمینان از انتشار داده‌ها به همهٔ اعضای گروه، از شایعات نظیر به نظیر استفاده می‌کنند. برخی از شبکه‌های موقت رجیستر مرکزی ندارند و تنها راه انتشار داده‌های مشترک اعتماد به هر یک از اعضا برای انتقال آن به همسایگان خود است. اصطلاح پروتکل اپیدمی اپیدمی گاهی به عنوان مترادف پروتکل شایعات به کار می‌رود، زیرا شایعات اطلاعات را به روشی مشابه انتشار ویروس در یک جامعه بیولوژیکی، منتشر می‌کنند. ارتباطات شایعات مفهوم ارتباط شایعات را می‌توان به کمک انتشار شایعات توسط کارمندان ادارات نشان داد. هر کارمند به‌طور تصادفی با دیگری جفت می‌شود و آخرین شایعات را به اشتراک می‌گذارد؛ مثلاً در ابتدای روز، دیو شایعهٔ جدیدی را شروع می‌کند: او به باب می‌گوید که معتقد است چارلی سبیل خود را رنگ می‌کند. در جلسه بعدی، باب به آلیس می‌گوید و در همین زمان دیو این شایعه را به حوا هم می‌گوید. بعد از هر قرار ملاقات اطراف کولر آبی، تعداد افرادی که این شایعه را شنیده‌اند تقریباً دو برابر می‌شود (هرچند اگر دوبار با یک شخص شایعه پراکنی شود تعداد افراد دو برابر نمی‌شود؛ مثلاً شاید دیو بخواهد داستان را برای فرانک تعریف کند در حالی که فرانک قبلاً آن را از آلیس شنیده‌است). سیستم‌های رایانه‌ای معمولاً این نوع پروتکل‌ها را با نوعی «انتخاب جفت» تصادفی پیاده‌سازی می‌کنند: با یک فرکانس مشخص، هر دستگاه به‌طور تصادفی ماشین دیگری را انتخاب می‌کند و هر گونه شایعه را به اشتراک می‌گذارد. بسیاری از انواع و سبک‌ها احتمالاً صدها نوع پروتکل خاص شایعات مانند وجود دارد زیرا معمولاً هر سناریوی استفاده، متناسب با نیازهای خاص هر سازمان تنظیم می‌شود. به عنوان مثال، یک پروتکل شایعات ممکن است از برخی از این ایده‌ها استفاده کند: هسته اصلی پروتکل شامل تعاملات دوره‌ای، جفتی و بین فرایندی است. هنگام تعامل عوامل، وضعیت حداقل یک عامل تغییر می‌کند تا وضعیت عامل دیگر را منعکس کند. فراوانی تعاملات در مقایسه با تأخیرهای معمول پیام کم است به طوری که هزینه‌های پروتکل بسیار ناچیز است. ممکن است جفت‌ها از مجموعهٔ همهٔ گره‌ها یا از مجموعه‌ای کوچکتر همسایه‌ها انتخاب شوند. انواع پروتکل شایعات تشخیص دو سبک غالب پروتکل شایعات مفید است: پروتکل‌های انتشار (یا پروتکل‌های شایعه ساز). آن‌ها اساساً با دربرگرفتن شبکه توسط عوامل کار می‌کنند، اما به روشی که محدودترین بارهای بد را تولید کند. آن‌ها رویدادها را گزارش می‌دهند، اما شایعات به صورت دوره‌ای رخ می‌دهد و در واقع وقایع باعث ایجاد شایعات نمی‌شوند. پروتکل‌های انتشار دادهٔ پس زمینه مداوم در مورد اطلاعات مرتبط با گره‌های شرکت کننده غیبت می‌کنند. | ## بخش 2: پروتکل شایعه | معمولاً تأخیر انتشار نگران کننده نیست، شاید به این دلیل که اطلاعات مورد نظر به آرامی تغییر می‌کنند یا مجازات قابل توجهی برای انجام عملیات روی داده‌های کمی کهنه وجود ندارد. این‌ها با نمونه‌برداری اطلاعات در گره‌های شبکه و ترکیب مقادیر برای رسیدن به مقداری در سطح سیستم، یک توده (به انگلیسی: aggregate) در سطح شبکه را محاسبه می‌کنند. لازمهٔ اصلی این است که توده باید با تبادل اطلاعات دو به دو با اندازهٔ ثابت قابل محاسبه باشد. این‌ها معمولاً پس از انجام چندین دور تبادل اطلاعات لگاریتمی در اندازه سیستم خاتمه می‌یابند، که در آن زمان یک الگوی جریان اطلاعات همه به همه ایجاد شده‌است. به عنوان یک اثر فرعی تجمع، می‌توان انواع دیگر مشکلات را با استفاده از شایعات حل کرد. به عنوان مثال، پروتکل‌های شایعات وجود دارد که با استفاده از تبادل اطلاعات به سبک توده می‌تواند در زمان لگاریتمی گره‌های یک پوشش شایعه را دریک لیست مرتب شده بر اساس شناسهٔ گره (به انگلیسی: node-id) (یا برخی ویژگی‌های دیگر) مرتب کنند. به همین ترتیب، الگوریتم‌های شایعات وجود دارد که گره‌ها را درون یک درخت قرار می‌دهند و با شایعه گفتن در الگویی که تمایل به مطابقت با ساختار درخت دارد، جمع‌هایی مانند sum یا count را محاسبه می‌کنند. بسیاری از پروتکل‌ها که قبل از اولین استفاده از اصطلاح "شایعات " بودند هم از آن استفاده می‌کردند. به عنوان مثال، پروتکل‌های مسیریابی اینترنت اغلب از تبادل اطلاعات شایعات‌مانند استفاده می‌کنند. از یک بستر شایعات می‌توان برای پیاده‌سازی یک شبکهٔ مسیریاب استاندارد استفاده کرد: گره‌ها در مورد پیام‌های قدیمی نقطه به نقطه شایعه پراکنی می‌کنند و به‌طور مؤثر ازدحام را به لایهٔ شایعه هل می‌دهند. اجازهٔ پهنای باند، بدان معنی است که یک سیستم شایعه سازی می‌تواند به‌طور بالقوه از هر پروتکل کلاسیک پشتیبانی کند یا هر سرویس توزیع شدهٔ کلاسیک را پیاده‌سازی کند. پروتکل‌های شایعات معمولاً پروتکل‌هایی هستند که به‌طور منظم، دوره‌ای، نسبتاً تنبل، متقارن و غیرمتمرکز اجرا می‌شوند؛ بنابراین، در حالی که می‌توان یک پروتکل کامیت دو فازی (به انگلیسی: Two-phase commit protocol) را بر روی یک بستر شایعه اجرا کرد، انجام این کار با معنی تعریف مغایرت دارد. برای این منظور، یک پروتکل باید هر اطلاعات جدیدی را به همهٔ گره‌هایی که تحت تأثیر اطلاعات قرار می‌گیرند، در زمانی لگاریتمی در اندازهٔ سیستم منتشر کند. مثال‌ها فرض کنید می‌خواهیم شی‌ای را که با برخی از الگوهای جستجو بیشترین تطابق را داشته‌باشد در یک شبکه با اندازهٔ نامعلوم که در آن کامپیوترها به هم متصلند و هر ماشین در حال اجرای یک برنامهٔ عامل کوچک که یک پروتکل شایعات را پیاده‌سازی می‌کند؛ است، پیدا کنیم. برای شروع جستجو، یک کاربر از نمایندهٔ محلی می‌خواهد شروع به شایعه‌سازی در مورد رشتهٔ جستجو کند. (ما فرض می‌کنیم نمایندگان یا با لیست شناخته شده‌ای از همتایان (به انگلیسی: peers) شروع می‌کنند یا این اطلاعات را از نوعی انبار مشترک بازیابی می‌کنند) به صورت دوره ای، با هر سرعتی (بگذارید برای سادگی بگوییم ده بار در ثانیه)، هر یک از عوامل به‌طور تصادفی برخی از عوامل دیگر را انتخاب می‌کند و با آن‌ها شایعه می‌پراکند. در «دور» شایعات بعدی، A و B هم جفت‌های تصادفی بعدی را انتخاب می‌کنند، شاید C و D. | ## بخش 3: پروتکل شایعه | این پدیدهٔ دو برابر شدن دور به دور پروتکل را بسیار مقاوم می‌کند، حتی اگر برخی از پیام‌ها از بین بروند یا برخی از جفت‌های انتخاب شده تکراری باشند و در مورد رشتهٔ جستجو بدانند. با دریافت رشتهٔ جستجو برای اولین بار، هر نماینده دستگاه محلی خود را برای مطابقت اسناد بررسی می‌کند. همچنین نمایندگان در مورد بهترین تطابق تا به امروز غیبت می‌کنند؛ بنابراین، اگر A با B غیبت کند، پس از تعامل، A از بهترین تطابق‌های شناخته شده برای B اطلاع خواهد داشت و بالعکس. اگر ممکن است پیام‌ها بزرگ شوند (به عنوان مثال، اگر بسیاری از جستجوها همزمان فعال باشند)، باید محدودیت اندازه را تعیین کنید. به این ترتیب که در مدت زمان لگاریتمی در اندازهٔ شبکه (تعداد عوامل)، هر رشتهٔ جستجوی جدید به همهٔ عوامل رسیده‌است. با یک تأخیر اضافی با همان طول تقریبی، هر نماینده می‌آموزد که بهترین تطابق را از کجا می‌تواند پیدا کند. به عنوان مثال، در شبکهای با ۲۵۰۰۰ ماشین، می‌توانیم بهترین تطابق را پس از حدود ۳۰ دور شایعه پیدا کنیم؛ ۱۵ مورد برای گسترش رشته جستجو و ۱۵ مورد دیگر برای کشف بهترین تطبیق. تبادل شایعات می‌تواند هر بار در هر دهم ثانیه بدون تحمیل بار ناخواسته رخ دهد، از این رو این شکل از جستجوی شبکه می‌تواند در مدت زمان ۳ ثانیه یک مرکز دادهٔ بزرگ را جستجو کند. در این سناریو، جستجوها ممکن است بعد از مثلاً ۱۰ ثانیه به‌طور خودکار از شبکه خارج شوند. در آن زمان، آغازگر پاسخ را می‌داند و شایعات بیشتر در مورد آن جستجو معنایی ندارد. پروتکل‌های شایعات همچنین برای دستیابی و حفظ انسجام پایگاه دادهٔ توزیع شده یا با انواع دیگر داده‌ها در حالت‌های سازگار (منسجم)، شمارش تعداد گره‌ها در شبکه‌ای با اندازهٔ ناشناخته،انتشار قوی اخبار، سازماندهی گره‌ها بر اساس برخی سیاست‌های ساختاری، ساخت شبکه‌های overlay، محاسبهٔ توده، مرتب‌سازی گره‌ها در یک شبکه، انتخاب رهبران و غیره استفاده می‌شوند. الگوریتم‌های اپیدمیک از پروتکل‌های شایعات می‌توان برای انتشار اطلاعات به شیوه ای کاملاً مشابه روش انتشار عفونت ویروسی در یک جمعیت بیولوژیکی استفاده کرد. در واقع، ریاضیات اپیدمی‌ها اغلب برای مدل‌سازی ریاضیات ارتباط شایعات استفاده می‌شود. اصطلاح الگوریتم اپیدمی گاهی اوقات هنگام توصیف یک سیستم نرم‌افزاری که در آن از این نوع انتشار اطلاعات مبتنی بر شایعات استفاده می‌شود؛ به کار می‌رود. همچنین ملاحظه کنید پروتکل‌های شایعات تنها یک کلاس در میان بسیاری از کلاس‌های پروتکل‌های شبکه هستند. همچنین می‌توانید هم‌زمانی مجازی، ماشین‌های حالت توزیع‌شده، الگوریتم Paxos و تراکنش پایگاه داده را ببینید. هر کلاس شامل ده‌ها یا حتی صدها پروتکل است که در جزئیات و ویژگی‌های عملکرد آن‌ها تفاوت وجود دارد اما در سطح تضمین‌های ارائه‌شده به کاربران مشابه هستند. | ## جمع‌بندی | برخی از پروتکل‌های شایعه مکانیزم انتخاب همتای تصادفی را با یک طرح قطعی جایگزین می‌کنند.