תקציר
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 |
| מזהי עצם דיגיטלי (DOIs) | |
| סטטוס פרסום | פורסם - 1992 |
| פורסם באופן חיצוני | כן |
| אירוע | 6th International Workshop on Distributed Algorithms, WDAG 1992 - Haifa, ישראל משך הזמן: 2 נוב׳ 1992 → 4 נוב׳ 1992 |
סדרות פרסומים
| שם | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| כרך | 647 LNCS |
| ISSN (מודפס) | 0302-9743 |
| ISSN (אלקטרוני) | 1611-3349 |
כנס
| כנס | 6th International Workshop on Distributed Algorithms, WDAG 1992 |
|---|---|
| מדינה/אזור | ישראל |
| עיר | Haifa |
| תקופה | 2/11/92 → 4/11/92 |
הערה ביבליוגרפית
Publisher Copyright:© 1992, Springer Verlag. All rights reserved.