ملخص
The Choice Coordination Problem with k alternatives (k-CCP) was introduced by Rabin in 1982 [Rab82]. The goal is to design a wait-free protocol for n asynchronous processes which causes all correct processes to agree on one out of k possible alternatives. The agreement on a single choice is complicated by the fact that there is no a priori agreement on names for the alternatives. Furthermore processes must state their choice and do all communication via registers associated with the alternatives. We exactly characterize when the k-CCP can be solved deterministiclly, prove upper and lower space bounds for deterministic solutions, and provide a randomized protocol which is significantly better than the deterministic lower bound.
اللغة الأصلية | الإنجليزيّة |
---|---|
عنوان منشور المضيف | Distributed Algorithms - 6th International Workshop, WDAG 1992, Proceedings |
المحررون | Adrian Segall, Shmuel Zaks |
ناشر | Springer Verlag |
الصفحات | 54-68 |
عدد الصفحات | 15 |
رقم المعيار الدولي للكتب (المطبوع) | 9783540561880 |
المعرِّفات الرقمية للأشياء | |
حالة النشر | نُشِر - 1992 |
منشور خارجيًا | نعم |
الحدث | 6th International Workshop on Distributed Algorithms, WDAG 1992 - Haifa, إسرائيل المدة: ٢ نوفمبر ١٩٩٢ → ٤ نوفمبر ١٩٩٢ |
سلسلة المنشورات
الاسم | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
مستوى الصوت | 647 LNCS |
رقم المعيار الدولي للدوريات (المطبوع) | 0302-9743 |
رقم المعيار الدولي للدوريات (الإلكتروني) | 1611-3349 |
!!Conference
!!Conference | 6th International Workshop on Distributed Algorithms, WDAG 1992 |
---|---|
الدولة/الإقليم | إسرائيل |
المدينة | Haifa |
المدة | ٢/١١/٩٢ → ٤/١١/٩٢ |
ملاحظة ببليوغرافية
Publisher Copyright:© 1992, Springer Verlag. All rights reserved.