Back
Featured image of post 【分布式与并行计算】分布式作业
作业

【分布式与并行计算】分布式作业

分布式计算巩固类作业

1 逻辑时钟与一致割集

下图中，直线上小黑点给出了时钟计数，请分别用Lamport 逻辑时钟和向量时钟给图上的事件设置时间戳，并给出一致割集和非一致割集的例子。

事件时钟计数
事件时钟计数

答：

  • 设置时间戳

    • Lamport逻辑时钟

      Lamport逻辑时钟
      Lamport逻辑时钟

    • 向量时钟

      向量时钟
      向量时钟

  • 割集的例子

    • 一致割集

      一致割集
      一致割集

    • 非一致割集

      非一致割集
      非一致割集

      包含$e_1^2$这个接收事件但是不包含$e_3^1$这个发送事件。

2 异步分布式系统的故障类型

考虑在异步分布式系统中使用的两个通信服务。在服务A中，消息可能丢失、被复制或延迟，校验和仅应用到消息头。在服务B中，消息可能丢失、延迟或发送地太快以致接收方无法处理它，但到达目的地的消息其内容一定正确。描述每个服务会有的故障类型。根据对有效性和完整性的影响将故障分类。服务B能被描述成一个可靠的通信服务吗？

答：

  • 服务A会有的故障类型

    • 遗漏故障
      • 消息丢失
    • 拜占庭故障
      • checksum仅仅应用到消息的head，消息的body可能发生损坏
      • 消息重复
    • 因为这是异步分布式系统，所以不会有时序故障。

    遗漏故障的消息丢失破坏了有效性。拜占庭故障的可能损坏的消息以及重复的消息破坏了完整性。

  • 服务B会有的故障类型

    • 遗漏故障
      • 消息丢失
      • 发送地太快以致接收方无法处理它，接收遗漏
    • 因为这是异步分布式系统，所以不会有时序故障。

    服务B满足完整性，但是服务B消息发生的遗漏故障，不满足有效性，所以不是可靠的通信服务。

3 Ricart and Agrawala 算法

请证明Ricart-Agrawala的互斥算法满足ME2和ME3。

ME2:进入或退出临界区的请求最终都会成功

ME3:如果一个进入临界区的请求发生在先，那么进入临界区也按此顺序

Ricart-Agrawala算法：

  1. 一个进程申请资源时向所有其他进程发出带有时间戳的申请报文；
  2. 一个进程收到申请报文后，答复这个申请，当且仅当：1）若不在临界区并且自己未申请进入临界区,或者2)自己虽然发出了申请报文，但自己的报文的时间戳大于收到的申请报文。如果已经在临界区，或者自己的申请发送在前，则在出临界区之前将所有的申请挂起。
  3. 申请资源的进程仅在收到其它所有进程的回答报文后才进入临界区使用资源；
  4. 一个进程使用完资源后，它向所有挂起的申请发送回答报文。

证明：

  • 证明满足ME2
    • 一个进程$p_i$要进入临界区向其他进程发送请求，不想进入临界区的进程，或者已经发送了请求但是发送时间戳大于接收请求时间戳$T_i$的进程都会回复。所以进程$p_i$要等待逻辑时间戳$T_i$之前发送了请求的进程以及正在临界区的进程的答复。
    • 在逻辑时间戳$T_i$之前发出请求的进程所等待进程的数量依次递减到1。等正在临界区的进程使用完资源并退出后，所有在等待的进程所需等待进程数量全都减1。此时有一个进程得到了全部的答复，进入临界区。
    • 按照这个过程，只要前边的进程依次进入临界区并退出之后，进程$p_i$就可以成功进入临界区，毕竟没有进程可以插队，所需等待进程数量只能递减。
    • 由于使用完资源后退出临界区不需要等待答复，所以可以成功退出。所以，满足ME2。
  • 证明满足ME3
    • 当进$p_i$给其他进程发送进入临界区的申请时
    • 如果进程$p_j$也想进入临界区，发送的申请的时间戳小于收到的$T_i$，那么$p_j$不会发送答复给$p_i$,这样$p_i$就必须等待$p_j$进入并退出临界区之后才能得到答复，才有可能进入临界区。
    • 如果进程$p_j$也想进入临界区，发送的申请的时间戳大于收到的$T_i$，那么他会回复$p_i$的申请，$p_i$无需等待$p_j$，且当$p_i$收到$p_j$的请求之后不会回复，$p_j$等待$p_i$。
    • 所以，满足ME3

