Of Choices, Failures and Asynchrony: The Many Faces of Set Agreement
Of Choices, Failures and Asynchrony: The Many Faces of Set Agreement
复制标题
选择、失败和异步：既定协议的多面性
作者：
Dan Alistarh;Seth Gilbert;R. Guerraoui;Corentin Travers
集合一致是分布式计算中的一个基本问题，在这个问题中，进程集体地从一个较大的建议集合中选择一个小子集的值。异步网络中容错集协议的不可能性是分布式计算的重要成果之一。在同步网络中，集合协议的复杂性一直是一个重要的研究挑战，现在已经解决了。然而，真实的系统既不是纯同步的，也不是纯异步的。相反，它们倾向于在同步周期和异步周期之间交替。对于这种“部分同步”设置中集合协议的复杂性，我们一无所知。在本文中，我们解决了这一挑战，提出了此类系统中集合一致复杂性的第一个（渐近）紧界。我们介绍了一种新的技术，用于在一个容易出错的异步共享内存中模拟一个异步和容易出错的消息传递系统的执行，其中一些片段对某些进程来说是同步的。利用该仿真技术，通过对异步无等待集合协议的约简，得到了部分同步系统中集合协议轮复杂度的下界。具体来说，我们表明每个集合协议协议至少需要documentclass[12pt]{minimal} uspackage {amsmath} uspackage {wasysym} uspackage {amsfonts} uspackage {amssymb} uspackage {amssyb} uspackage {mathrsfs} uspackage {upgreek} setlength{oddsidemargin}{-69pt} egin{document}$lfloorfrac{t}{k}
floor + 2$end{document}同步轮来决定。我们提出了一种（渐近）匹配算法，该算法依赖于分布式异步检测机制，以便在同步期间尽快做出决定。从这两个结果中，我们推导出解决集合一致性所需的最小同步窗口的大小。通过将同步、异步和部分同步环境联系起来，我们的仿真技术具有独立的意义。特别是，它允许我们获得与Gafni et al. （SIAM J. Comput. 40(1): 63-78, 2011）互补的早期决定k集协议复杂性的新下界，并重新导出了Guerraoui et al. （thetheet al.）的组合拓扑下界。第一版。科学通报，2009,(6):557 - 558。
Set agreement is a fundamental problem in distributed computing in which processes collectively choose a small subset of values from a larger set of proposals. The impossibility of fault-tolerant set agreement in asynchronous networks is one of the seminal results in distributed computing. In synchronous networks, too, the complexity of set agreement has been a significant research challenge that has now been resolved. Real systems, however, are neither purely synchronous nor purely asynchronous. Rather, they tend to alternate between periods of synchrony and periods of asynchrony. Nothing specific is known about the complexity of set agreement in such a “partially synchronous” setting. In this paper, we address this challenge, presenting the first (asymptotically) tight bound on the complexity of set agreement in such systems. We introduce a novel technique for simulating, in a fault-prone asynchronous shared memory, executions of an asynchronous and failure-prone message-passing system in which some fragments appear synchronous to some processes. We use this simulation technique to derive a lower bound on the round complexity of set agreement in a partially synchronous system by a reduction from asynchronous wait-free set agreement. Specifically, we show that every set agreement protocol requires at least documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$lfloorfrac{t}{k}
floor + 2$end{document} synchronous rounds to decide. We present an (asymptotically) matching algorithm that relies on a distributed asynchrony detection mechanism to decide as soon as possible during periods of synchrony. From these two results, we derive the size of the minimal window of synchrony needed to solve set agreement. By relating synchronous, asynchronous and partially synchronous environments, our simulation technique is of independent interest. In particular, it allows us to obtain a new lower bound on the complexity of early deciding k-set agreement complementary to that of Gafni et al. (in SIAM J. Comput. 40(1):63–78, 2011), and to re-derive the combinatorial topology lower bound of Guerraoui et al. (in Theor. Comput. Sci. 410(6–7):570–580, 2009) in an algorithmic way.