首页> 外文OA文献 >A Fault-Resistant Asynchronous Clock Function
【2h】

A Fault-Resistant Asynchronous Clock Function

机译:一种抗故障的异步时钟功能

代理获取
本网站仅为用户提供外文OA文献查询和代理获取服务,本网站没有原文。下单后我们将采用程序或人工为您竭诚获取高质量的原文,但由于OA文献来源多样且变更频繁,仍可能出现获取不到、文献不完整或与标题不符等情况,如果获取不到我们将提供退款服务。请知悉。

摘要

Consider an asynchronous network in a shared-memory environment consisting ofn nodes. Assume that up to f of the nodes might be Byzantine (n > 12f), wherethe adversary is full-information and dynamic (sometimes called adaptive). Inaddition, the non-Byzantine nodes may undergo transient failures. Nodes advancein atomic steps, which consist of reading all registers, performing somecalculation and writing to all registers. This paper contains three main contributions. First, the clock-functionproblem is defined, which is a generalization of the clock synchronizationproblem. This generalization encapsulates previous clock synchronizationproblem definitions while extending them to the current paper's model. Second,a randomized asynchronous self-stabilizing Byzantine tolerant clocksynchronization algorithm is presented. In the construction of the clock synchronization algorithm, a building blockthat ensures different nodes advance at similar rates is developed. Thisfeature is the third contribution of the paper. It is self-stabilizing andByzantine tolerant and can be used as a building block for different algorithmsthat operate in an asynchronous self-stabilizing Byzantine model. The convergence time of the presented algorithm is exponential. Observe thatin the asynchronous setting the best known full-information dynamic Byzantineagreement also has expected exponential convergence time, even though currentlythere is no known reduction between the two.
机译:考虑由n个节点组成的共享内存环境中的异步网络。假设最多f个节点可能是拜占庭式(n> 12f),其中对手是完整信息且动态的(有时称为自适应)。此外,非拜占庭式节点可能会遭受短暂故障。节点按原子步骤前进,该步骤包括读取所有寄存器,执行一些计算并写入所有寄存器。本文包含三个主要贡献。首先,定义时钟功能问题,这是时钟同步问题的概括。这种概括封装了以前的时钟同步问题定义,同时将它们扩展到当前论文的模型。其次,提出了一种随机的异步自稳定拜占庭容忍时钟同步算法。在时钟同步算法的构造中,开发了一种确保不同节点以相似速率前进的构造块。此功能是本文的第三部分。它具有自稳定和拜占庭耐受性,可以用作在异步自稳定拜占庭模型中运行的不同算法的构造块。该算法的收敛时间是指数的。可以看出,在异步设置中,即使目前尚无已知的减少,但最著名的完整信息动态拜占庭协议也具有预期的指数收敛时间。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
代理获取

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号