| عنوان فارسی مقاله: | نمونه گیری همتا برمبنای گوسیپ (Gossip) |
| عنوان انگلیسی مقاله: | Gossip-based Peer Sampling |
| دانلود مقاله انگلیسی: | برای دانلود رایگان مقاله انگلیسی با فرمت pdf اینجا کلیک نمائید |
| سال انتشار | 2011 |
| تعداد صفحات مقاله انگلیسی | 36 صفحه |
| تعداد صفحات ترجمه مقاله | 41 صفحه |
| مجله | تراکنش ها در سیستم های کامپیوتری |
| دانشگاه | – |
| کلمات کلیدی | – |
| نشریه IAAE | ACM |
فهرست مطالب:
چکیده
۱ مقدمه
۲ سرویس نمونه گیری همتا
۱ ۲ API
۲ ۲ توصیف پروتکل عمومی
۳ ۲ فضای طراحی
۱ ۳ ۲ انتخاب همتا
۲ ۳ ۲ انتشار ویوو
۴ ۲ اجرا
۱ ۴ ۲ فرمت بندی و مقدار دهی اولیه
۲ ۴ ۲ نمونه گیری
۳ تصادفی بودن محلی
۱ ۳ محیط های آزمایشی
۲ ۳ نتایج تست
۳ ۳ نتایج
۴ خصلت تصادفی کلی
۱ ۴ خصوصیات توزیع درجه
۱ ۱ ۴ همگرایی
۲ ۱ ۴ خصوصیات ایستا(استاتیکی)
۳ ۱ ۴ خصوصیات دینامیکی
۲ ۴ خوشه بندی و طول مسیر
۱ ۲ ۴ متوسط طول مسیر
۲ ۲ ۴ ضریب خوشه بندی
۵ تولرانس یا تحمل خرابی
۱ ۵ خرابی فجیع
۲ ۵ چرن
۳ ۵ شبیه سازیهای چرن بر مبنای رد یابی
۶ نمونه سازی شبکه گسترده
۷ بحث
۱ ۷ تصادفی بودن (خصلت تصادفی)
۱ ۱ ۷ تعادل بار
۲ ۱ ۷ تحمل خطا
۸ کار وابسته
۱ ۸ پروتکل های عضویت گوسیپ
۲ ۸ شبکه های پیچیده
۳ ۸ جایگذاشت های سازمان نیافته
۴ ۸ جایگذاشت های ساختار یافته
۹ ملاحظات پایانی
بخشی از ترجمه:
۱ مقدمه
پروتکل های برمبنای گوسیپ که همچنین پروتکل های اپیدمی نامیده می شوند، در برنامه های توزیع شده درمقیاس بزرگ کاربرد دارند. شهرت این پروتکل ها ریشه در توانایی آنها برای انتقال اطلاعات در میان مجموعه گره های متصل به هم دارد، حتی اگر گره ها به طور منظم به سیستم ملحق شده و آن را ترک کنند ( به صورت هدمند یا به خاطر خطا) و شبکه پایه از لینک های کند یا شکسته آسیب می بیند. در پروتکل برمبنای گوسیپ، هر گره در سیستم به طور متناوب اطلاعات را با زیرمجموعه ای از همتایانش مبادله می کند. انتخاب این زیرمجموعه نقش بسیار مهمی در توزیع وسیع گوسیپ دارد. در سطح ایده آل، هر گره باید اطلاعات را با همتایان انتخاب شده با پیروی از نمونه تصادفی یکنواخت کلیه گره های در حال حاضر موجود در سیستم مبادله کند. این فرضیه منجر به تعیین بسیاری از مشخصه های مطلوب پروتکل های بر مبنای گوسیپ مثل مقیاس پذیری، پایایی و کارایی و راندمان در مورد توزیع اطلاعات یا انباشتگی گردید. در عمل، اجرای این فرضیه نیاز به توسعه برنامه هایی دارد که هر گره از سایر گره های حاضر در سیستم اطلاع دارد. اما، فراهم نمودن جدول عضویت کامل برای هر گره، جدولی که نمونه تصادفی را از آن می توان انتخاب نمود، در سیستم دینامیکی در مقیاس بزرگ غیرممکن می باشد، زیرا حفظ و نگهداری چنین جداولی در حضور گره های ملحق شده و ترک کننده ( نامیده شده) موجب تحمیل هزینه های همگام سازی قابل ملاحظه ای می گردد. به ویژه، مطالعات اندازه گیری پیرامون شبکه های مختلف همتا با همتا نشان می دهد که یک گره اختصاصی (تکی) اغلب ظرف چند دقیقه تا یک ساعت وصل می شود. بدیهی است طرح های غیر متمرکز برای حفظ اطلاعات عضویت نقش مهمی در آرایش پروتکل های بر مبنای گوسیپ دارند. مقاله حاضر در مورد چکیده ای از سرویس نمونه گیری همتا صحبت کرده و چارچوب عمومی ، ساده و بر مبنای گوسیپی برای اجرای آن مطرح می کند. سرویس نمونه گیری همتا با استفاده از آن از برنامه جداشده و اجمالاً می توان گفت که از این سرویس در محیط های مختلف می توان استفاده نمود: توزیع اطلاعات، انباشتگی،تعادل بار و مدیریت شبکه. این سرویس به شکل تجرد درجه یک سیستم توزیع شده در مقیاس بزرگ ارتقاء یافته است. در اصل، نقش مهمی در سرویس نامگذاری در سیستم توزیع شده LAN سنتی ایفا می کند، چرا که شرایطی برای تعامل و برهم کنش گره ها فراهم می آورد. اصل عمومی پایه چارچوب پیشنهاد شده برای اجرای سرویس نمونه گیری همتا، بر اساس الگوی گوسیپ می باشد. به طور خلاصه، هرگره (۱) جدول عضویت محلی نسبتاً کوچکی در اختیار دارد که نگرشی جزئی پیرامون مجموعه کاملی از گره ها ارائه داده و (۲) به طور متناوب و با استفاده از روش گوسیپ جدول را تازه می کند. این چارچوب عمومی بوده و از آن می توان برای اجراهای عضویت بر مبنای گوسیپ جدید و شناخته شده استفاده نمود. در حقیقت، چارچوب معرفی شده با بسیاری از گونه های توزیع عضویت بر مبنای گوسیپ سرو کار دارد. این گونه ها عمدتاً در شیوه به روزدرآوری جدول عضویت در هر گره بعد از مبادله جداول در دور گوسیپ باهم تفاوت دارند.
9. ملاحظات پایانی
اخیراً پروتکل های گوسیپ علاقه زیادی در جامعه تحقیقاتی ایجاد کرده اند. جایگذاشت های نشات گرفته از این پروتکل ها نسبت به خرابی ها و نرخ چرن بالا عکس العمل نشان می دهند. الگوی پایه برنامه های توزیع شده در مقیاس بزرگ را می سازد.
سهم این مقاله فاکتور بندی چکیده اجرا شده توسط مکانیسم عضویت زیرمبنای پروتکل های گوسیپ موسوم به سرویس نمونه گیری همتا می باشد. این سرویس دانش محلی از بخشهای دیگر سیستم را در اختیار هر همتا قرارمی دهد که کلیدی برای همگرایی کل سیستم به سمت خصوصیات کلی با استفاده از اطلاعات محلی به تنهایی میباشد.
در اینجا چارچوب بکاررفته برای اجرای سرویس نمونه گیری همتای موثق و کارآمد توصیف گردید. این چارچوب خود بر اساس گوسیپ عمل می کند. این چارچوب به اندازه کافی عمومی می باشد که با بیشتر پروتکل های عضویت گوسیپ فعلی معرفی شود. در این مقاله از این چارچوب برای مقایسه تجربی رنج پروتکل ها از طریق شبیه سازیها بر اساس آثار واقعی و مصنوعی و همچنین اجرا استفاده گردید. همچنین به این مسئله اشاره می شود که این پروتکل ها از تصادفی بودن محلی از دیدگاه هر همتا اطمینان حاصل می کنند. همچنین مشاهده گردید که تا زمانی که خصوصیات کلی مد نظر باشند، متوسط طول مسیر به گراف های تصادفی نزدیک بوده و خصوصیات خوشه بندی و رشد تحت کنترل پارامتر H می باشند. در خصوص تحمل و مقاومت در برابر خرابی، عکس العمل بالایی نسبت به نرخ چرن بالا و خصوصیات خوددرمانی بسیار خوب مشاهده می شود که عمدتاً تحت کنترل پارامتر H می باشند.
بخشی از مقاله انگلیسی:
1. INTRODUCTION
Gossip-based protocols, also called epidemic protocols, are appealing in large-scaledistributed applications. The popularity of these protocols stems from their abilityto reliably pass information among a large set of interconnected nodes, even if thenodes regularly join and leave the system (either purposefully or on account offailures), and the underlying network suffers from broken or slow links.In a gossip-based protocol, each node in the system periodically exchanges infor-mation with a subset of its peers. The choice of this subset is crucial to the widedissemination of the gossip. Ideally, any given node should exchange informationwith peers that are selected following a uniform random sample of all nodes cur-rently in the system [Demers et al. 1987; van Renesse et al. 1998; Birman et al.1999; Karp et al. 2000; Sun and Sturman 2000; Kowalczyk and Vlassis 2005]. Thisassumption has led to rigorously establish many desirable features of gossip-basedprotocols like scalability, reliability, and efficiency (see, e.g., [Pittel 1987] in thecase of information dissemination, or [Kempe et al. 2003; Jelasity et al. 2005] foraggregation).In practice, enforcing this assumption would require to develop applicationswhere each node may be assumed to know every other node in the system [Bir-man et al. 1999; Gupta et al. 2002; Kermarrec et al. 2003]. However, providingeach node with a complete membership table from which a random sample can bedrawn, is unrealistic in a large-scale dynamic system, for maintaining such tables inthe presence of joining and leaving nodes (referred to as churn) incurs considerablesynchronization costs. In particular, measurement studies on various peer-to-peernetworks indicate that an individual node may often be connected in the order ofonly a few minutes to an hour (see, e.g. [Bhagwan et al. 2003; Saroiu et al. 2003;Sen and Wang 2004]). Clearly, decentralized schemes to maintain membership information are crucialto the deployment of gossip-based protocols. This paper factors out the very ab-straction of a peer-sampling service and presents a generic, yet simple, gossip-basedframework to implement it.The peer-sampling service is singled-out from the application using it and, ab-stractly speaking, the same service can be used in different settings: informationdissemination [Demers et al. 1987; Eugster et al. 2004], aggregation [Kempe et al.2003; Jelasity et al. 2005; Jelasity et al. 2004; Montresor et al. 2004], load bal-ancing [Jelasity et al. 2004], and network management [Voulgaris and van Steen2003; Voulgaris et al. 2005]. The service is promoted as a first class abstraction ofa large-scale distributed system. In a sense, it plays the role of a naming service ina traditional LAN-oriented distributed system as it provides each node with othernodes to interact with. The basic general principle underlying the framework we propose to implement the peer-sampling service, is itself based on a gossip paradigm. In short, everynode (1) maintains a relatively small local membership table that provides a partialview on the complete set of nodes and (2) periodically refreshes the table usinga gossiping procedure. The framework is generic and can be used to instantiateknown [Eugster et al. 2003; Jelasity et al. 2003; Voulgaris et al. 2005] and novelgossip-based membership implementations. In fact, our framework captures manypossible variants of gossip-based membership dissemination. These variants mainlydiffer in the way the membership table is updated at a given node after the exchangeof tables in a gossip round.
9. CONCLUDING REMARKS
Gossip protocols have recently generated a lot of interest in the research community. The overlays that result from these protocols are highly resilient to failures and high churn rates. The underlying paradigm is clearly appealing to build large-scale distributed applications
The contribution of this paper is to factor out the abstraction implemented by the membership mechanism underlying gossip protocols: the peer-sampling service. The service provides every peer with (local) knowledge of the rest of system, which is key to have the system converge as a whole towards global properties using only local information.
We described a framework to implement a reliable and efficient peer-sampling service. The framework itself is based on gossiping. This framework is generic enough to be instantiated with most current gossip membership protocols [Eugster et al. 2003; Jelasity et al. 2003; Stavrou et al. 2004; Voulgaris et al. 2005]. We used this framework to empirically compare the range of protocols through simulations based on synthetic and realistic traces as well as implementations. We point out the very fact that these protocols ensure local randomness from each peer’s point of view. We also observed that as far as the global properties are concerned, the average path length is close to the one in random graphs and that clustering properties are controlled by (and grow with) the parameter H. With respect to fault tolerance, we observe a high resilience to high churn rate and particularly good self-healing properties, again mostly controlled by the parameter H.
| عنوان فارسی مقاله: | نمونه گیری همتا برمبنای گوسیپ (Gossip) |
| عنوان انگلیسی مقاله: | Gossip-based Peer Sampling |
خرید ترجمه فارسی مقاله با فرمت ورد