4 改进Ricart and Agrawala 算法

在Ricart-Agrawala的互斥算法中，原始假定系统的进程是不出故障的。请修改算法增加处理一个进程崩溃的情况。

答：如果有进程崩溃，那么它永远不会回复，则发送请求的进程需要一直盲等。

  • 所以每当接收到消息之后要做出答复，回复同意，当且仅当：1）若不在临界区并且自己未申请进入临界区,或者2)自己虽然发出了申请报文，但自己的报文的时间戳大于收到的申请报文。或者回复拒绝，当1）自己处在临界区，或者2）自己的临界区申请的逻辑时间戳小于收到的申请，把回复拒绝的进程缓存起来，等待回复。
  • 如果超出timeout没有收到答复则认为机器故障，只需等待其余的机器全部回复同意
  • 当一个进程退出临界区之后，要向所有回复拒绝的进程回复同意。

5改进基于环的互斥算法

改进基于环的互斥算法使得它能检测权标的丢失并重新生成权标。

答：

  • 一个进程发出申请之后，如果长时间没有拿到权标，则向下一个节点发送一个请求reqest确认权标是否还在。
  • 一个进程收到了确认权标存在的请求request，如果权标在自己手里则向下一个节点发送一个exist，如果权标不在自己手里，则将requst传递给下一个节点
  • 一个进程收到了一个exist消息则将它传递到下一个节点
  • 如果发出申请的进程收到request请求，则认为权标丢失，重新生成权标。如果收到exist，则说明一切正常。

6 双向环结构的选举算法

基于环的选举算法是建立在单向环的假设之上的，为了获得更快的选举速度，现采用双向环结构，即每个节点可以同时向顺时针和逆时针两个方向发送选举消息，请列出新算法的高层描述，并用一个四节点的双向环来说明你的方法。

答：

  • 最初，所有进程标记为非参与者，任意一个进程发起选举，发起选举后，置自己为参与者（$elected_i = ⊥$)，向上下游发送一个选举消息，包含自己的标识符。
  • 一个进程收到选举消息后，那么比较自己的标识符与收到消息中的标识符，
    • 如果自己的标识符小于消息中的标识符，那么顺消息来的方向传递选举消息；
    • 如果自己的标识符大于消息中的标识符
      • 如果自己是非参与者，将消息中的标识符改为自己标识符，顺消息来的方向传递选举消息。
      • 如果自己是参与者，则不转发消息。
    • 如果自己的标识符等于消息中的标识符，那么说明自己的标识符最大，如果还未当选，则当选为协调者，向上游和下游发送一个当选消息，包含自己的标识符P
  • 一个进程收到一个当选消息，如果自己是参与者，设置$elected_i = P$，置自己为非参与者，并且按照消息发送的方向传递给自己的邻居；如果自己已经知晓当选消息，则不转发。
Init elected != ⊥ for process i (i = 1,2,...N)

in the process which start an election:
	function startElection():
		electingMSG <- MSG(type = "electing", value = Local.id)
		Local.elected = '⊥'
		send(msg = electingMSG ,direction = clockwise)
		send(msg = electingMSG , direction = counterclockwise)
	
