• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Parallel and Distributed Systems, IEEE Transactions on >Discovering Network Topology in the Presence of Byzantine Faults
【24h】

Discovering Network Topology in the Presence of Byzantine Faults

机译：在存在拜占庭式故障的情况下发现网络拓扑

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

摘要

We pose and study the problem of Byzantine-robust topology discovery in an arbitrary asynchronous network. The problem is an abstraction of fault-tolerant routing. We formally state the weak and strong versions of the problem. The weak version requires that either each node discovers the topology of the network or at least one node detects the presence of a faulty node. The strong version requires that each node discovers the topology regardless of faults. We focus on noncryptographic solutions to these problems. We explore their bounds. We prove that the weak topology discovery problem is solvable only if the connectivity of the network exceeds the number of faults in the system. Similarly, we show that the strong version of the problem is solvable only if the network connectivity is more than twice the number of faults. We present solutions to both versions of the problem. The presented algorithms match the established graph connectivity bounds. The algorithms do not require the individual nodes to know either the diameter or the size of the network. The message complexity of both programs is low polynomial with respect to the network size. We describe how our solutions can be extended to add the property of termination, handle topology changes, and perform neighborhood discovery.
机译：我们提出并研究了任意异步网络中拜占庭鲁棒拓扑发现的问题。问题是容错路由的抽象。我们正式陈述了该问题的弱点和强点。弱版本要求要么每个节点都发现网络的拓扑，要么至少一个节点检测到故障节点的存在。增强版本要求不考虑故障而每个节点都可以发现拓扑。我们致力于解决这些问题的非密码解决方案。我们探索他们的界限。我们证明只有当网络的连通性超过系统中的故障数量时，弱拓扑发现问题才可以解决。类似地，我们证明只有网络连接数是故障数量的两倍以上，问题的强版本才可以解决。我们为两种版本的问题提供解决方案。提出的算法与已建立的图连通性边界匹配。该算法不需要各个节点知道网络的直径或大小。相对于网络大小，这两个程序的消息复杂度都是低多项式。我们描述了如何扩展解决方案以添加端接属性，处理拓扑更改以及执行邻居发现。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号