• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Parallel and Distributed Systems, IEEE Transactions on >Compression of View on Anonymous Networksȁ4;Folded Viewȁ4;
【24h】

Compression of View on Anonymous Networksȁ4;Folded Viewȁ4;

机译：匿名网络上视图的压缩ȁ4；折叠视图ȁ4；

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

摘要

View is a labeled directed graph containing all information about the network that a party can learn by exchanging messages with its neighbors. View can be used to solve distributed problems on an anonymous network (i.e., a network that does not guarantee that every party has a unique identifier). This paper presents an algorithm that constructs views in a compressed form on an anonymous n-party network of any topology in at most 2n rounds with O(n^6log n) bit complexity, where the time complexity (i.e., the number of local computation steps per party) is O(n^6log n). This is the first view-construction algorithm that runs in O(n) rounds with polynomial bits complexity. The paper also gives an algorithm that counts the number of nonisomorphic views in the network in O(n^6log n) time complexity if a view is given in the compressed form. These algorithms imply that some well-studied problems, including the leader election problem, can deterministically be solved in O(n) rounds with polynomial bit and time complexity on an anonymous n-party network of any topology.
机译：视图是带标签的有向图，其中包含有关一方可以通过与邻居交换消息来学习的有关网络的所有信息。 View可用于解决匿名网络（即不能保证每一方都有唯一标识符的网络）上的分布式问题。本文提出了一种算法，该算法最多可以在2n轮内以O（n ^ 6log n）位复杂度在任何拓扑的匿名n-party网络上以压缩形式构造视图，其中时间复杂度（即本地计算的数量）每方的步骤数）为O（n ^ 6log n）。这是第一个以多项式位复杂度在O（n）轮次中运行的视图构造算法。本文还给出了一种算法，如果以压缩形式给出视图，则该算法将以O（n ^ 6log n）时间复杂度来计算网络中非同构视图的数量。这些算法表明，可以在任意拓扑的匿名n-方网络上以多项式位和时间复杂度在O（n）轮中确定性地解决一些经过深入研究的问题，包括领导人选举问题。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号