...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>電子情報通信学会技術研究報告. コンピュ-タシステム. Computer Systems >Timed Uniform Consensus Protocol Tolerating Crash and Timing Faults
【24h】

Timed Uniform Consensus Protocol Tolerating Crash and Timing Faults

机译：定时一致共识协议容忍崩溃和定时错误

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Δ-timed uniform consensus is a stronger variant of the traditional consensus and it satisfies the following additional property: The correct process terminates its execution within a constant time Δ(Δ-timeliness), and no two processes decide differently (Uniformity). In this paper, we consider the A-timed uniform consensus problem in presence of f{sub}t crash processes and f{sub}c timing-faulty processes. This paper proposes a Δ-timed uniform consensus algorithms. The proposed algorithm is adaptive in the following sense: It solves the Δ-timed uniform consensus when at least f{sub}t + 1 correct processes exist in the system. If the system has less than f{sub}t + 1 correct processes, the algorithm cannot solve the Δ-timed uniform consensus. However, as long as f{sub}t +1 processes are alive, the algorithm solves (non-timed) uniform consensus. We also investigate the maximum number of faulty processes that can be tolerated. We show that any Δ-timed uniform consensus algorithm tolerating up to f{sub}t timing-faulty processes requires that the system has at least f{sub}t + 1 correct processes. This impossibility result implies that the proposed algorithm attains the maximal resilience about the number of faulty processes. We also show that any Δ-timed uniform consensus algorithm tolerating up to f{sub}t timing-faulty processes cannot solve the (non-timed) uniform consensus when the system has less than f{sub}t + 1 non-crashed processes. This impossibility result implies that our algorithm attains the maximum adaptiveness.
机译：Δ定时统一共识是传统共识的更强变体，它满足以下附加属性：正确的过程在恒定的时间Δ（Δ时效性）内终止其执行，并且没有两个过程做出不同的决定（统一性）。在本文中，我们考虑存在f {sub} t崩溃过程和f {sub} c时序错误过程的A定时一致共识问题。本文提出了一种Δ定时统一共识算法。所提出的算法在以下意义上是自适应的：当系统中至少存在f {sub} t + 1个正确过程时，它解决了Δ定时统一共识。如果系统具有少于f {sub} t +1个正确的过程，则该算法将无法求解Δ定时统一共识。但是，只要有f {sub} t +1个进程存在，该算法就可以解决（非定时）统一共识。我们还将调查可容忍的最大错误进程数。我们证明了，任何能够耐受f {sub} t个定时故障过程的Δ定时统一共识算法都要求系统至少具有f {sub} t +1个正确的过程。这种不可能的结果表明，所提出的算法获得了关于故障过程数量的最大弹性。我们还表明，当系统具有少于f {sub} t +1个非崩溃进程时，任何容忍f {sub} t个定时故障过程的Δ定时统一共识算法都无法解决（非定时）一致共识。 。这种不可能的结果暗示我们的算法获得了最大的适应性。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号