ترتیب پیام و چندپخشی
ارتباط گروهی، پیامی را با تضمینهای قابلیت اطمینان و ترتیب مشخص، از FIFO تا ترتیب علّی و کلی، به مجموعهای از فرآیندها تحویل میدهد.
Definition
چندپخشی یک پیام واحد را به هر عضو یک گروه فرآیند تحویل میدهد؛ تضمینهای ترتیب، ترتیب تحویل نسبی پیامها را محدود میکنند، به طوری که FIFO ترتیب هر فرستنده را حفظ میکند، علّی ترتیب «پیش از وقوع» را حفظ میکند، و ترتیب کلی همه پیامها را با یک توالی در هر عضو تحویل میدهد.
Scope
این موضوع چندپخشی قابل اعتماد و سلسلهمراتب ترتیبهای تحویل — FIFO، علّی و کلی (اتمی) — پیادهسازی آنها با استفاده از شمارههای توالی، ساعتهای منطقی، و طرحهای توالیساز یا توکن، و مدل همگامسازی مجازی که چندپخشی مرتب را با تغییرات سازگار عضویت گروه یکپارچه میکند، را پوشش میدهد. پخش کلی (اتمی) معادل قدرت اجماع نشان داده شده است.
Core questions
- یک برنامه کاربردی چه تضمینهای قابلیت اطمینان و ترتیب را از ارتباط گروهی نیاز دارد؟
- ترتیبهای تحویل علّی و کلی چگونه به طور کارآمد پیادهسازی میشوند؟
- چرا پخش کلی معادل اجماع است؟
Key theories
- سلسلهمراتب ترتیب
- ترتیبهای تحویل یک سلسلهمراتب را تشکیل میدهند — FIFO ضعیفتر از علّی است، که ضعیفتر از ترتیب کلی است — هر یک با فرادادههای اضافی مانند شمارههای توالی هر فرستنده، برچسبهای زمانی برداری، یا یک توالی مورد توافق جهانی اعمال میشود.
- همگامسازی مجازی
- همگامسازی مجازی تغییرات عضویت گروه و پیامهای چندپخشی را به ترتیبی سازگار به همه اعضا ارائه میدهد، به طوری که فرآیندها توالی یکسانی از رویدادها و تغییرات دیدگاه را مشاهده میکنند، که ساخت سرویس تکثیر شده را ساده میکند.
- پخش اتمی برابر با اجماع
- پخش کلی (اتمی) و اجماع به یکدیگر قابل تقلیل هستند، بنابراین هر راهحلی برای یکی، راهحلی برای دیگری ارائه میدهد و هر دو محدودیتهای حلپذیری یکسانی را تحت عدم همگامسازی و شکستها به اشتراک میگذارند.
Clinical relevance
چندپخشی مرتب و قابل اعتماد، زیربنای تکثیر ماشین حالت، سیستمهای انتشار-اشتراک، و پایگاههای داده تکثیر شده است، جایی که هر نسخه باید بهروزرسانیهای یکسان را به ترتیب یکسان اعمال کند تا سازگار باقی بماند.
History
بیرمن و جوزف همگامسازی مجازی و چندپخشی مرتب را در دهه 1980 از طریق سیستم ISIS معرفی کردند؛ رابطه بین پخش اتمی و اجماع در دهه 1990 روشن شد، و بررسی دفاگو، شیپر و اوربان در سال 2004 بسیاری از الگوریتمهای ترتیب کلی را نظاممند کرد.
Key figures
- Kenneth Birman
- Thomas Joseph
- Andre Schiper
- Leslie Lamport
Related topics
Seminal works
- birman1987
- defago2004
- lamport1978
Frequently asked questions
- تفاوت بین ترتیب علّی و کلی چیست؟
- ترتیب علّی فقط پیامهایی را که به طور علّی مرتبط هستند محدود میکند و پیامهای همزمان را آزاد میگذارد تا در فرآیندهای مختلف با ترتیبهای متفاوت تحویل داده شوند. ترتیب کلی از هر فرآیند میخواهد که همه پیامها را با توالی یکسان تحویل دهد، که به مراتب قویتر و به سختی اجماع است.