Message-logging protocols are an integral part of a popular technique for implementing processes that can recover from crash failures. All message-logging protocols require that, when recovery is complete, there be no orphan processes, which are surviving processes whose states are inconsistent with the recovered state of a crashed process. We give a precise specification of the consistency property "no orphan processes". From this specification, we describe how different existing classes of message-logging protocols (namely optimistic, pessimistic, and a class that we call causal) implement this property. We then propose a set of metrics to evaluate the performance of message-logging protocols, and characterize the protocols that are optimal with respect to these metrics. Finally, starting from a protocol that relies on causal delivery order, we show how to derive optimal causal protocols that tolerate f overlapping failures and recoveries for a parameter f (1/spl les/f/spl les).
展开▼
机译:消息记录协议是一种流行的技术的组成部分,用于实现可以从崩溃失败中恢复的流程。所有消息记录协议都要求,在恢复完成后,没有孤立的进程,这些孤立的进程仍处于生存状态,其状态与崩溃的进程的恢复状态不一致。我们给出了一致性属性“无孤立过程”的精确规范。从该规范中,我们描述了消息记录协议的不同现有类(即乐观类,悲观类和因果类)如何实现此属性。然后,我们提出了一组度量标准,以评估消息日志记录协议的性能,并针对这些度量标准确定最佳协议。最后,从依赖因果传递顺序的协议开始,我们展示如何针对参数f(1 / spl les / f / spl les / n)得出容忍f个重叠失败和恢复的最优因果协议。
展开▼