A modular approach to shared-memory consensus, with applications to the probabilistic-write model
A modular approach to shared-memory consensus, with applications to the probabilistic-write model
复制标题
共享内存共识的模块化方法，以及概率写入模型的应用
DOI：
10.1007/s00446-011-0134-8
复制
发表时间：
2010
影响因子：
1.3
通讯作者：
J. Aspnes
中科院分区：
文献类型：
--
作者：
J. Aspnes
我们表明，共识可以通过交替采用-提交对象的顺序来解决(Gafni在第17届ACM分布式计算原理年度研讨会的论文集上，第143-152页，1998；Alistarh等人。在《艾萨克》一书中，《计算机科学讲义》，第5878卷。施普林格，柏林，943-953页，2009)，它们检测到一致，以及调解人，它们确保以一定概率达成一致。我们观察到，大多数已知的随机共识算法都具有这种结构。对于使用lgm+Θ(Loglogm)空间和单个工作的无限数量的进程，我们给出了一个m值采用-提交对象的确定性实现。我们还给出了n进程概率写模型中任意值的随机化调解器，它保证在使用一个多写寄存器、O(Logn)期望个体工作和Θ(N)期望总工作的情况下以恒定概率一致。结合这些对象给出了概率写模型的共识协议，该模型使用O(logm+logn)个工作和O(Nlogm)个总工作。在这个模型中，以前的协议都不使用次线性的单个功或对常数m使用线性的总功。
We show that consensus can be solved by an alternating sequence of adopt-commit objects (Gafni in Proceedings of the seventeenth annual ACM symposium on principles of distributed computing, pp 143–152, 1998; Alistarh et al. in ISAAC, Lecture notes in computer science, vol 5878. Springer, Berlin, pp 943–953, 2009), which detect agreement, and conciliators, which ensure agreement with some probability. We observe that most known randomized consensus algorithms have this structure. We give a deterministic implementation of an m-valued adopt-commit object for an unbounded number of processes that uses lg m + Θ(log log m) space and individual work. We also give a randomized conciliator for any number of values in the probabilistic-write model with n processes that guarantees agreement with constant probability while using one multi-writer register, O(log n) expected individual work, and Θ(n) expected total work. Combining these objects gives a consensus protocol for the probabilistic-write model that uses O(log m + log n) individual work and O(n log m) total work. No previous protocol in this model uses sublinear individual work or linear total work for constant m.