我的新博客地址

http://blog.163.com/sukerl@126/

1、进程的输入都是从一个特定的集合V开始的。所有的无故障进程都被要求从同一个值集合V中产生输出，并符合简单的一致性和有效性条件。

2、通常被用于容错的冗余多处理器系统中。其中少数处理器执行相同的计算，就每一步的结果达成一致。

3、floodset算法:

每个进程都有一个变量W,它包含V的一个子集。开始时,进程i的变量W只包含了i的初始值。在f+1轮中的每一轮，每个进程都广播W，然后把所接收到的元素加到W中。

在f+1轮后，进程i使用下面的决定规则。如果w是一个单元素集合，那么i就决定出W中的惟一元素；否则i就决定出默认值V0。

4、进程就像floodset算法一样操作，只是每个进程i最多广播2个值。第一次广播发生在第1轮，每个进程i都广播自己的初始值。第二次广播发生在第r轮，2<=r<=f+1，其中在第r轮的开始，i知道某个v的值和自己的初始值不同，那么i就广播这个新值V0

1、每个进程从0级开始，当它收到其他所有进程的消息后，就进入等级1，当它知道所有其他的进程都已经到了1，就进入2。

2、使用同步模型，允许任意数量的消息在运行过程中丢失。让进程通过把特定决定状态组件设置为0或1，最终输出一个在{0,1}中的决定。进程所做的决定必须满足三个条件：
1）一致性：没有两个进程决定出不同的值
2）有效性：
如果所有进程都以0开始，那么0就是惟一可能的决定值。
如果所有进程都以1开始，而且所有消息都被传递，那么1就是惟一可能的决定值。
3）终止性：所有进程最后都会做出决定。
3、随机攻击算法
   每个进程i根据在运行中产生的通信模式，都明确地把它的级别保存在变量level中。进程1从[1,r]的整数中选择一个随机的key值，这个值附于所有消息中。另外，所有进程的初值也附于所有消息中。
   在r轮之后，如果每个进程计算出来的level值不少于key,且它知道所有进程的初值都是1，那么它决定出1。

1、在每个阶段中，每个进程i按均匀分布在范围{1,...,n^4}中随机选择一个整数vali。一旦进程选择了这些值，我们就定义I'由所有任为局部winner的节点i组成，也就是在i的所有的邻接节点j中，vali>valj。n^4使得每个进程i以高概率选择不同的值

2、算法分阶段进行

1）在一个阶段的第一轮中，各个进程都选择它们各自的val，并把它们发送给自己的邻接节点。到第一轮的最后，当所有的val消息都被接收到时，winner-也就是在I'中的进程-将会知道它们是谁。

2）在第二轮中，winner通知它们的邻接节点。在第二轮的最后，loser-也就是有邻接节点在集合I'中的进程-知道它们是谁。

3）在第三轮中，每个loser通知它的邻接节点，然后所有相关进程-winner和loser的邻接节点-从图中删除合适的节点和边。更精确地说，在这个阶段之后，winner和loser不再参与以后的工作，loser的邻接节点也删除所有与新删除节点相关的边

1、这个算法分层构造各组件。对于每个k ,第k层的各组件构成了一个生成森林，其中k层第一组件都包含一棵树，该树是MST的一个子图。K层的每个组件至少有2^k个节点。在每一层中，每个组件有一个独特的领导者节点。进程允许按一个固定的轮数O(n)来完成每层的工作。

2、算法从0层开始，各组件由单独的节点组成且不包含边。我们归纳地假设k层的各个组件已经确定了（包括它们的领导）。更特别地，假定每个进程都已经知道其组件的领导的领导的UID；这个UID就被用作整个组件的标识符。每个进程也知道它的哪条邻接边在该组件的树中。

3、为了得到K+1层的各个组件，K层的每个组件会沿着其生成树的边搜索组件的MWOE。领导者使用消息广播策略，沿着树的边广播搜索请求。每个进程都在自己的邻接边中找到一条权最小的组件的出向边；它为了完成这个工作，在所有的非树中的边上传递test消息，询问边的另一端点是否属于相同的组件（通过比较组件的标识符来确定）。然后各进程就会把本地最小权边的信息聚播给领导者，途中选择最小的。领导者得到的最小值就是整个组件的MWOE。

4、当K层的各组件都找到它们的MWOE后，这些组件就通过所有的MWOE合并为K+1层的组件。这涉及

每个进程i都记录目前所知的从i0出发的最短距离dist,以及作为入向邻接节点的父节点parent（这个父节点位于i之前，与i之间的路径的权重为dist）。开始时，disti0=0,对于i<>i0，则disti=∞,parent分量没有定义。在每一轮，每个进程都把dist发送给所有的出向邻接节点。然后每个进程通过一个松弛步来更新自己的dist，即在前一步的dist和所有的disti+weightji中取最小值勤，其中j是它的入向邻接点。如果dist改变了，那么它的parent分量也会相应更新。在n-1轮后，dist就包含了最短距离，parent则指向最短路径树中的父节点。

http://www.jin14.com/gaozhong/news/Detail/08/04/02/83_094947747.shtml　 　随着高考的日期越来越近，家长们考虑更多的可能都是孩子未来报考的学校和专业问题。 　　而一提到志愿问题，家长们的着眼点一定会在将来孩子毕业时的就业。 　　现在，有关大学生就业的报道比比皆是。通观下来，好像令人兴奋的利好消息不多。更多的是一些有关就业难和学生求职难的报道。 　　也许，在扩招的历史背景条件下，大学生就业难、求职难是一个不可忽视的问题，但是，在人们讨论这个问题的时候，是否忽视了另外一个方面？ 　　在《大学生》杂志上，看到了这样的发问，觉得有些道理，于是，便顺手摘录如下，希望能给家长以启发…… 　　针对有的大学生抱怨求职难，就业难，某高校的某教授很客观地说：一门课一个学期下来，交一份作业就可以了。这份作业还不知道是不是抄来的。这么多年书读下来，简

在运行中的任一时刻，总有一个进程是被标记的。最初的时候是i0。进程i0在第一轮时向所有出向邻接节点发出一个搜索消息。在每一轮中，如果一个未标记的进程接收到一个搜索消息，就标记它自己，并且从传来搜索消息的进程里选择一个作为父节点。在一个进程被标记之后的第一轮，它向所有的出向邻接节点发送搜索消息。建立了一个BFS树，进行广度优先搜索。

1、有向图来说，如果任意两个节点之间都有路径的话成为强连通图

2、

算法要求进程知道图的直径diam

每个进程保持有一个最大UID的记录(最初是自己的UID).在每轮中,每个进程都要在自己的所有出向边上传播最大的UID.在diam轮后,如果得到的最大值是进程自己的UID,那么进程就把自己选为领导者,否则就成为非领导者。

这个算法可以优化为进程只在它们初次知道max-uid时发送消息. 不是每轮都发送

    在阶段1,2,...中进行计算，每一个都由n个连续的轮组成。每个阶段都有一个携带着特殊UID的令牌一直在个环中流转。更特别地，在包含轮(v-1)n+1,...,vn的阶段中，只有带着UID v的令牌才被允许流转。

   如果存在UID为v的进程i，且在(v-1)n+1轮到达之前进程i没有收到任何非空消息，那么进程i就会把自己选举为领导者，并沿着环发送一个包含其UID的令牌。当这个令牌在传递的时候，所有其他进程都接收到它，这样它们就不会选举自己为领导者或在以后的阶段中创建令牌。

  在这个算法中，最小的UID 最终会环绕整个路径，它的原始进程被选举为领导者

  这个算法要求环的大小n所有进程都知道