- 参考文献
- Self-stabilizing systems in spite of distributed control
- 可以把松散耦合的 循环序列过程 间的同步任务，看成是要保持一个这样的不变性：“系统要处于一种合法状态”
- 因此每个进程在运行每一个可能会改变不变性的步骤之前都要先检查一下是可以执行，还是要延迟执行
- 如果允许不同进程互斥地访问记录有“当前系统状态”的公共存储，解决方案就很简洁—并且可以很系统化地实现
- 如果没有一个所有进程都可以访问的公共存储模块的话，复杂度就会增加，因为当前系统的状态就不得不分布式地存储在各个进程内的变量中；
- 进一步地，如果再对通信进行限定，比如每个进程只能与它的邻居进行通信，复杂度还会上升
- 问题的复杂性在于单个进程的状态只能被整个系统状态中对它可用的那一部分影响，而进程本地动作要基于本地信息实现全局性的目标
- 这样的系统(可以称之为“分布式控制”系统)已经被设计出来，但是当时所知的所有设计都不是“自稳定”的，也就是说它们一旦进入非法状态，就会永远处于这种状态
- 考虑一个由少数边连接的图，图中每个节点对应一个有限状态机；
- 图中直接相连的那些状态机，它们相互之间称为邻居
- 每个状态机定义一个或多个"特权"，比如是关于它自己和邻居状态的一组布尔函数；
- 当布尔函数值为 true 时，我们就认为对应的特权“存在”
- 我们引入一个中央守护进程，采用中央守护进程只是为了方便说明，实际上可以采用一个分布式的 守护进程 来完成，具体算法本文没有涉及
- 一个简单的观察是如果享有 特权 的是不相邻的状态机，它们的转换是可以并行进行的，它们不需要同步，因为并行运行的结果与通过一个中央守护进程选择一个进行执行是一致的，因为选择一个执行之后，由于它们两个不相邻，因此另一个的邻居状态不会改变，在新的状态中另一个依然是享有特权者，下一次可以继续选择它，而相邻的实际上因为可以相互通信，它们自己可以协调到底是谁进行状态转换
- 在下面的状态转换手动演练中，实际上我们就充当了中央守护进程的角色，在有多个 特权 存在的情况下，选择其中一个进行状态转换，通过它从“存在”的 特权 中选择一个进行状态转换，每个合法状态中可能有多个特权“存在”，所以需要从里面选择一个进行状态转换
- 允许多个享有特权者是一种更通用的需求，只有一个享有特权者的情况是互斥锁，而多个则可以类比信号量
- 拥有该被选定的 特权 的状态机可以进行状态转换—根据一个以它的老状态和邻居状态为输入的状态函数进入新状态
- 对于不止有一个 特权“存在”的状态机来说，新状态可能还依赖于被选定的特权
- 状态转换完成后，守护进程再选择一个新的特权
- 可以通过如下全局规则判断系统是否处于合法状态
- 要求：
- 1. 每个合法状态，必须至少要有一个 特权“存在”
- 2. 在合法状态的每一个执行步骤都要确保系统还是会处于合法状态
- 3. 每个 特权 至少出现在一个合法状态中
- 4. 对于任意两个合法状态来说，总是可以通过一定执行步骤从一个到达另一个
- 我们称一个系统是“自稳定”的，当且仅当无论系统初始状态如何也无论每次为下一个执行步骤选定的 特权 是谁，可以保证在有限数目的执行步骤之后总是至少存在一个 特权 并且系统可以发现它自己处于合法状态
- “自稳定”的系统是否能通过各节点的本地执行步骤来满足上述的全局性条件，本来也不是可以很直接地得出结论
- 而守护进程的不确定性引入了额外的复杂度
- 实际上该问题可以通过如下三个方案解决：
- 在如下三个解决方案中，我们假设有 N+1 个进程，它们以 0…N 进行编号
- 假设当前机器编号为 nr.i
- L，代表机器的左邻居的状态，对应的机器编号为 nr.(i-1) mod (N+1)
- S，代表当前机器自己的状态，编号为 nr.i
- R，代表机器的右邻居的状态，对应的机器编号为 nr.(i+1) mod (N+1)
- 换句话说，我们假设机器是像环一样连接在一块
- 机器 nr.0 又称为“底部机器”，机器 nr.N 则又被称为“顶部机器”
- 同时在这里我们将那些只有一个 特权“存在”的状态作为合法状态
- 同时所有的方案描述，均采用了如下格式：
- “if privilege then corresponding move fi” 如果有特权，那么就进行相应的操作
- Solution with K-state Machines (K>N)
- 每个机器的状态由一个整数 S 表示，并且0=<S<K
- 对于每个机器来说，只定义一个 特权，具体如下：
- 对于底部机器来说，if L = S then S := (S+1)mod K fi
- 对于其他机器来说，if L != S then S := L fi
- 说明 1：对于一个中央式的守护进程来说，K>=N 就可以了
- 说明 2：C.S.Scholten 扩展了该解决方案，使之可以应用到任意网络结构
- 根据格式“if privilege then corresponding move fi”，我们可以看出，在上面的解决方案中，对于 底部机器 来说 L=S 就是 特权，意味着如果 L=S 它就是享有特权者，对于其他机器来说 L!=S 就是 特权，意味着如果 L!=S 它就是享有特权者
- 我们可以以 3 个状态机为例，令 K=4，根据上面的算法进行模拟运行可以发现，即使一开始不满足有一个特权者，执行一段时间后会进入只有一个特权者的状态，并且此后一直处于只有一个特权者的状态
- 比如如下状态转换序列，如下数组中的值分别代表编号为 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.持有令牌的计算机会将令牌传给它后面的计算机，最终该令牌可以在环上循环流转
- 不持有令牌对于单个计算机来说是合法的，但是如果所有计算机都不持有令牌，对于整个系统来说就是非法的
- 类似的，如果有不止一个计算机持有令牌，也是非法的，但是对于每个计算机来说这很难发现，因为他们每个都只能与邻居通信
- 因此，论文中的算法并没有去检测错误，而是确保系统不断向着合法状态前进
- 而且那个时候用于错误检测的传统方法很困难而且很耗时
- 但是随着新的更高效的错误检测算法的提出，基于错误检测还可以将非自稳定算法结合自稳定算法实现更高效的自稳定算法
论文-分布式-分布式计算|容错-分布式控制下的自稳定系统
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/104720.html
如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！相关文章
轻松批量剪辑：将MP4视频转换为FLV格式
在视频制作和编辑领域，批量剪辑和格式转换是非常常见的操作。将MP4视频转换为FLV格式，可以帮助我们更好地管理和发布视频内容。本文将介绍云炫AI智剪如何轻松批量剪辑，将MP4视频转换为FLV格式，帮助您提高工作效率，减少…
高防CDN：保卫您的网站免受攻击之利与弊
在当今数字化时代，网络安全对于网站经营者至关重要。高防CDN（Content Delivery Network）技术旨在提供强大的安全性，以保护网站免受恶意攻击。本文将探讨高防CDN为普通网站带来的优势与不足之处，并分析国内外高防CDN的发…
在C代码中找到栈顶的位置并访问栈空间
任务目标
在主循环中写一个任务，检查栈是否溢出。 思路
先找到任务的栈顶位置。在初始化时在栈顶位置写一个标志，运行过程中及时检查该标志是否被改写。如果标志位改变了，则判断为栈溢出。 问题
在RTOS中，任务的栈空间是自己分…
Jmeter(十四)：跨线程组传递jmeter变量及cookie的处理详解
setUp线程组 setUp thread group
一种特殊类型的线程组，用于在执行常规线程组之前执行一些必要的操作。 在 setup线程组下提到的线程行为与普通线程组完全相同。不同的是执行顺序--- 它会在普通线程组执行之前被触发；
应用场景举例：
A、测…
项目中拖拽元素，可以使用html的draggable属性，当然也可以用第三方插件interact
项目中拖拽元素，可以使用html的draggable属性，当然也可以用第三方插件interact 一、安装二、引用三、使用 一、安装
npm install interactjs二、引用
import interact from interactjs三、使用
<div class"drag_box"> &…
如何公网远程连接本地群晖NAS中的WebDAV
文章目录 1. 在群晖套件中心安装WebDav Server套件1.1 安装完成后，启动webdav服务，并勾选HTTP复选框 2. 局域网测试WebDav服务2.1 下载RaiDrive客户端2.2 打开RaiDrive，设置界面语言可以选择中文2.3 点击添加按钮，新建虚拟驱动区2…
品牌媒介工作流程是什么，媒体投放目标怎么做？
品牌媒介其实说简单也很简单，说难也很难，简单在于其实事情流程简洁，难呢，在于很多东西如果不亲身体验是无法领悟到精髓的。今天为大家分享下品牌媒介工作流程是什么，媒体投放目标怎么做？ 我们怎么才能在媒体…
2023年腾讯云双11活动云服务器价格表
2023年腾讯云双11活动已经拉开了序幕，腾讯云推出了一系列的优惠活动，下面给大家分享腾讯云双11活动云服务器价格表，对于有需要购买云服务器的用户来说，无疑是一份非常有价值的参考。 一、腾讯云双十一活动入口
活动入口ÿ…
2021-arXiv-The Power of Scale for Parameter-Efficient Prompt Tuning
2021-arXiv-The Power of Scale for Parameter-Efficient Prompt Tuning Paper: https://arxiv.org/abs/2104.08691 Code: https://github.com/google-research/ text-to-text-transfer-transformer/ blob/main/released_checkpoints.md# lm-adapted-t511lm100k
在这项工作中&…
14、Python -- 列表推导式（for表达式）与控制循环
目录 for表达式（列表推导式）列表推导式的说明使用break跳出循环使用continue忽略本次循环使用return结束函数 列表推导式 使用break跳出循环 使用continue忽略本次循环 for表达式（列表推导式）
for表达式用于利用其他区间、元组、…
Telegram 引入了国产小程序容器技术
Telegram 宣布为其开发者提供了一项“能够在 App 中运行迷你应用”的新功能（ 迷你应用即 Mini App，下文中以“小程序”代替）。 在一篇博客文章中，Telegram 的开发者写到“小程序提供了可替代互联网网站的灵活界面（cre…
uni-app：解决异步请求返回值问题
可以使用 Promise 或者回调函数来处理异步请求的返回值。
方法一： Promise处理异步请求的返回值
使用 Promise 可以将异步请求的结果通过 resolve 和 reject 返回，然后通过 .then() 方法获取成功的结果，通过 .catch() 方法获取错误信息。
…
服务器中了360后缀勒索病毒怎么解决，勒索病毒解密，数据恢复
近期，网络上的各种病毒都比较猖獗，而其中较为明显的就是360后缀勒索病毒，从这个月开始云天数据恢复中心接到很多企业的求助，企业的服务器遭到了360后缀勒索病毒的攻击，通过给用户的服务器检测与加密病毒的分析…
财务RPA机器人真的能提高效率吗？
财务部门作为一个公司的管理职能部门承担着一个公司在商业活动中各个方面的重要职责。理论上来说，一个公司的财务部门的实际工作包含但不限于对企业的盈亏情况进行评估、对风险进行预测、通过数据分析把握好公司的财务状况、税务管理等。
然而，实际上在…
内网穿透的应用-Linux JumpServer堡垒机：安全远程访问解决方案
文章目录 前言1. 安装Jump server2. 本地访问jump server3. 安装 cpolar内网穿透软件4. 配置Jump server公网访问地址5. 公网远程访问Jump server6. 固定Jump server公网地址 前言
JumpServer 是广受欢迎的开源堡垒机，是符合 4A 规范的专业运维安全审计系统。JumpS…
二、W5100S/W5500+RP2040树莓派Pico＜DHCP＞
文章目录 1 前言2 简介2 .1 什么是DHCP？2.2 为什么要使用DHCP？2.3 DHCP工作原理2.4 DHCP应用场景 3 WIZnet以太网芯片4 DHCP网络设置示例概述以及使用4.1 流程图4.2 准备工作核心4.3 连接方式4.4 主要代码概述4.5 结果演示 5 注意事项6 相关链接 1 前言 …
初识Java 16-1 字符串
目录
字符串的常量和变量
不变的String常量
String变量
重载的和更快的StringBuilder
容易忽略的递归现象
对字符串的操作
格式化输出
System.out.format()
Formatter类
格式说明符
Formatter转换
String.format() 新特性：文本块 本笔记参考自ÿ…
【Django restframework】django跨域问题，解决PUT/PATCH/DELETE用ajax请求无法提交数据的问题
【Django restframework】django跨域问题，解决PUT/PATCH/DELETE用ajax请求无法提交数据的问题 1 问题描述：
我用restframework(ModelSerializerGenericApiView)开发了一组符合RestFul接口标准的接口，这意味着它将支持客户端发来的GET、POST、…
【分布式技术专题】「分布式技术架构」MySQL数据同步到Elasticsearch之N种方案解析，实现高效数据同步
MySQL数据同步到Elasticsearch之N种方案解析，实现高效数据同步 前提介绍MySQL和ElasticSearch的同步双写优点缺点针对于缺点补充优化方案 MySQL和ElasticSearch的异步双写优点缺点 定时延时写入ElasticSearch数据库机制优点缺点 开源和成熟的数据迁移工具选型Logsta…
【SwiftUI模块】0060、SwiftUI基于Firebase搭建一个类似InstagramApp 2/7部分-搭建TabBar
SwiftUI模块系列 - 已更新60篇 SwiftUI项目 - 已更新5个项目 往期Demo源码下载 技术:SwiftUI、SwiftUI4.0、Instagram、Firebase 运行环境: SwiftUI4.0 Xcode14 MacOS12.6 iPhone Simulator iPhone 14 Pro Max SwiftUI基于Firebase搭建一个类似InstagramApp 2/7部分-搭建Tab…
最新文章
- 民宿预定管理系统｜Java｜SSM｜Vue｜ 前后端分离
- 单例模式与QT中的C++实现
- elementui el-input修改字体样式
- Figma入门-填充、描边、效果、导出
- 鸿蒙学习高效开发与测试-集成开发环境（4）
- UE5 第一人称射击项目学习（完结）
- 【AI】Sklearn
- 目标检测之学习路线（本科版）
- Dockerfile打包部署
- 鸿蒙学习使用模拟器运行应用（开发篇）
- 数组学习后记——递归
- 每天五分钟深度学习：神经网络的前向传播的计算过程（单样本）
- 网络编程学习探索系列之——广播原理剖析
- iOS实时查看App运行日志
- 单火线开关语音芯片AT6811
- # 从浅入深 学习 SpringCloud 微服务架构（七）Hystrix（2）
- #### golang中【堆】的使用及底层 ####
- ##13 如何在Python中优雅地使用异常处理