[分布式算法] 生成树广播与敛播

复杂度

首先需要了解分布式算法的复杂度概念
(1) 消息复杂度: 算法在所有容许的执行上发送msg总数的最大值(包括同步和异步系统)
(2) 时间复杂度:
①同步系统：最大轮数，即算法的任何容许执行直到终止的最大轮数。
②异步系统：假设：①节点计算任何有限数目事件的时间为0； ②一条消息发送和接收之间的时间至多为1个时间单位，定义为：所有计时容许执行中直到终止的最大时间。
(3) 空间复杂度
(4) 性能衡量：最坏性能、期望性能

消息复杂度

消息的延迟
发送msg的计算事件和处理该msg的计算事件之间所逝去的时间, 主要由msg在发送者的outbuf中的等待时间和在接收者的inbuf中的等待时间所构成

时间复杂度

定义中，每个msg延时至多为1，但实际中，至多1个时间单位会很难计算，因此修改假设：
①一条消息发送和接收之间时间恰好为1个时间单位
②一条消息发送和接收之间时间介于α和1之间(0< α<1)
③假设消息传递的延迟满足某种概率分布，并以此计算

生成树广播

信息收集（敛播/汇集）及分发(广播)是许多分布式算法的基础
由于分布式系统中，每个节点并不知道全局拓扑状态，但某些算法需要在特定的结构下才能达到最优。例如：广播/敛播在树结构下才能达到消息复杂度最优，因此构造生成树是必要的，且是其他算法的基础。
假定网络的生成树已给定。某处理器pr希望将消息M发送至其余处理器。假定生成树的根为pr ，每个处理器有一个信道连接其双亲(pr除外)，有若干个信道连接其孩子。

广播算法

pr: if(i=r): //初始广播节点。假设初始化时M已在传输状态
1. upon receiving no msg: //pr发送M后执行终止
2. 	terminate; //将terminated置为true。 
3. pi(i≠r,0 ≤ i ≤ n-1):
4. 	upon receiving M from parent:
5. 		send M to all children;
6. 		terminate;
1
2
3
4
5
6
7

Msg复杂度: 无论在同步还是异步模型中，msg M在生成树的每条边上恰好发送一次。
因此，msg复杂性为n-1，即O(n)。
时间复杂度为O(h)，其中h为生成树的高度。

生成树敛播

与广播问题相反，汇集是从所有结点收集信息至根。为简单起见，先考虑一个特殊的变种问题：
假定每个pi开始时有一初值xi，我们希望将这些值中最大者发送至根pr。

算法思想
每个叶子结点$pi$发送$xi$至双亲。//启动者
对每个非叶结点$pj$，设$pj$有$k$个孩子$p{i}_1,\dots ,p{i}_k$，$pj$等待$k$个孩子的msg $v{i}_1,v{i}_2,\dots ,v{i}_k$，当$pj$收到所有孩子的msg之后将 v j = m a x { x j , v i 1 , … , v i k } vj=max\{xj,vi_1,…,vi_k\} vj=max{xj,vi1​,…,vik​}发送到$pj$的双亲。

小结
广播和敛播算法用途：初始化某一信息请求(广播发布)，然后用敛播响应信息至根