检测网站死链,自媒体wordpress主题,邢路桥建设总公司网站,长春网站只长春网站制作做参考文献Self-stabilizing systems in spite of distributed control可以把松散耦合的 循环序列过程 间的同步任务#xff0c;看成是要保持一个这样的不变性#xff1a;“系统要处于一种合法状态”因此每个进程在运行每一个可能会改变不变性的步骤之前都要先检查一下是可以执…参考文献Self-stabilizing systems in spite of distributed control可以把松散耦合的 循环序列过程 间的同步任务看成是要保持一个这样的不变性“系统要处于一种合法状态”因此每个进程在运行每一个可能会改变不变性的步骤之前都要先检查一下是可以执行还是要延迟执行如果允许不同进程互斥地访问记录有“当前系统状态”的公共存储解决方案就很简洁—并且可以很系统化地实现如果没有一个所有进程都可以访问的公共存储模块的话复杂度就会增加因为当前系统的状态就不得不分布式地存储在各个进程内的变量中进一步地如果再对通信进行限定比如每个进程只能与它的邻居进行通信复杂度还会上升问题的复杂性在于单个进程的状态只能被整个系统状态中对它可用的那一部分影响而进程本地动作要基于本地信息实现全局性的目标这样的系统(可以称之为“分布式控制”系统)已经被设计出来但是当时所知的所有设计都不是“自稳定”的也就是说它们一旦进入非法状态就会永远处于这种状态考虑一个由少数边连接的图图中每个节点对应一个有限状态机图中直接相连的那些状态机它们相互之间称为邻居每个状态机定义一个或多个特权比如是关于它自己和邻居状态的一组布尔函数当布尔函数值为 true 时我们就认为对应的特权“存在”我们引入一个中央守护进程采用中央守护进程只是为了方便说明实际上可以采用一个分布式的 守护进程 来完成具体算法本文没有涉及一个简单的观察是如果享有 特权 的是不相邻的状态机它们的转换是可以并行进行的它们不需要同步因为并行运行的结果与通过一个中央守护进程选择一个进行执行是一致的因为选择一个执行之后由于它们两个不相邻因此另一个的邻居状态不会改变在新的状态中另一个依然是享有特权者下一次可以继续选择它而相邻的实际上因为可以相互通信它们自己可以协调到底是谁进行状态转换在下面的状态转换手动演练中实际上我们就充当了中央守护进程的角色在有多个 特权 存在的情况下选择其中一个进行状态转换通过它从“存在”的 特权 中选择一个进行状态转换每个合法状态中可能有多个特权“存在”所以需要从里面选择一个进行状态转换允许多个享有特权者是一种更通用的需求只有一个享有特权者的情况是互斥锁而多个则可以类比信号量拥有该被选定的 特权 的状态机可以进行状态转换—根据一个以它的老状态和邻居状态为输入的状态函数进入新状态对于不止有一个 特权“存在”的状态机来说新状态可能还依赖于被选定的特权状态转换完成后守护进程再选择一个新的特权可以通过如下全局规则判断系统是否处于合法状态要求 1. 每个合法状态必须至少要有一个 特权“存在” 2. 在合法状态的每一个执行步骤都要确保系统还是会处于合法状态 3. 每个 特权 至少出现在一个合法状态中 4. 对于任意两个合法状态来说总是可以通过一定执行步骤从一个到达另一个我们称一个系统是“自稳定”的当且仅当无论系统初始状态如何也无论每次为下一个执行步骤选定的 特权 是谁可以保证在有限数目的执行步骤之后总是至少存在一个 特权 并且系统可以发现它自己处于合法状态“自稳定”的系统是否能通过各节点的本地执行步骤来满足上述的全局性条件本来也不是可以很直接地得出结论而守护进程的不确定性引入了额外的复杂度实际上该问题可以通过如下三个方案解决在如下三个解决方案中我们假设有 N1 个进程它们以 0…N 进行编号假设当前机器编号为 nr.iL代表机器的左邻居的状态对应的机器编号为 nr.(i-1) mod (N1)S代表当前机器自己的状态编号为 nr.iR代表机器的右邻居的状态对应的机器编号为 nr.(i1) mod (N1)换句话说我们假设机器是像环一样连接在一块机器 nr.0 又称为“底部机器”机器 nr.N 则又被称为“顶部机器”同时在这里我们将那些只有一个 特权“存在”的状态作为合法状态同时所有的方案描述均采用了如下格式“if privilege then corresponding move fi” 如果有特权那么就进行相应的操作Solution with K-state Machines (KN)每个机器的状态由一个整数 S 表示并且0SK对于每个机器来说只定义一个 特权具体如下对于底部机器来说if L S then S : (S1)mod K fi对于其他机器来说if L ! S then S : L fi说明 1对于一个中央式的守护进程来说KN 就可以了说明 2C.S.Scholten 扩展了该解决方案使之可以应用到任意网络结构根据格式“if privilege then corresponding move fi”我们可以看出在上面的解决方案中对于 底部机器 来说 LS 就是 特权意味着如果 LS 它就是享有特权者对于其他机器来说 L!S 就是 特权意味着如果 L!S 它就是享有特权者我们可以以 3 个状态机为例令 K4根据上面的算法进行模拟运行可以发现即使一开始不满足有一个特权者执行一段时间后会进入只有一个特权者的状态并且此后一直处于只有一个特权者的状态比如如下状态转换序列如下数组中的值分别代表编号为 0,1,2 的状态机的状态值[0, 1, 2] - [0, 0, 2] - [0, 0, 0] - [1, 0, 0] - [1, 1, 0] - [1, 1, 1] - [2, 1, 1] - [2, 2, 1] - [2, 2, 2]……如上初始状态状态机 0,1,2 对应的 S 值为[0, 1, 2]根据方案描述 对于状态 1 来说状态值是 1左右值分别是 0 和 2因此满足 L!S所以此时状态机 1 享有特权 对于状态机 2 来说状态值是 2左右值分别是 1 和 0因此也满足 L!S因此它也是享有特权者 对于 0 来说要看 L 是否等于 S由于 0 的左右值是 2和 1因此它不享有特权可以看到这个初始状态有两个享有特权者不满足上面关于合法状态中只有一个特权者的定义然后我们根据状态转换函数从初始状态开始不断进行状态转换可以看到到了[0, 0, 0]后变成了只有状态机 0为特权者而此后就一直处于只有一个享有特权者的状态可以看到整个过程中就是从初始处于非法状态然后经过一定步骤进入了合法状态此后就一直处于合法状态而这个过程中进程只看了它左右邻居的状态通过局部信息就实现了只有一个享有特权者这一全局性需求这实际上说明了在分布式系统中我们仅通过部分节点的局部信息不需要得到全局状态就可以实现全局性的状态要求其他两个方案代表的含义与上述解决方案类似有个区别是状态机定义了两个特权以第三个方案为例我们再手动模拟一个状态转换过程假设有 4 个状态机它们的初始状态值分别为[0,1,2,0]按照下面的算法描述可以得到如下一个状态转换过程[0,1,2,0] 此时 0,1,2 均为享有特权者选择 0 进行状态转换[2,1,2,0] 此时 1,2 为享有特权者选择 1 进行状态转换[2,2,2,0] 此时 2,3 为享有特权者选择 2 进行状态转换[2,2,0,0] 此时 1 为享有特权者1 进行状态转换[2,0,0,0] 此时 0 为享有特权者0 进行状态转换……可以看到依然是初始不合法然后一定步骤后变成合法之后一直合法方案 3 具体算法如下 上述三个解决方案说明对于一个分布式系统来言即使节点只能跟所有节点中的部分节点进行通信对于上述特权者(互斥任意时刻只有一个特权者)问题而言存在一个“自稳定”的算法无论系统初始状态如何经历一定步骤之后它都可以进入合法状态“自稳定”属性使得分布式算法可以从暂态错误中恢复Dijskstra 在论文中提出了“自稳定”概念并以上述“令牌环”问题为例给出了相应的自稳定算法在“令牌环”场景下计算机网络连接成环状每个计算机可以获取它前面的那个计算机的状态该状态可以显示该计算机“持有令牌”还是“不持有令牌”对应的算法要满足如下两个条件1.任意时刻只有一个计算机持有令牌2.持有令牌的计算机会将令牌传给它后面的计算机最终该令牌可以在环上循环流转不持有令牌对于单个计算机来说是合法的但是如果所有计算机都不持有令牌对于整个系统来说就是非法的类似的如果有不止一个计算机持有令牌也是非法的但是对于每个计算机来说这很难发现因为他们每个都只能与邻居通信因此论文中的算法并没有去检测错误而是确保系统不断向着合法状态前进而且那个时候用于错误检测的传统方法很困难而且很耗时但是随着新的更高效的错误检测算法的提出基于错误检测还可以将非自稳定算法结合自稳定算法实现更高效的自稳定算法
