本文从理论的角度对分布选择问题进行了研究。给定直径的一般连通图<我>D我>组成的<我>n我>的目标,其中每个节点保存一个数字元素的节点<我>k我>-选择算法是确定的<我>k我>th我>最小的元素。我们证明了分布式选择确实比其他聚合函数需要更多的工作,例如计算所有元素的平均值或最大值。另一方面,我们表明<我>k我>th我>最小元素可以通过提供随机和确定两种方式有效地计算出来<我>k我>-选择算法,消除了通过网络内聚合解决分布式选择不可行的误解。
回到顶部一个>
最近,由于数据挖掘或传感器网络等新兴应用领域的出现,人们对分布式聚合的兴趣日益浓厚。<年代up>2一个>,<一个href="#R8">8一个>,<一个href="#R23">23一个>,<一个href="#R24">24一个>分布式聚合的目标是在一组分布式值上计算聚合函数,每个值存储在网络中的一个节点上。典型的聚合函数有<我>最大值,和,计数,平均值,中位数,方差我>,<我>k我>th我>最小的我>,或<我>最大的价值我>,或者它们的组合,例如,“最大的10%的值的平均值是多少?”
数据库社区将聚合函数分为三类:分布式的<我>(max, min, sum, count)我>、代数<我>(加,减,平均,方差)我>,整体<我>(中位数,k<年代up>th年代up>最小的,或<我>最大的值)。我>这些函数的组合被认为可以支持大量合理的聚合查询。<年代up>一个一个>
众所周知,分配函数和代数函数可以很容易地用所谓的<我>convergecast我>在预计算对象上执行的操作<我>广度优先搜索我>(BFS)树:树的根向树的叶子发送消息,要求叶子开始聚合。生成树的内部节点等待从所有子节点接收到聚合数据后,对自己的数据和聚合数据应用聚合函数,然后将聚合结果转发给各自的父节点。Convergecast是快速的,因为它最多在之后终止<我>二维我>T我>时间,<我>D我>T我>表示生成树的深度。请注意,BFS树的深度最多为直径<我>D我>原始图形的<我>G我>,因此一次聚合铸造成本仅为<我>二维我>时间。中描述了在传感器网络环境中这样一棵生成树的一个例子<一个href="#F1">图1一个>.但是,集合变换不能支持整体功能。毕竟,“整体”这个名字本身就表明一个人“不能查看”一组值,更准确地说,所有的值需要集中在一个节点上才能计算整体函数。坦率地说,网络内聚合被认为实际上不可能实现整体功能。
对于任意的<我>k我>,一个选择算法回答有关的问题<我>k我>th我>一个集合或网络中的最小值。的特殊情况<我>k我>选择问题,<我>k = n / 2我>是著名的<我>中值问题。我>一般来说,选择可以解决关于订单统计信息和百分比的聚合查询。令人惊讶的是,人们对分布式(网络)选择知之甚少,尽管它对理解数据聚合至关重要。
在本文中,我们对一般网络的分布式选择问题给出了一些新的见解<我>n我>节点和直径<我>D我>.特别地,我们通过给出的下界,证明了分布式选择比收敛变换严格地更难W(<我>D我>日志<年代ub>D我>n我>)的时间复杂度。换句话说,就我们所知,我们是第一个正式确认整体函数比分配函数或代数函数严格地更难这一先见的人。此外,在第4.1节,我们提出了一部小说<我>拉斯维加斯算法我>用高概率匹配这个下界,改进了最佳随机算法。对于许多网络,这个运行时间严格低于收集一个节点上的所有值,我们的新上界证明(与通常的看法相反)对于整体功能,网络内聚合也是可能的;事实上,在直径较大的网络拓扑中,例如网格或典型的无线传感器网络,选择可以在收敛变换相同的渐近时间范围内进行。第三个结果,在第4.2节中,我们对算法进行了去随机化,得到了一个确定性的分布式选择算法,其时间复杂度为<我mg src="https://dl.acm.org/cms/attachment/a424ea49-202e-4a69-95ee-d7ef3bef98ad/cacm5109_a.gif" border="0" hspace="2" alt="cacm5109_a.gif">这是对现有技术的重大改进。
找到<我>k我>th我>一组中最小的值<我>n我>元素是一个经典的问题,在过去的大约30年里,在分布式和非分布式环境中都得到了广泛的研究。找到中值的问题,即元素中一半较小,另一半较大,是一种特殊情况<我>k我>-选择问题,也得到了很多关注。布卢姆等。<年代up>1一个>提出了第一个确定性序列算法,给定数组的大小<我>n我>,计算<我>k我>th我>最小的元素<我>O (n)我>时间。该算法将<我>n我>元素大致<我>n / 5我>一组5个元素,并确定每组元素的中位数。它们的中位数<我>n / 5我>然后递归计算中位数。虽然这个中位数的中位数不一定是所有中位数<我>n我>元素,它仍然很好地划分了所有元素,至少(大约)30%的元素更小,也至少30%的元素更大。这样,至少可以排除所有元素的30%,剩余元素递归应用该算法。仔细分析这个算法就会发现只有<我>O (n)我>总共需要操作。随后,Schönhage等。<年代up>19一个>开发了一种算法,在最坏情况下需要更少的比较。
就分布而言<我>k我>-选择,多年来已经为各种模型积累了丰富的算法集合。大量的工作集中在特殊的图上,如星图和完全图。<年代up>9一个>,<一个href="#R16">16一个>由两个连通的节点组成的小图,其中每个节点知道所有节点的一半<我>n我>文中还研究了时间复杂度为<我>O我>(日志<我>n我>)。<年代up>3.一个>,<一个href="#R15">15一个>对于受限模型中的确定性算法,这个结果是严格的。<年代up>15一个>完了<年代up>14一个>提出了环、网格和时间复杂度为<我>O我>(<我>n我>),<我>O我>(<我mg src="https://dl.acm.org/cms/attachment/dd2589e8-b410-4e34-8bfd-884fbc748dec/cacm5109_i.gif" border="0" hspace="2" alt="cacm5109_i.gif">),<我>O我>(日志<年代up>3.年代up>n我>),分别。
几个算法,都是确定性的<年代up>12一个>,<一个href="#R13">13一个>,<一个href="#R20">20.一个>和概率性质,<年代up>17一个>,<一个href="#R18">18一个>,<一个href="#R20">20.一个>也被设计用于任意连通图。其中一些确定性算法限制了节点可以容纳的元素,即最大数值项<我>x我>马克斯我>必须被限定<我>O我>(<我>n我>O (1)我>).给定这个约束条件,应用二叉搜索的时间复杂度为<我>O我>(<我>D我>日志<我>x我>马克斯我>) =<我>O我>(<我>D我>日志<我>n我>).<年代up>13一个>或者,通过指数增加最初的猜测<我>x我>k我>= 1时,可以在中找到解<我>O我>(<我>D我>日志<我>x我>k我>).<年代up>12一个>据我们所知,唯一的非限制性确定性<我>k我>-对于节点数次线性时间复杂度的一般图的选择算法是由Shrira等人提出的。<年代up>20.一个>他们对Blum等人用于分布式设置的经典顺序算法的改进,其最坏情况运行时间为<我>O我>(<我>Dn我>0.9114年代up>).在同一工作中,提出了一般图的随机化算法。该算法简单地向一个随机节点查询其元素,并使用这种猜测来缩小潜在元素的数量。期望的时间复杂度为<我>O我>(<我>D我>日志<我>n我>).肯普等。<年代up>7一个>提出了一种基于八卦的算法,其概率至少为1<我mg src="https://dl.acm.org/cms/attachment/a814093c-b1e3-4714-8405-07c8f4289d2e/isin.gif" border="0" hspace="2" alt="isin.gif">计算<我>k我>th我>最小的元素在<我>O我>(日志<我>n我>+日志1 /<我mg src="https://dl.acm.org/cms/attachment/a814093c-b1e3-4714-8405-07c8f4289d2e/isin.gif" border="0" hspace="2" alt="isin.gif">) +(日志<我>n我>+日志日志<我>1/<我mg src="https://dl.acm.org/cms/attachment/a814093c-b1e3-4714-8405-07c8f4289d2e/isin.gif" border="0" hspace="2" alt="isin.gif">))在一个完整的图表上交流轮。
如果元素的个数<我>N我>比节点数大得多,在<我>O我>(<我>D我>日志记录分钟{<我>k我>,<我>n - k + 1我>})的期望时间,使用Santoro等人提出的算法可以将问题简化为每个节点只有一个元素的问题。<年代up>17一个>,<一个href="#R18">18一个>然而,他们的算法取决于节点上元素的特定分布。Patt-Shamir<年代up>13一个>表明中值可以非常有效地逼近,再次受到限制,即最大元素必须以多项式为界<我>n我>.
在我们的系统模型中,我们给出了一个连通图<我>G = (v, e)我>的直径<我>D我>与节点集<我>V我>和边集<我>E。我>节点集的基数是|<我>V我>| =<我>n我>表示节点<我>v我>1年代ub>、……<我>v我>n我>.的<我>直径我>图中任意两个节点之间的最长最短路径的长度。每个节点<我>v我>我我>保存单个元素<我>x我>我我>.<年代up>b一个>在不失一般性的前提下,我们可以假定所有元素<我>x我>我我>是独一无二的。如果两个元素<我>x我>我我>而且<我>x我>j我>节点id,例如:<我>我我>而且<我>j我>,可以作为决胜局。目标是高效地计算<我>k我>th我>所有元素中最小的元素<我>x我>1年代ub>、……<我>x我>n我>,节点可以通过交换消息来实现这一目标。节点<我>v我>我我>而且<我>v我>j我>可以直接沟通如果(<我>v我>我我>,<我>v我>j我>)<我mg src="https://dl.acm.org/cms/attachment/a814093c-b1e3-4714-8405-07c8f4289d2e/isin.gif" border="0" hspace="2" alt="isin.gif">E我>.
采用标准的异步通信模型。在本文中,通信被认为是可靠的,没有节点故障,并且所有节点都遵循强制协议。我们没有对存储元素的大小施加任何限制。但是,我们限制任何单个消息的大小,这样它可以只包含固定数量的节点id和元素,而且最多也只能包含固定数量的元素<我>O我>(日志<我>n我>)任意附加位。通过限制消息的大小,我们努力获取消息的大小<我>信息我>必须在节点之间交换才能解决问题。此外,这种限制是非常自然的,因为消息大小在实际应用程序中通常是有限的。请注意,如果没有对消息大小的这种限制,单个convergecast就足以在单个节点上累积所有元素,这随后可以在本地解决问题。
这两个算法都是<我>迭代我>由于它们不断减少可能解的集合,我们需要区分持有仍然感兴趣的元素的节点和其他节点。因此,第一组节点称为<我>候选节点我>或<我>候选人。我>我们把搜索空间的缩减称为一个特定的因子<我>一个阶段我>的算法。阶段中候选节点的数量<我>我我>来标示<我>n我>(<我>我我>)
我们假设所有节点都知道直径<我>D我>的图。此外,假设已经预先计算了在初始化算法的节点上扎根的BFS生成树。这些假设是不关键的,因为直径和生成树都可以计算<我>二维我>时间。<年代up>14一个>
主要的复杂性度量是时间复杂度,对于确定性算法来说,在最坏情况下,每个合法输入和每个执行场景从执行开始到完成所需的时间。将时间复杂度标准化,假设最慢的消息在一个时间单位后到达目标。对于我们的随机算法,我们以高概率确定算法执行完成的时间,即概率至少为1<我mg src="https://dl.acm.org/cms/attachment/3d2099a7-c8b7-4d75-a349-f070c44071df/cacm5109_b.gif" border="0" hspace="2" alt="cacm5109_b.gif">为一个常数<我>c我>> = 1。因此,在这两种情况下,我们都没有为本地计算分配任何成本。
本文提出的算法在连续阶段操作,其中候选空间稳步减少。这种模式是很自然的<我>k我>-选择,并用于所有其他提出的算法,包括非分布式情况。最著名的一般图的确定性分布式算法使用了众所周知的分布式版本<我>median-of-median我>技术,我们在第2节中简要概述,导致时间复杂度<我>O我>(<我>Dn我>0.9114年代up>)以维持恒定的群体规模。对该算法进行了简单的修改,其中组大小在每个阶段<我>我我>被设置为<我>O我>(<我mg src="https://dl.acm.org/cms/attachment/7a85a1eb-565b-4502-9187-ef143804b0cb/cacm5109_j.gif" border="0" hspace="2" alt="cacm5109_j.gif">(我)我>)会导致更好的时间复杂度。可以证明,该算法的时间复杂度是有界的<我>O我>(<我>D我>(日志<我>n我>)<年代up>日志记录<我>n + O (1)我>).然而,由于我们提出的算法要好得多,我们将不再进一步讨论这种基于中值的中值算法。由于确定性算法的复杂性,我们将首先处理随机算法。
4.1随机算法
虽然一种权宜的确定性算法的推导有点复杂,但提出一种快速的随机算法却非常简单。Shrira等人提出了一个明显的解决方案,<年代up>20.一个>是随机选择一个节点,取其元素作为初始猜测。在计算了具有较小和较大元素的节点数量后,很可能所有节点中有相当一部分不再需要考虑。通过在剩余的候选节点上迭代这个过程<我>k我>th我>最小的元素可以快速找到<我>k我>.
节点可以通过以下方式随机选择:在生成树中,从根节点开始,沿着一条随机路径发送一条将要选择的随机元素的消息。如果根节点有<我>l我>孩子们<我>v我>1年代ub>、……<我>u我>l我>那里的孩子<我>V我>我我>子树的根是<我>n我>我我>候选节点包括它自己,根结点有概率选择它自己的元素<我mg src="https://dl.acm.org/cms/attachment/9971ea37-3b12-4d48-a5c2-2119420c7905/cacm5109_c.gif" border="0" hspace="2" alt="cacm5109_c.gif">.否则,它会发送一条消息给它的一个子进程。消息被转发到节点<我>v我>我我>的概率<我mg src="https://dl.acm.org/cms/attachment/cbbbcd0d-314e-4078-968c-48d09204da71/cacm5109_d.gif" border="0" hspace="2" alt="cacm5109_d.gif">对所有<我>我我>{1,…,<我>l我>},消息的接收者以同样的方式继续。很容易看出,该方案均匀随机选择一个节点,最多需要2个节点<我>D我>时间,因为到达任何节点和返回报告的时间都是有限的<我>D我>.注意,在每个阶段之后,概率会发生变化,因为它们取决于每个子树中剩余的候选节点数量的变化。然而,在确定了解必须存在的新区间后,所有子树中满足新谓词的节点数可以再次用2计算<我>D我>时间。
这个简单的过程产生了一个算法来查找<我>k我>th我>最小的元素<我>O我>(<我>D我>日志<我>n我>)预期时间,如<我>O我>(日志<我>n我>阶段足以将候选的数量缩小到一个小的常数。甚至可以证明所需的时间是<我>O我>(<我>D我>日志<我>n我>),概率大。改进该算法的关键观察是随机选择一个节点总是需要<我>O我>(<我>D我>)时间时,为了进一步减少候选节点的数量,应在单个阶段中选择多个随机元素。可以很容易地修改选择单个随机元素的方法,通过在请求消息中包含所需的随机元素的数量,从而允许选择多个随机元素。在本地接收到这类消息的节点决定是否选择了自己的元素,以及其子树必须提供多少随机元素。随后,它将请求转发给它的所有子节点,这些子节点的子树必须产生至少一个随机元素。注意,所有随机元素都可以在<我>D我>时间与随机元素的数量无关,但由于只能将常数数量的元素打包到单个消息中这一限制,很可能不是所有元素都可以传播回根中<我>D我>时间。然而,所有元素仍然到达根in<我>O我>(<我>D我>)时间,如果随机元素的数量为<我>O我>(<我>D我>).
通过使用这个简单的<我>流水线我>技术选择<我>O我>(<我>D我>的随机元素<我>O我>(<我>D我>)时,我们立即得到一个更有效的算法,我们以后将称之为<我>一个我>兰德我>在选择<我>O我>(<我>D我>)元素在每个相中均匀随机地,可以表明,候选的数量减少了一个因子<我>O我>(<我>D我>)在恒定数量的相中,具有较高的概率<我>O我>(<我>D我>),而不是在只选择单个元素的情况下仅仅是一个常数因子。这个结果,加上观察到的每个阶段的成本仅仅是<我>O我>(<我>D我>时,用来证明下面的定理。
定理4.1。<我>在直径为D >= 2的n个节点连通图中,算法a的时间复杂度我>兰德我>O (D我>日志<年代ub>D我>n) w.h.p。我>
特别是在图中<我>D我>大,算法<我>一个我>兰德我>比在每个阶段只选择一个随机元素的算法要快得多。在第5节中,我们证明了没有确定性算法或概率算法可以在渐近上更好,即:<我>一个我>兰德我>是<我>渐近最优的。我>
4.2确定的算法
确定性迭代算法的难点在于<我>k -我>选择在于对元素的选择,这些元素被证明可以减少每个阶段的搜索空间。一旦找到这些元素,就可以用与随机算法相同的方法确定候选节点的简化集。因此,确定性算法,简称为<我>一个我>依据我>,必须计算一组<我>O我>(<我>D我>)元素对所有元素进行类似于算法使用的随机集的划分<我>一个我>兰德我>在每一个阶段。
解决这个问题的一个简单方法是,从生成树的叶子节点开始向上发送元素,将内部节点上所有子节点的元素累加起来,然后递归地转发选择的<我>t我>元素到父元素。这种方法的问题是将从子节点接收到的所有元素减少到所需的元素<我>t我>元素。如果一个节点<我>v我>我我>接收<我>t我>元素<我>c我>我我>生成树中的子结点<我>t我>所有分区的元素<我>c我>我我>t我>应该找到大小大致相等的节点。然而,为了找到这些元素,每个片段中的元素数量必须从叶节点开始计算。由于这个计数必须在沿着根路径的每一步中重复,找到一个有用的分区所需的时间<我>k我>段要求<我>O(D (D + Ct))我>时间,<我>C我>: =马克斯<年代ub>我<我mg src="https://dl.acm.org/cms/attachment/a814093c-b1e3-4714-8405-07c8f4289d2e/isin.gif" border="0" hspace="2" alt="isin.gif">{1,…,n}我>C我>我我>.这种方法有几个缺点:它至少需要花费时间<我>O我>(<我>D我>2年代up>)的时间,只是找到一个分区,时间的复杂性取决于生成树的结构。
我们的算法<我>一个我>依据我>按以下方式解决这些问题。在任何阶段<我>我我>,算法将整个生成树分解为<我>O我>(<我mg src="https://dl.acm.org/cms/attachment/2a44ee7a-a47a-42e2-af9a-e721803c5504/cacm5109_k.gif" border="0" hspace="2" alt="cacm5109_k.gif">),大小不一<我>O我>(<我>n我>(我)我>/<我mg src="https://dl.acm.org/cms/attachment/2a44ee7a-a47a-42e2-af9a-e721803c5504/cacm5109_k.gif" border="0" hspace="2" alt="cacm5109_k.gif">).<一个href="#F2">图2一个>描述了一个分为4组的示例树。递归地,在每个组中,特定的节点启动相同的分区<我>O我>(<我mg src="https://dl.acm.org/cms/attachment/2a44ee7a-a47a-42e2-af9a-e721803c5504/cacm5109_k.gif" border="0" hspace="2" alt="cacm5109_k.gif">)组,只要组大小大于<我>O我>(<我mg src="https://dl.acm.org/cms/attachment/2a44ee7a-a47a-42e2-af9a-e721803c5504/cacm5109_k.gif" border="0" hspace="2" alt="cacm5109_k.gif">).这种递归划分的目标是找到每一组,<我>O我>(<我mg src="https://dl.acm.org/cms/attachment/2a44ee7a-a47a-42e2-af9a-e721803c5504/cacm5109_k.gif" border="0" hspace="2" alt="cacm5109_k.gif">)元素将搜索空间减少一个因子<我>O我>(<我mg src="https://dl.acm.org/cms/attachment/2a44ee7a-a47a-42e2-af9a-e721803c5504/cacm5109_k.gif" border="0" hspace="2" alt="cacm5109_k.gif">).群组大小最多<我>O我>(<我mg src="https://dl.acm.org/cms/attachment/2a44ee7a-a47a-42e2-af9a-e721803c5504/cacm5109_k.gif" border="0" hspace="2" alt="cacm5109_k.gif">)可以简单地将它们的所有元素报告给在这个递归级别启动分组的节点。一旦有这样的初始节点<我>v我>已收到所有<我>O我>(<我mg src="https://dl.acm.org/cms/attachment/2a44ee7a-a47a-42e2-af9a-e721803c5504/cacm5109_k.gif" border="0" hspace="2" alt="cacm5109_k.gif">)的元素<我>O我>(<我mg src="https://dl.acm.org/cms/attachment/2a44ee7a-a47a-42e2-af9a-e721803c5504/cacm5109_k.gif" border="0" hspace="2" alt="cacm5109_k.gif">)创建的组,它会对它们进行分类<我>O我>(<我>D我>)元素,然后发出一个请求,对每个元素中的节点进行计数<我>O我>(<我>D我>)由接收元件引起的间隔。假设所有组都由节点创建<我>v我>一起包含<我mg src="https://dl.acm.org/cms/attachment/9f68a974-2b3d-4728-a4b7-46decc70654e/cacm5109_e.gif" border="0" hspace="2" alt="cacm5109_e.gif">节点在阶段<我>我我>.这些间隔可以局部地合并为<我>O我>(<我mg src="https://dl.acm.org/cms/attachment/2a44ee7a-a47a-42e2-af9a-e721803c5504/cacm5109_k.gif" border="0" hspace="2" alt="cacm5109_k.gif">)间隔,使每个间隔最多包含<我mg src="https://dl.acm.org/cms/attachment/1d46f8a1-3394-4426-a6d8-985648e12739/cacm5109_f.gif" border="0" hspace="2" alt="cacm5109_f.gif">节点。这些<我>O我>(<我mg src="https://dl.acm.org/cms/attachment/2a44ee7a-a47a-42e2-af9a-e721803c5504/cacm5109_k.gif" border="0" hspace="2" alt="cacm5109_k.gif">)元素递归地发送回创建组的节点<我>v我>属于。在接收到<我>O我>(<我>D我>)元素<我>O我>(<我mg src="https://dl.acm.org/cms/attachment/2a44ee7a-a47a-42e2-af9a-e721803c5504/cacm5109_k.gif" border="0" hspace="2" alt="cacm5109_k.gif">)组,并计算每个间隔中的节点数,根可以启动阶段<我>我我>+ 1<我>n我>(i + 1)我><<我>n我>(我)我>/<我>O我>(<我mg src="https://dl.acm.org/cms/attachment/2a44ee7a-a47a-42e2-af9a-e721803c5504/cacm5109_k.gif" border="0" hspace="2" alt="cacm5109_k.gif">).
假设候选人的数量减少了一倍<我>O我>(<我mg src="https://dl.acm.org/cms/attachment/2a44ee7a-a47a-42e2-af9a-e721803c5504/cacm5109_k.gif" border="0" hspace="2" alt="cacm5109_k.gif">)时,可以得出相的数量是有界的<我>O我>(日志<年代ub>D我>n我>).可以看出每个阶段的成本<我>O我>(<我>D我>日志<年代ub>D我>n我>)时间,证明了时间复杂度的下界。
定理4.2。<我>在直径为D >= 2的n个节点连通图中,算法a的时间复杂度我>依据我>是我>.
在本节中,我们概述如何证明的时间下界<我>通用的我>这表明了第4.1节的简单随机化算法在寻找秩元素时的时间复杂度<我>k我>对A的大多数值渐近最优;如果选择算法没有利用元素空间的结构(除了使用所有元素的全局顺序这一事实外),那么我们将其称为泛型算法。形式上,这意味着只有通过比较函数才能访问元素空间的结构。同样地,我们可以假设分配给节点的所有元素都是固定的,但属于不同节点的元素的顺序是由对手决定的,最初节点不知道。对于下界,我们使用了一个更简单的同步通信模型,将时间分为几轮,每轮每个节点都可以向每个邻居发送消息。注意,由于同步模型比异步模型有更严格的限制,因此同步模型的下界会直接传递给异步模型。我们证明,如果在任何轮中只有一个元素可以通过任何边,这样的算法至少需要W(<我>D我>日志<年代ub>D我>n我>),以合理的概率求中值。
将下界推广到求秩的元素<我>k我>对于任意的<我>k我>{1,…,<我>n我>}是直接的。我们可以假设<我>k n / 2我>因为求秩的元素<我>k我>等于找到秩的元素<我>n我>+ 1<我>k我>相对于全局逆序。我们现在可以告诉算法除了第一名以外的所有人的排名<我>2 k我>元素(额外的信息不会使问题变得更难)。现在问题变成了求中值<我>2 k我>元素。
让我们先来概述一下我们的证明策略。下界的证明分为两步。我们首先考虑两个节点之间的协议,其中每个节点从一半的元素开始。假设两个节点可以互相发送最多包含内容的消息<我>B > =我>每一轮有1个元素W(日志<年代ub>B我>n我>)需要轮来找到中位数。在第二步中,我们通过约简的方法得到一般图的期望下界:我们构造一个图<我>G (D)我>对于每一个直径<我>D > =我>3 . such…<我>T我>整数中值算法<我>G (D)我>能不能变成一个<我>T我>/(<我>D我>2)轮双方协议,两个节点必须通信<我>D我>每个消息包含2个元素。
因此,我们从研究两个节点之间的协议开始<我>u我>而且<我>v我>这样<我>u我>而且<我>v我>每个人都有<我>N我>> = 1的元素<我>u我>0年代ub><<我>u我>1年代ub><……<<我>u我>n - 1我>而且<我>v我>0年代ub><<我>v我>1年代ub><……<<我>v我>n - 1我>分别,其中<是我们要查找中值的全局顺序。我们表示元素的集合<我>u我>而且<我>v我>通过<我>年代我>u我>而且<我>年代我>v我>,分别。每个消息<我>M = (s, x)我>进一步假设两个节点之间包含一个集合<我>年代我>最多的<我>B我>元素和一些任意的附加信息<我>X我>.假设<我>米我>是来自<我>u我>来<我>v。我>在这种情况下,<我>X我>可以是所有元素之间的比较结果可以计算出来的东西吗<我>u我>已经看到的,以及所有的附加信息<我>u我>已收到。唯一的限制<我>X我>它不能用来传输关于不在中的元素的值的信息吗<我>年代我>或者在之前的信息中。我们称之为协议<我>u我>而且<我>v我>它只发送表单=<我>(年代,X)我>如上所述,通用的两方协议。
总体思路如下。我们定义<我>N我>不同的分区,每个分区分配N (2<我>N我>元素<我>u我>,另一个<我>N我>元素<我>v我>(例如,<我>N我>元素之间的不同顺序<我>年代我>u我>而且<我>年代我>v我>),以这样的方式,每个分区导致不同的中位数元素。我们选择作为输入之一<我>N我>均匀随机划分。为了计算中值,我们必须找出哪个<我>N我>分区被选中。我们证明,在每一轮通信中,减少可能分区数目的概率大于一个因子lB在l.
为了简单起见,假设<我>N我> =2<年代up>l年代up>是2的幂。让<我>X我>0年代ub>、……<我>X我>l - 1我>伯努利(1/2)<我>l我>独立的伯努利变量,也就是所有<我>X我>我我>以相等的概率取值0或1。2的分划<我>N我>元素中<我>u我>而且<我>v我>是由<我>X我>0年代ub>、……<我>X我>l - 1我>.如果<我>X我>l - 1我>= 0,<我>N我>2中的最小的<我>N我>元素赋值为<我>u我>和<我>N我>/2个最大的元素被赋值<我>v我>.如果<我>X我>l - 1我>= 1,则正好相反。同理,的价值<我>X我>l2我>确定最小和最大的赋值<我>N我>/4的剩余元素:If<我>X我>l2我>= 0,<我>u我>获取带有rank的元素<我>N我>/ 2 + 1,……3<我>N我>/ 4和<我>v我>获取秩为5的元素<我>N我>/ 4 + 1,……3<我>N我>/2在所有2中<我>N我>元素。同样,根据的值递归地分配其余元素<我>X我>l - 3我>、……<我>X我>0年代ub>只有两个有秩的元素<我>N我>而且<我>N我>+ 1(即两个中值元素)仍然存在。带秩的元素<我>N我>被分配给<我>u我>还有带秩的元素<我>N +我>1被分配给<我>v。我>图3一个>说明所描述的过程。
考虑以下两个要素<我>u我>一个*年代ub>而且<我>V我>b*年代ub>与排名<我>N我>而且<我>N我>+ 1,令一个*和b*是元素的秩<我>N我>而且<我>N我>在集合中+ 1<我>年代我>u我>而且<我>年代我>v我>.我们认为中位数问题只要两者之一就能得到解决<我>u我>知道一个*或<我>v我>知道b*。元素的划分方式是随机变量<我>X我>我我>直接确定以2为底的一个*和b*。如果<我>X我>0年代ub>的位表示的最高有效位= 0一个*为1,而位表示的最高有效位为b* = 0。如果<我>X我>0年代ub> =1,的最有效位一个*为0,且为b*是1。以2为底的表示的其他位一个*和b*的确定类似于:If<我>X我>我我>= 0, (<我>我我>+ 1)<我>圣我>-最重要的一点一个*为1,且(<我>我我>+ l)<我>圣我>-最重要的一点b*为0,反之亦然<我>X我>我年代ub> =1。考虑两个任意元素<我>u我>一个年代我>u我>而且<我>V我>b年代我>v我>与排名一个而且b在两组内<我>年代我>u我>而且<我>年代我>v我>,分别。比较的结果<我>u我>一个而且<我>V我>β;年代ub>(即,是否<我>u我>一个<<我>V我>b或<我>V我>b<<我>u我>一个)由第一个变量决定<我>X我>我我>它等于以2为底的矩阵中对应的位<我>u我>一个或者与以2为底的情况下对应的位不同<我>V我>b先不管发生。如果<我>X我>我年代ub> =0,我们有这个<我>u我>一个<<我>V我>b否则<我>V我>b<<我>u我>一个.
很明显,<我>u我>而且<我>v我>只能了解一个*和b*通过比较它们自己的元素和从其他节点接收到的元素,以及节点发送给彼此的附加信息。考虑一个通用的两方算法<我>一个我>计算中值。假定在一定时间后执行<我>一个,你我>一个1年代ub>、……<我>u我>w这些元素<我>u我>已经发送到<我>v我>而且<我>u我>b1年代ub>、……<我>u我>b年代我>这些元素<我>v我>已经发送到<我>u。我>让<我>我我>是某个元素的最大索引<我>u我>bj年代ub>因为第一个<我>我我>位与对应的变量不同<我>X我>我我>或者有一个元素<我>V我>bj我>因为第一个<我>我我>比特等于相应的变量<我>X我>我我>.由上述观察,中元素之间的任何比较<我>年代我>u我>还有一个元素<我>v我>已经发送到<我>u我>中的元素之间的比较<我>年代我>v我>还有一个元素<我>u我>已经发送到<我>v我>是由<我>X我>0年代ub>、……<我>X我>我+ 1年代ub>.直观地说,<我>u我>而且<我>v我>的值的任何信息<我>X我>我+ 2年代ub>、……<我>X我>l - 1我>.因此,<我>u我>而且<我>v我>必须通过互相发送正确的元素来猜测剩余的部分。由此可以看出,猜测的概率至少为x每一轮正确的比特数最多为2<我>B我>/ 2<年代up>x.每轮新学习的比特数可以由独立的随机变量来上界。使用chernoff类型的参数,可以显示该日志<年代ub>8 b年代ub>(N) / C我>所有这些都需要查房来了解<我>l我>位<我>X我>0年代ub>…,<我>X我>l - 1我>至少有可能<我mg src="https://dl.acm.org/cms/attachment/6fd759a9-a0d6-4c77-8ccf-4b1a3e3b6115/cacm5109_h.gif" border="0" hspace="2" alt="cacm5109_h.gif">暗示了下面的定理。
定理5.1。<我>每一个,随机的,通用的两方协议来找到中位数的需求我>W(日志<年代ub>2<我>B我>N我>)<我>轮数是预期的,至少是概率的我>11 /<我>N我>d对于每一个常数d< 1/2。我>
基于双方协议的下界,我们可以证明一般图上泛型选择算法的下界。在下面的图中,我们假设图的每个节点<我>n我>节点从一个元素开始,我们要找到<我>k我>th我>最小的<我>n我>元素。在每一轮中,每个节点可以向它的每个邻居发送一个元素。对于每一个<我>n我>> =<我>D我>>= 3,我们构造一个图<我>G我>(<我>D我>),<我>n我>节点和直径<我>D我>这样我们就可以把找到中位数的问题通过两方协议简化为找到秩元素的问题<我>k我>在<我>G我>(<我>D我>).
我们首先描述一个下界W(<我>D我>日志<年代ub>D我>,<我>n我>)求中值,然后推广到求任意秩的元素<我>k我>.为了简单起见,假设<我>n我>D我>是一个奇数。让<我>N我> =(<我>n我>D我>+ 1) / 2。我们考虑这个图<我>G我>(<我>D我>)定义如下<我>G我>(<我>D我>)包含两个节点<我>u我>而且<我>v我>它们由一条有长度的路径连接<我>D我>2(即,它包含<我>D我>1节点)。此外,还有节点<我>u我>1年代ub>、……<我>u我>N我>而且<我>V我>1年代ub>、……<我>V我>N我>这样<我>u我>我我>,连接到<我>u我>而且<我>v我>我年代ub>,连接到<我>v我>对所有<我>我我>{1,…,<我>N我>}。我们当然可以这样假设<我>n我>=w(<我>D我>),因为W(<我>D我>)是一个微不足道的下界(即使找到最小元素也需要W(<我>D我>)轮)。因此我们可以假设只有叶节点<我>u我>我我>.而且<我>v我>我我>为<我>我我>{1,…,<我>N我>}中包含一个元素,我们需要找到这两个元素的中值<我>N我>元素。我们可以简单地将虚拟元素分配给所有其他节点,使全局中值等于叶元素的中值。因为只有叶节点从一个元素开始,我们可以假设在第一轮中,所有的叶节点<我>u我>t我>将它们的元素发送到<我>u我>和所有的叶子<我>v我>我我>将它们的元素发送到<我>v我>,因为这是第一轮中唯一可能有用的交流。这样,问题就变成了<我>k我>th我>2的最小元素<我>N我>长度路径上的元素<我>D2我>如果最初是两个结束节点中的每一个<我>u我>而且<我>v我>路径的<我>N我>元素。的叶节点<我>G我>(<我>D我>)不需要进一步参与分布式选择协议,因为<我>u我>而且<我>v我>知道它们各自叶子所知道的一切,并能局部模拟它们叶子节点的所有动作。
假设我们给出了一个算法<我>一个我>它找到上的中值<我>G我>(<我>D我>)时间<我>T我>+ 1。我们概述了如何构造一个两方协议<我>一个“我>它最多发送<我>D我>每条信息包含2个元素,并找出时间的中位数[<我>T我>/(<我>D我>2)]W(日志<年代ub>D我>N我>)的下界<我>一个我>'暗示着<我>T我>=W(<我>D我>日志<年代ub>D我>N我>).因为信息至少需要<我>D我>从…出发<我>u我>来<我>v我>反之亦然<我>u我>而且<我>v我>能进行整数计算<我>t我>(即收到来自圆的消息后<我>t我>1)函数是将自己的元素和其他节点的消息内容四舍五入<我>t我>- (<我>D我>例如,2)。<我>u我>第一个的留言<我>D我>2轮只靠<我>年代我>n我>,传讯<我>D我>1,…2 (<我>D我>-2)可以从<我>年代我>u我>而且<我>v我>的信息在第一<我>D我>2回合,以此类推。获取两方协议<我>一个我>“从<我>一个我>,我们可以这样进行。在第一轮<我>一个我>”,<我>u我>而且<我>v我>发送他们的第一个消息<我>D我>2轮的<我>一个我>的相互关系。现在,<我>u我>而且<我>v我>两者都可以本地模拟第一个的所有通信吗<我>D我>2轮的<我>一个我>.这允许计算下一个消息<我>D我>2轮的<我>一个我>.总的来说,在圆<我>r我>两方协议的<我>一个我>”,<我>u我>而且<我>v我>可以互相发送发牌信息(<我>r我>1) (<我>D我>2) + 1……<我>r我>(<我>D我>2)的<我>一个我>并能随后局部模拟各自的回合<我>一个我>.的时间复杂度<我>一个“我>就变成了(<我>T我>/(<我>D我>2)]。
定理5.2。<我>对于每n个>= D >= 3,就有一个n个节点、直径D的图G(D),使每个可能随机化的泛型算法都能找到k我>th我>最小的元素要求W(D我>日志<年代ub>D我>最小值<我>{k, nk})轮的期望和概率至少我>11 /(分钟<我>{k, nk}我>)<年代up>d对于每一个常数d< 1/2。特别是,找到中位数需要至少W(<我>D我>日志<年代ub>D我>n)轮。我>
类似的证明技术也被用于复杂通信领域,人们试图找到解决某个通信问题所需传输的总比特数的界限。<年代up>22一个>特别是,<年代up>21一个>引入一种模拟技术来在路径和更通用的图中运行两方协议,以便将两个节点之间的计算下限扩展到更通用的拓扑上的计算。与通信复杂性相比,我们的重点是最小化通信轮数,而不是最小化传输比特数。
在本文中,我们研究了<我>k我>-选择问题,一个突出的数据聚合问题,并证明了其(时间)复杂度的上界和下界。我们的结果以一种完全抽象的方式呈现,也就是说,我们的算法在真实网络中对聚合函数的性能有显著的影响,从而证明在实际应用中是有意义的。显然,在应用程序领域中简单地植入分布式算法通常是不可能的,因为需要尊重应用程序施加的额外约束。例如,在无线传感器网络中,聚合需要坚持无线信道特性。我们相信,我们的工作能够进一步阐明可实现的综合速度和能力<年代up>10一个>,<一个href="#R11">11一个>在无线网络中,或与其他数据收集算法相结合,例如,<年代up>5一个>,<一个href="#R6">6一个>甚至可以为各种应用程序域提供基本的聚合功能。我们希望我们的研究结果和技术最终可以应用到多个应用领域,为流数据库或多核架构等提供聚合支持。
我们要感谢Pascal von Rickenbach和Roland Flury对插图的帮助。此外,我们要感谢Hagit Attiya提供了宝贵的反馈,这极大地帮助了我们改进了本文,也让我们有时间写了一个技术观点。
本文的原始版本题为“分布式选择的紧边界”,可以在<我>第十九届美国计算机学会并行算法与架构研讨会论文集我>(加州圣地亚哥,2007年6月)。
1.布鲁姆,M.,弗洛伊德,r.w .,普拉特,V,里维斯特,r.l和塔扬,r.e .选择的时间范围。<我>计算机与系统科学杂志。我>7:448461, 1973年。
2.Burri, N., von Rickenbach, P.和Wattenhofer, R. Dozer。传感器网络的超低功耗数据采集。在<我>国际传感器网络信息处理会议(IPSN)我>, 2007年
3.陈凤莲,丁鸿飞。一种分布求中值的改进算法。<我>Algorithmica。我>2:7786, 1987年。
4.分布式网络中选择的折衷。在<我>第二届ACM分布式计算原理年会论文集我>,第154160页,1983。
5.Goel, A.和Estrin, D.凹成本的同时优化:单个汇聚合或单个来源批量购买。<我>Algorithmica我>43 (l2): 515年,2005年。
6.Jia, L, Lin, G, Noubir, G, Rajaraman, R.和Sundaram, R. TSP的通用近似,斯坦纳树,和集合覆盖。在<我>第37届ACM计算理论年会(STOC)我>,第386395页,2005年。
7.肯普博士、多布拉博士和格尔克J.基于流言的综合信息计算。在<我>第44届IEEE计算机科学基础年会论文集我>,2003年。
8.Madden, S., Franklin, m.j., Hellerstein, j.m.和Hong, W. TAG:一种用于自组织传感器网络的小型聚合服务。在<我>第五届操作系统设计与实现年会论文集(OSDI)我>, 131146年,2002页。
9.Marberg, J. M.和Gafini, E.分布式集合中选择的最优呼喊-回声算法。在<我>第23届阿勒顿通信、控制和计算会议论文集我>, 1985年。
10.Moscibroda, T.无线传感器网络的最坏情况容量。在<我>第六届传感器网络信息处理国际会议(IPSN)我>, 2007年。
11.Moscibroda, T.和Wattenhofer, R.无线网络连接的复杂性。在<我>第25届IEEE计算机与通信学会年会(INFOCOM)我>, 2006年。
12.Negro, A., Santoro, N., and Urrutia, J.有界信息的高效分布选择。<我>并行与分布式系统学报。我>397401(4): 1997。
13.关于传感器网络中高效聚合查询的说明。在<我>第23届美国计算机学会(ACM)原则年会论文集我>分布式计算(PODC)我>, 283289年,2004页。
14.法勒,D。<我>分布式计算:位置敏感方法。我>离散数学及其应用,2000。
15.Rodeh, m,找到分配的中值。<我>计算机与系统科学杂志我>24(2): 162166。1982.
16.Rodem, D., Santoro, N.和Sidney, J.在分布式文件中大喊-回声选择。<我>网络。我>16:235249, 1986年。
17.桑托罗,舒特佐,M.,和西德尼,J. B.关于分布式选择的预期复杂性。<我>并行与分布式计算杂志我>5(2): 194203年,1988年。
18.Santoro, N., Sidney, J. B.和Sidney, S. J.一种分布式选择算法及其期望通信复杂度。<我>理论计算机科学。我>100(1): 185204、1992。
19.Schönhage, A., Paterson, m.s.和Pippenger, N.找到中位数。<我>计算机与系统科学杂志我>, 1976年13:184199。
20.Shrira, L, Francez, N.和Rodeh。M.分布式k-选择:从序列算法到分布式算法。在<我>第二届ACM分布式计算原理年会论文集我>,第143153页,1983年。
21.分布式计算机网络中通信复杂性的下界。<我>美国计算机学会学报(JACM)。我>34(4): 921、1987。
22.关于分布式计算的一些复杂性问题。在<我>计算机学会计算理论年会论文集(STOC)我>, 209年,1979页。
23.姚,Y, Gehrke, J.基于Cougar的传感器网络内查询处理方法。<我>ACM SIGMOD记录我>31(3): 918年,2002年。
24.Zhao, J., Govindan, R.和Estrin, D.用于监测无线传感器网络的计算聚合。在<我>第一届IEEE传感器网络协议与应用国际研讨会(SNPA)论文集我>,2003年。
费边库恩(kuhn@inf.ethz.ch)瑞士苏黎世联邦理工学院理论计算机研究所博士后研究员
托马斯•洛克(lochert@tik.ee.ethz.ch博士研究生,计算机工程与网络实验室,苏黎世联邦理工学院,瑞士
罗杰Wattenhofer(wattenhofer@tik.ee.ethz.ch)教授,瑞士苏黎世联邦理工学院计算机工程与网络实验室分布式计算组组长
a.我们鼓励读者思考一个自然的聚合(单值结果)查询,它不能由分布函数、代数函数和整体函数的组合来表述。
b.我们的结果很容易推广到每个节点存储多个元素的情况。然后用元素的数量来表示时间的复杂性<我>N >我>而不是节点数。
DOI: http://doi.acm.org/10.1145/1378727.1378749
图1。传感器网络中的数据在预先计算的虚拟生成树上聚合。通常,节点从其子节点接收数据,并将聚合结果转发给树中的父节点。
图2。根据算法对直径为12、包含24个节点的样例树进行分割<我>一个我>▽年代up>分成4组,每组最多7个节点。
图3。2<我>N我>将减去两个中位数的元素赋值给<我>u我>而且<我>v我>根据<我>l我> =日志<我>n我>独立的伯努利方程的变量<我>X我>0年代ub>、……<我>X我>l - 1我>.两个中值之一被分配给<我>u我>另一个是<我>v我>.为了求中位数,<我>u我>而且<我>v我>必须计算的值<我>X我>0年代ub>、……<我>X我>l - 1我>.
©2008 acm 0001-0782/08/0900 $5.00
允许制作本作品的全部或部分的数字或硬拷贝用于个人或课堂使用,但前提是该拷贝不是为了盈利或商业利益而制作或分发,并且该拷贝在第一页上带有本通知和完整引用。以其他方式复制、重新发布、在服务器上发布或重新分发到列表,需要事先获得特定的许可和/或付费。
数字图书馆是由计算机协会出版的。版权所有©2008 ACM有限公司
没有发现记录