type
status
date
slug
summary
tags
category
icon
password
Reliable broadcast primitives
Best-effort broadcast
- 如果一个正确进程广播了m，所有进程都会传递m
p3没有保障
算法：Basic Broadcast
pl：perfect link通道（reliable delivery特性）
Reliable Broadcast
RB4:如果消息被一个正确进程传递，则m会被所有正确进程传递
算法：Lazy Reliable Broadcast
beb的deliver来源p与广播的来源s不一定相同，如果此时s不正确，就帮助它广播一遍；如果错误检测器报告了p故障，则重新帮它广播
算法表现：没有崩溃O(N)，最坏情况O(N^2)
算法：Eager Reliable Broadcast
只要接收到信息就帮其转发
Uniform Reliable Broadcast
对URB-4（agreement）的定义不同：只要m被某个节点deliver（无论正确与否），则最后m一定要被所有正确节点deliever
算法：All-Ack Uniform Reliable Broadcast
让正确进程传递信息的前提为当前正确进程是传递过消息进程的子集
delivered表示已经传递的消息，pending表示已经bed- delivered但没有urb- delivered的消息
ack[m]表示发送m的进程数组
收到消息先放到pending，同时转发，当所有正确结点（ack[m]为所有正确结点）都发过，就传递回去
ON - ON2
Quorum（法定人数）
Quorum是节点子集的集合，且任意两个Q1 Q2交集不为空，且对称性，每个Q长度一致
quorum system：只要有一个quorum在就可以保证推进的一致性
防止下列情况出现：
脑裂问题
同时，一定要有一个好的quorum存在，否则无法实现 → liveness
假设有f个机器故障，N-f个机器也可以保证推进 因此2(N-f)>N N≥2f+1
Majority-ACK Uniform Reliable Broadcast
all-ack uniform reliable broadcast 算法依赖 perfect failure detector，换句话说，当failure detector 不属于perfect类型时，uniform agreement 属性可能被违反。
只要求系统中至多存在f个进程会崩溃，N>2f
只要有大于N/2的节点ack就可以deliver
Causal-order broadcast primitives
因果序广播（primitives：原语）
大于等于两个消息，一个消息m1 causes m2，则m1不应该在m2之后传递
eg
Happened-before relationship刻画因果序
Logical clocks
Each process p maintains its own event counter cnt(p)，p increments cnt(p) with every step
p includes cnt(p) in every message it sends
upon q receives a message from p → cnt(q) := max(cnt(q), cnt(p)) + 1
1→2 3→4
存在问题：lc(a) < lc(b) does not imply a → b 可能无关
Vector clocks
- Each process pi maintains a vector of counters n维向量
- Initially, VCi[j] = 0, for every j 属于 1..n
- pi increments VCi[i] with every step
- pi includes VCi[] in every message it sends
- VCj[k] := max(VCj[k], VCi[k]), for every k
- VCj[j] := VCj[j] + 1（追赶机制）
Casual precedence（优先）
但happened before不可以直接映射到broadcast的precedence，修改
Casual-order Reliable Broadcast
新性质：CRB5
Causal delivery: For any message m1 that causally precedes a message m2, i.e., m1 → m2, no process delivers m2 unless it has already delivered m1不允许任何节点先deliver m2再deliver m1
违反因果序：
CRUniformB
继承自uniform的CRB5
No-Waiting Causal-Order Broadcast
past为历史变量，每次广播时同时广播past
接收时先对past判断，如果有没有delivered的就先处理，同时加入到本地的历史，然后再处理新的m
在Complexity的考虑中会使用Truncate（剪枝）
Garbage-Collection of Causal Past
当所有的正确结点都ack，那么把m节点在past中删除
Waiting Causal Broadcast
用v记录当前广播的因果前序，广播时将W中自己的位置赋Isn，且Isn更新
每次接收时V为本地状态，W的每一栏为一个要求的前序，比对后如果没问题，则deliever
如果比对有问题，则只放到pending中，等一等再处理
这里虽然是m2发第二个，但是由于是m1发的第一个，前序为m1-1因此还是100
- Author:faii
- URL:https://www.faii.top/article/688a484b-24df-4487-a0de-9f69ba485d68
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!
Relate Posts