in process i:
	function handleMSG(MSG msg, Direction direction):
		if msg.type = "electing":
			if Local.id < msg.id:
				send(msg,direction)
				Local.elected = '⊥'
			else if Local.id > msg.id:
				if Local.elected != '⊥':
					msg.value = Local.id
					send(msg, direction)
					Local.elected = '⊥'
				end
			else
				if(process i is not Coordinator)
                	setCoordinator(process i)
                	Local.elected = '⊥'
                	electdeMSG <- MSG(type = "elected", value = Local.id)
                	send(msg = electedMSG, direction = clockwise)
                	send(msg = electedMSG, direction = counterclockwise)
                end
            end
		end      
			
		if msg.type = "elected"
			if Local.elected == '⊥':
				Local.elected = msg.value
				send(msg, direction)
			end
		end

image-20211209165145519
image-20211209165145519

图中: 白色表示初始非参与者，黄色表示参与者，红色表示知道当选结果。蓝色是选举消息，绿色是当选消息。从13号开始发起选举，最终选出23为协调者。

  • 网络带宽：找到最大标识符最多需要N个消息，确认最大标识符最多需要2N个消息，通知当选最多需要N+1个消息，则最多需要消息为 4N+1
  • 回转时间：第一轮寻找花费最多(N/2)个消息，第二轮确认需要最多花费N个消息，第三轮通知最多需要花费(N/2)+1个消息，所以最多需要花费2N+1个消息的回转时间。

7 基于生成树的选举算法

节点之间按照生成树方式连接，仅有边相连的节点能通信，请基于此网络拓扑，设计一个选举算法，给出其伪码。当仅有一个进程发起选举，你的选举算法所需的消息量是多少？

答：假定是有向生成树，每个节点有父节点和子节点，每个节点可以向子节点或者父节点发送消息。任何一个进程都可以发起选举。算法如下：

  • 收到选举消息，将发送消息的标识符和自己的标识符作比较，更改消息中的信息为较大值；如果有子节点，则向子节点发送这个选举消息；如果是叶子节点，则父亲节点返回一个回复消息，包含当前的较大标识符。

  • 等到收到所有子节点的回复消息，选出最大的标识符，返回给父亲节点

  • 当根节点收到最大的 标识符，则向所有的子节点发送当选信息，直到叶节点。如果有子节点发现自己的标识符等于消息中的的标识符，则成为协调者。

我的选举算法所需的消息量选举有N-1个，回复有N-1个，当选有N-1个，所以总共有3N-3个。

Init Local.elected != ⊥ for process i (i = 1,2,...N)
	 Local.count =0 for process i (i = 1,2,...N)

in the process p0 which start an election:
	function startElection():
		electingMSG <- MSG(type = "electing", value = Local.id)
		Local.elected = '⊥'
		for i in son(p0):
			send(electingMSG, dest = i)
		end

in process p:
	function handleMSG(MSG msg):
		if msg.type = "electing":
			Local.elected = '⊥'
			if !isEmpty(son(p):
				msg.value = max(Local.id,msg.value)
				for i in son(p):
					send(msg, dest = i)
				end
			else
				replyMSG = MSG(type = "reply", value = max(Local.id,msg.value)
				send(relpyMSG, dest = father(p))
            end
            
		if msg.type = "reply":
			Local.count++;
			msg.value = max(Local.id, msg.value)
			if(Local.count == son(p).size()):
				if !isEmpty(father(p)):
					send(msg, dest = father(p))
				else
					electedMSG = MSG(type = "elected",value = msg.value)
					for i in son(p):
						send(electedMSG, dest = i)
					end
					Local.elected = msg.value
					if Local.ip == msg.value:
						setCoordinator(process = p)
					end
				end
			end
		end
					
		
		if msg.type = "elected":
			if Local.ip == msg.value:
				setCoordinator(process = p)
			end
			if !isEmpty(son(p)):
				for i in son(p):
					send(msg, dest = i)
				end
			end

8 法定数共识复制

在服务器X、Y和Z上使用法定数共识进行复制，这些服务器都有数据项A和B的副本。A和B副本的初始值是100，并且在X、Y和Z上A和B的选票是1。同样对于A和B，R＝W＝2。一个客户读A的值然后将它写到B上。

1）当客户执行这些操作时，出现了一个分区，将服务器X和Y与服务器Z分隔开了。描述当客户能访问服务器X和Y时，获得的法定数和发生的操作。

2）描述当客户仅能访问服务器Z时，获得的法定数和发生的操作。

3）分区修复了，然后另一个分区发生了，结果X和Z与Y分隔开了。描述当客户能访问服务器X和Z时，获得的法定数和发生的操作。

答：

1）在数据的v0版本时，A和B副本的初始值是100，出现了一个分区，将服务器X和Y与服务器Z分隔开。

XYZ
A = 100（v0)A = 100（v0)A = 100（v0)
B = 100（v0)B = 100（v0)B = 100（v0)

