论文标题
真正的原子多播（扩展版本）的最弱故障检测器
The Weakest Failure Detector for Genuine Atomic Multicast (Extended Version)
论文作者
论文摘要
Atomic Broadcast是一组对一组分布式过程中订购消息的原始沟通。原子多播是其自然概括，其中每条消息$ m $都被解决为$ dst（m）$，这是该过程的一个称为其目标组的子集。仅当过程仅在向其发送消息时才能采取步骤时，解决原子多播的方法是真实的。真正的解决方案是实践中使用的解决方案，因为它们具有更好的性能。 让$ g $为所有目的地组，$ f $是其中的循环系列，那就是$ g $的子集的相交图是汉密尔顿。本文确定，解决真正的原子多播的最弱的失败探测器为$μ=（\ wedge_ {g，h \ in G} 〜σ_ {g \ cap h}）\ wedge（\ wedge_ {g}检测器仅限于$ p $中的流程，（ii）$γ$是一个新的故障检测器，在$ f $有缺陷时，在f $ in F $中的过程中告知这些过程。 我们还研究了原子多播的两个经典变化。第一个变化要求消息传递遵循实时订单。在这种情况下，必须使用$ 1^{g \ cap h} $加强$μ$，这是指示器故障检测器，当$ g \ cap h $中的$ g \ cup h $中的每个过程都告知每个过程。第二个变体需要隔离目标组运行时要传递消息。我们证明其最弱的故障检测器至少为$μ\ wedge（\ wedge_ {g，h \ in G} 〜Ω__ {g \ cap h}）$。当$ f = \ varnothing $时，可以实现此值。
Atomic broadcast is a group communication primitive to order messages across a set of distributed processes. Atomic multicast is its natural generalization where each message $m$ is addressed to $dst(m)$, a subset of the processes called its destination group. A solution to atomic multicast is genuine when a process takes steps only if a message is addressed to it. Genuine solutions are the ones used in practice because they have better performance. Let $G$ be all the destination groups and $F$ be the cyclic families in it, that is the subsets of $G$ whose intersection graph is hamiltonian. This paper establishes that the weakest failure detector to solve genuine atomic multicast is $μ=(\wedge_{g,h \in G}~Σ_{g \cap h}) \wedge (\wedge_{g \in G}~Ω_g) \wedge γ$, where (i) $Σ_P$ and $Ω_P$ are the quorum and leader failure detectors restricted to the processes in $P$, and (ii) $γ$ is a new failure detector that informs the processes in a cyclic family $f \in F$ when $f$ is faulty. We also study two classical variations of atomic multicast. The first variation requires that message delivery follows the real-time order. In this case, $μ$ must be strengthened with $1^{g \cap h}$, the indicator failure detector that informs each process in $g \cup h$ when $g \cap h$ is faulty. The second variation requires a message to be delivered when the destination group runs in isolation. We prove that its weakest failure detector is at least $μ\wedge (\wedge_{g, h \in G}~Ω_{g \cap h})$. This value is attained when $F=\varnothing$.
