program Chandy - Misra shortest path { program for process 0} send ( D (0)+ w (0, k ),0) to each node in k EN (0); deficit :=| N (0)|; do D ( i )+ w ( i ,0) z D (0)→ send ack to sender i deficit >0 ack → deficit := deficit -1{ deficit =0 signals termination } od ; { program for process j >0 after receiving a message from process { initially Vj : D ( j )=∞, deficit =0} do D ( i )+ w ( i , j )< D ( j )→ if ( deficit >0)^( parent ≠ j )→ send ack to parent fi ; D ( j ):= D ( i )+ w ( i , j ); parent := i ;{ the sender becomes the new parent } send the new D ( j ) to each node in N ( j ){ i }; deficit := deficit +| N ( j )|-1 D ( i )+ w ( i , j ) z D ( j )→ send ack to sender j deficit >0 Aack → deficit := deficit -1 ( deficit =0)^( parent ≠ j )→ send ack to parent ; parent = j od 日
时间: 2024-04-28 18:26:11 浏览: 18
这段程序是一个用于计算Chandy-Misra最短路径的分布式算法,其中每个进程都会发送消息给和它相邻的进程,以计算最短路径。进程0会发送消息给所有它相邻的进程k,其中包括自己,消息包括从0到k的距离和0的标识符。接着进程0会等待所有进程回复ack,直到deficit为0,表示计算完成。
对于其他进程j,初始时它们的最短距离为无穷大,deficit为0。当它接收到来自进程i的消息时,如果通过i到达0的距离加上i到j的距离比当前的最短距离小,那么它就会更新最短距离,并将i设为它的父节点。它会发送一个ack给i,如果它当前的deficit大于0并且它的父节点不是j,它会发送一个ack给它的父节点。接着,它会将新的最短距离发送给它的所有邻居,并更新它的deficit。如果它收到来自j的消息,它会将j设为它的父节点并发送一个ack给j。这个过程会一直持续直到所有进程的deficit为0,表示计算完成。
相关问题
Process O turns red ; records no =0,| sent (0,1)|=1, and | received (2,0)|=0; and sends the marker along (0,1). 2. Process 1 receives the token and forwards it along (1,2) before receiving the marker . Then , it receives the marker ; turns red ; records n1=0,| received (0,1)|=1, and t ,2= l ; andsends the marker along (1,2). 3. Process 2 receives the token and forwards it along (2,0) before receiving the marker . Then , it receives the marker ; turns red ; records n2=0,| received (1,2)=1, and | sent (2,0)|=1; and forwards the marker to process 0. 4. Process O receives the token and then receives the marker along (2,0). The algorithm terminates here .The total number of tokens recorded is as follows :( no + n ]+n2)+(| sent (0,1)- received (0,1)|)+(| sent (1,2)|-| received (1,2)|)+(| sent (2,0)|-| received (2,0)|)=1. This is consistent with the expected outcome .. Let machine i start Chandy-Lamport snapshot before it has sent M along ch1. Also, let machine j receive the marker after it sends out M’ along ch2. Observe that the snapshot state is down ∅ up M’ Doesn’t this appear strange? This state was never reached during the computation!再举至少两个运行场景的例子,并分析它们的特征,说明是否仍然是循环的;若有循环,循环的规律是什么等等
Based on the provided text, the question seems to be asking for an analysis of the Chandy-Lamport snapshot algorithm in certain scenarios and to provide examples of such scenarios.
In the given scenario, machine i starts the snapshot before sending message M along ch1, and machine j receives the marker after sending out message M' along ch2. The resulting snapshot state is down ∅ up M', which seems strange since this state was never reached during the computation.
One possible explanation for this is that the snapshot algorithm is designed to capture a specific moment in time, regardless of whether or not that moment was reached during the computation. In other words, the algorithm is not limited to capturing only states that were actually reached during the computation, but rather any state that could have been reached at some point.
As for examples of running scenarios, here are two possible scenarios and their characteristics:
Scenario 1:
- Process 0 sends message M1 to Process 1
- Process 1 receives M1 and sends message M2 to Process 2
- Process 2 receives M2 and sends message M3 to Process 0
- Process 0 receives M3 and terminates
In this scenario, the algorithm should record a snapshot state consisting of all messages in transit, as well as the state of each process's local variables at the moment the snapshot was taken.
Scenario 2:
- Process 0 sends message M1 to Process 1
- Process 1 receives M1 and sends message M2 to Process 2
- Process 1 receives the marker and turns red
- Process 2 receives M2 and sends message M3 to Process 0
- Process 0 receives M3 and terminates
In this scenario, the algorithm should record a snapshot state consisting of all messages in transit, as well as the state of each process's local variables at the moment the marker was received by Process 1. This scenario demonstrates that the algorithm can handle the presence of markers and still capture a consistent snapshot state.
Exactly-once 每一条消息只被流处理系统处理一次。 即使是在各种故障的情况下,流应用程序中的所有算子都保证事件只会被『精确一次』的处理。 Flink实现『精确一次』的分布式快照/状态检查点方法受到 Chandy-Lamport 分布式快照算法的启 发。 流应用程序中每个算子的所有状态都会定期做 checkpoint。 如果是在系统中的任何地方发生失败,每个算子的所有状态都回滚到最新的全局一致 checkpoint 点。 在回滚期间,将暂停所有处理。源也会重置为与最近 checkpoint 相对应的正确偏移量。 整个流应用程序基本上是回到最近一次的一致状态,然后程序从该状态重新启动。 。。。根据现实解释。。。
精确一次语义是指在流应用程序中每个事件只会被处理一次,而不会出现多次处理或者被漏处理的情况。这是非常重要的,因为流处理系统处理的数据往往是实时的,而且是不可重复的。如果出现重复处理或者漏处理的情况,就可能导致数据的不一致性,进而影响到业务的正确性。
Flink通过实现分布式快照/状态检查点方法来保证精确一次语义。具体来说,Flink会定期对所有算子的状态做checkpoint,将所有状态保存到持久化存储中。如果在系统中出现任何故障,Flink会将所有算子的状态回滚到最新的全局一致checkpoint点,源也会重置为与最近checkpoint相对应的正确偏移量。这样,整个流应用程序就可以回到最近一次的一致状态,然后程序从该状态重新启动,保证了数据的一致性和正确性。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)