​ 客户可能从X或者Y上读取A，R = 1+1 =2，读取成功。

​ 客户需要在X和Y上写B，W = 1+1 = 2， 写成功。

2)客户只能访问服务器Z，R = 1，客户无法读取；W = 1，客户无法写。

3)当分区被修复后，因为之前的分区导致X和Y的数据要比Z上的数据更新，例如

XYZ
A = 200（v1)A = 200（v1)A = 100（v0)
B = 300（v1)B = 300（v1)B = 100（v0)

此时，另一个分区出现，X和Z与Y分隔开，当客户试图获取法定数的时候，发现Z的数据版本过时，于是Z根据X上的最新数据更新自己。之后客户获取读法定数，R = 1+1 =2，然后读成功。客户获取写法定数，W = 1+1 =2，写成功。

9 串行等价的交错执行

一个服务器管理对象a1, a2, … an ，它为客户提供下面两种操作：read (i)返回对象ai的值。write(i, Value)将对象ai设置为值Value。

事务T和U定义如下：

T: x = read(j); y = read (i); write(j, 44); write(i, 33)

U: x = read(k); write(i, 55); y = read (j); write(k, 66)

请给出事务T和U的3个串行化等价的交错执行。

答：我们给每一步分别表上序号：

T: ①x = read(j); ②y = read (i); ③write(j, 44); ④write(i, 33)

U: ⑤x = read(k); ⑥write(i, 55); ⑦y = read (j); ⑧write(k, 66)

如果按照先T后U的顺序依次执行一个事务的话，我们发现①和⑤，②和⑦，④和⑥有写后写依赖；③和⑦有写后读依赖，①和③，②和④，②和⑥，⑤和⑧有读后写依赖，所以，我们要保证这些依赖的逻辑顺序，串行化等价的交错执行如下：

①⑤②③④⑥⑦⑧

①③⑤②④⑦⑧⑥

①⑤③②⑧⑦④⑥

10 乐观并发控制

考虑将乐观并发控制应用于下列事务T和U的情况：

​ T: x = read(i); write(j, 44);

​ U: write(i, 55); write(j, 66);

如果事务T和U同时处于活动状态，试描述以下几种情况的结果如何：

  1. 服务器首先处理T的提交请求，使用向后验证方式。
  2. 服务器首先处理U的提交请求，使用向后验证方式。
  3. 服务器首先处理T的提交请求，使用向前验证方式。
  4. 服务器首先处理U的提交请求，使用向前验证方式。

对于上面的每种情况，描述事务T和U的操作顺序，注意写操作在验证通过之后才真正起作用。

答：

  1. 服务器首先处理T的提交请求，使用向后验证方式。

    T先开始所以T的验证阶段无事发生，U进入验证阶段之后，U没有读集，所以没有冲突，可以顺利提交。

  2. 服务器首先处理U的提交请求，使用向后验证方式。

    T进入验证阶段，发现T的读集{i}与U的写集{i, j}有冲突，T事务被放弃。

  3. 服务器首先处理T的提交请求，使用向前验证方式。

    U进入验证阶段，发现U的写集{i,j}与T的读集{i}有冲突，所以推迟验证，等T的读集执行完毕之后再提交U。

  4. 服务器首先处理U的提交请求，使用向前验证方式。

    T进入验证阶段，发现U无读集，所以可以通过验证。