复习一中间件概念在分布式系统所扮演的角色和位置

组织起来，该层在逻辑上位于由用户和应用程序组成的与由操作系统组成的低层之间，1.基于分布式文件系统(distributedfile2.RPCRemoteProcedure3.二：分布式系统的进程通信，基本问题调用的基本原理和步骤十个步骤广域网中,agent的的数据，并执行对环境产生影响的行为。Agentagent减少网络负担Theyreducethenetworkload.agent允许用户将会话打包转移克服网络延迟问题They enetworklatency.将资源从中心控制器转移到本封装协议Theyencapsulate异步并自治执行Theyexecuteasynchronouslyand动态调整Theyadapt天然的异构性Theyarenaturally是健壮和容错的Theyarerobustandfault-agentAgent可以和其他Agent 名称解析就是查询名称的过程。考虑一个路径名，如N:<lable-1,label-2,…,label-n>。该名称的解析是从命名图的节点N开始的，在其 表中查询名称label-1，并返回label-1 表中继续查询名称label-2，依此类推，假设该命名路径确实存在，那么解析会在由label-n指向的最后一个节点上nl:<vu,cs,ftp,pub,globe,index.txt>。在同样使用递归名称解析的情况下，下一台服务器将解析完整的路当任何一个进程发现协调者不再响应请求时，它就发起一个。进程P按如下过程主持一次：P向所有编号比它大的进程发送一个election进程4主持一个进程5和6进行响应，告诉进程4停止进程5和6此时各自主持一个进程6通知进程5停止2election消息，并将该消息发送给它的后继者。如果后继者了，发送者沿着此环跳过它最终，息返回发起此的程。发者进程接到一个含自己程号的息时，它别出这。时，消类型变成codnaor息，并一次绕运行，向所有进程知谁是调者成员列中进程最大的个)以及环中的员都谁。这个消息再循一周后删除，后每个进 恢原的工作。上图示意了当进程2和进程5同时发现以前的协调者进程7了时，这两个进程各自构造一个election消息，并且它们相互独立地绕环运行。最后，两个消息都将绕环走过25coordinator消息，这两个消息拥有相同的成员，12进入临界区优点：没有进程会处于等待状态(不会出现的情况)；易于实现，每使用一次缺点：协调者是一个单个故障点，所以如果它了，整个系统就可能瘫痪。在一般已经这两种情况，因为上述两种情况都没有消息返回。此外，在规模较大的系统中，2的时间戳比较早，那么接收者向发送者发回一个OK消息。如果它自己的消息的时间戳比时，它向其他队列中的所有进程发送OK消息，并将它们从队列中删除。优点：不会发生死锁或者现象；最大的优点是不存在单个故障点。30token。该令牌绕着环运行，用点对点发送消息的k传递到进程k+1(以环大小为模)。进程从它邻近的进程得到令牌后，检查优点：不会发生现象，那么的情况是等待其他所有进进入这个临界区然严格一致性xx进行的写操作的结果所对应的严格一致性中存在的问是它依赖于全局间(注意由于技术的限制,我们需要处理)图例如下6.5(a)严格的一致性 (b)非严格的一致统维持着一个全局时间顺序。(如果一个数据项被改变了，那么无论数据项改变之后写操作，该读操作都将得到当前的值。)顺序一致性条件定义图例如下6.6顺序一致的与非顺序一致的数据顺序一致的数据；(b)非顺序一致的数据tsop1(x)<tsop2(y)，那么在这个顺序中，操作OP1(x)出现在操作OP2之前。（注意，可线性化的数据也是顺序化主要用于开发算法的形式验证。关于根据时间戳顺序的附加限制使得线性化的实现比顺系，因为y的计算可能依赖于P2所的x值。没有因果关系的操作被称为并发的。实现因果一致性要求哪些进程看到了哪些写操作这意味着必须构建和一张记录哪FIFO一致性（因果一致性允许不同的机器以不同的顺序看到并发的写操作但是所有机器必须以相同的顺序看到因果相关的写操作如果放弃后一条要求这样就得到FIFO一致性）以不同的顺序看到不同的进程写操作。（解释：实际上，这种模型不需要保证不同 FIFO的限制就是这些应用要求从任何位置都可以按顺序看到某个单一进程所产生的写操作。p只对本地数据副本进行操作，当数据被同步时，p进程对数据的最终操作结果才被到其它副本上。当然其它进程对数据的最终操作结果在同步时，会到进程P的副本上。通常，引入同步变量(synchronousvariabiles)S仅有一个关被到其他拷贝，而其他进程的写操作也将被到P的本地拷贝。使用同步变量来部分地定义一致性就得到称为弱一致性(weakconsistency)(Dubois1988)。(1)(2)(3)对同步变量的是FIFO一致的(不需要顺序一致)。获取(acquire)操作是用于通知数据进程进入临界区的操作形式上，如果一个数据满足以下所有条件，那么它符合一致性(Bershad(1)(2)在一个进程的一个同步变量的独占被允许执行之前其他的进程不可以(3)一个进程对一个同步变量执行独占之后在对该同步变量的所有者进行,这些实例可以被看作是可以相对较高程度的不一致性的(大规模的)分布式的数据库(valitecy)。 Vote_Request消息时，就向协调者返回一个mit消息通Vote_Abort消 mit消息。但是，如果有一个参与者表决要取消事务，那么协调者就决定取消事务并多播一个Global_Abort消息。每个提交表决的参与者都等待协调者的最后反应。如果参与者接收到一个mitGlobal_Abort消息时，Thefinitestatemachineforthecoordinatorin2PC.（协调者Thefinitestatemachineforaparticipant.（参与者三阶段提交Commit或者Abort收到所有参与者的确认消息就再发出“全局性提交”。3PC协议在站点失败，甚至是所有的站（a协调者，b参与者：与2PC相比，3PC的主要不同点在于以下情况的参与者可能恢复到了Commit状态，就没有的进程可以恢复到Init、Abort或mit之外的状态。因此存活进程总：分布式系统中的代码迁移是以进程迁移(processmigration)的形式进行的，在这种形式下分类（强弱4种用于定位移动实体的方1种方法是使用广播和多播。实体的标识符被广播给分布式系统的每个进程。为实体提供点的进程通过提供点的地址进行响应。2种方法是使用转发指针。每当一个实体转移到另一个位置时，还要中间位置的转发指针链。链很脆弱3种方法就是给实体指定一个起始位置。每当实体转移到另一个第4种方法是创建一颗搜索树。网络划分成不的域。域可以组合成更的(不)域，以此类推。只有一个顶级域，它覆盖了整个网 节点。如果一个实于域D中， 节点将拥有一个指向D的指针。最低层节点了实体的地址。最 节点知道所有的实体缺点：根节点需要所有实体的位置记录并为每个实体处理请以下四个模型如果一个进程数据x的值，那么该进程对执行任何后续读操作将总是得到tx的值，那么以后他不再会看到较老的版本的x的值。单调写一致性(monotonic-writeconsistency):保证写操作以正确的顺序到数据xx执行任何后续写操作之前xx执行的后续读读后写一致性(writes-follow-readsconsistency):更新是作为前一个读操作的结果同一个进程对数据项x执行的读操作之后的写操作，保证发生在与x值相xx的拷贝上执行，而问题描述有五个哲学家围坐在一圆桌旁桌子有一盘通心面每人面前有一只空盘子，h- f e-h:ke:表示为哲学家吃饭状态的库所f:表示筷子处于备用状态的库所初始状态：筷子备用状态，处于f0-f4k0-k4中。0为例T1变迁1（感到饥饿哲学家在思感到饿了，从库所k0经过T1到达库所h0。哲学家从T22（获得筷子h0，f4，f0T2e0。哲学家T33（释放筷子T3k0库所中，从吃饭状态转入思考状T3f0，f4，从使用状态进入备用状态。

Readyto

Agentmogent系统特有的现象.agent的移动而带agent系统中的普遍现象通信和移动所共享的“位置”信息未进行同步控制是造成通信失效的根本原因OS“位置”在通信失效问题中具有决定性的意义，“位置”的互斥＝》“状态”agent准确agent的状态信Mogentagent状态的数据结构设计agent状态值使用的“临界区”界定agent状态的“临界区”管理Home将mogent状态值的变Mogentmogent按计划准备向另一个结点迁移时,必须通知该mogent的Home,Home收到通知后应将状态值改为移动态mogent到达某个新结点时,mogentHomemogent的到达,Home收到通知,将状态值改为静止态为了同步逻辑时钟，Lamport“先发生”(happens-before)的关系。表达式a→b读作“a在b之前发生”，意思是所有进程一致认为a先发生，然后如果a和b是同一个进程中的两个，且a在之前发生，则a→b为真如果a是一个进程发送消息的而b为另一个进程接收消息的则对这个算法稍作补充就可以满足全局时间的需要。即在每两个之间，时钟必须至少在某些情况下还需要一个附加条件，即两个不会精确地同时发生。为了达到这个目标，我们可以将发生所在的进程号附加在时间的低位后，并用小数点分开。这样，如果进程1和进程2中的都发生在时刻40，那么前者记为40.1后者记为40.2。若同一进程中a在b之前发生，则C(a)<C(b)若a和b分别代表发送一个消息和接收该消息的，则C(a)<C(b)对于所有不同的a和b，C(a)≠C(b)这个算法为我们提供了一种对系统中所有进行完全排序的方法。许多其他的分布式算法都需要这种排序以避免，所以文献中广泛此算法。因果关系可以通过向量时间戳来捕获。分配给a的向量时间戳VT(a)具有下列性质：如果对某一b，有VT(a)<VT(b)，那么认为a在因果关系上处于b之前。向量时间戳的创建是通过让每个进程P一个向量V来完成的，该向量具有下面两个性Vi[i]是到目前为止进程Pi发生的的数量如果Vi[j]=kPi知道进程Pj中已经发生了k第一个性质是通过在进程Pi中的新发生时递增Vi[i]来的第二个性质时通过在所发送的消息中携带向量来的。当进程Pi发送消息时，它将自己的当前向量作为时间戳vt使用这种方式，接收者可以得知进程Pi中已经发生的数更重要的是接收者可以得知进程Pi发送消息m之前其他进程已经发生了多少个。换句话说，消息m的时间戳vt告诉接收者其他进程中有多少发生在它之前，并且消息m可能在因果关系上依赖于这些。PjmVj[kmax{Vj[k],vt[k]}。Pjm之前见到的消息。此后将Vj[i]1，这表示接收消息m的是来自于进程Pi的下一个事信是通过双向进行的，及时而且质量很好。但是有n个将军是叛徒(故障)，他们通过给忠诚的将军发送错误的和的信息(模拟故障进程)来他们达成协议。现在问题在于忠N个进程，其中MN>=3m+1时，才能达成一致，即有三分之二的进程拜占庭问题的最初描述是：n个将军被分隔在不同的地方，忠诚的将军希望通过某种协议误的消息阻挠忠诚的将军达成命令上的一致。Lamport3m，背叛m或者更少时，忠诚的将军可以达成命令上的一致。每两个忠诚的将军必须收到相同的值v(i)（v(i)是第i个将军令如果第i个将军是忠诚的，那么他发送令和每个忠诚将军收到的v(i)相IC1.所有忠诚的副官遵守相同IC2.如果发出命令的将军是忠诚的，那么所有忠诚的副官遵守司令（发出命令的将军）的n-1个副官。m代表叛国者的nn-1个。IC2中副官遵守实际上是指忠诚的将m3m+1个以A1.A2.A3.A1A2假设了两个将军之间通信没有干扰，既不会有背叛者阻碍消息的发送（截断）也OM(m)mOM(M)算法n-1OM(m)m个背叛者且总将军数为3m+1或者的情况下可以解决拜占庭将军问题（考虑到网络应用实际环境，原文使用 发令者将他令发送给每个副官对于每个i，vi是每个副官i从发令者收到令，如果没有收到命令则为撤退命iOM(m-1)vin-2个副官。对于每个i，并且j\neqi，vj是副官i从第（2）步中的副官j发送过来令（使用OM(m-1)算法，如果没有收到第（2）步中的副官j令则默认为撤退命令。最后副官imajority(v1,…,vn-1)得到命令。n=4，m=132第一步发令者执行算法OM(1)将令发送给三个副官，三个副官都正确地收到了命第二步每个收到命令的副官都作为发令者执行算法OM(0)，将令转发给其余副322最后根据majority函数来决定命令。31和发令者的决定。下面看看如果发令者是第一步：发令者向副官发送了不同令，实际情况中是一个者向不同方发送了不同 OM(0)向所有的副官发送命令，这样所（<x,,z>OM(m)m都是可以满足，首先引入一个引理（归纳法证：1mk2k+mkOM(m)IC2（IC2指的是，如果将军是忠诚的，所有的副官遵守将军命令m=0的时候，OM(0)IC2m>0时，首先将军将命令传递给n-1n-1OM(m-1)算法。因为假设了2k+m，所以小于背叛者的两倍这样每轮OM(m-k)算法中忠诚的副官收到令都是majority(v1,v2,...,v(n-1))，其中忠诚副官发送令大于或者等于一半。1m3m个将军和最多mOM(m)IC1IC2mOM(m-1)OM(mm>0。首先考虑kmOM(m)IC2，IC1在发令将军mm-1个副官是背叛者了，又因为3m3m-13m-1>3(m-1)。因此通过归纳法假设OM(m-1)IC1IC2（3(m-1)m-1个背叛者。那么任意两个忠诚jOM(m-1)vjOM(m)算法中每个忠诚的副