• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Structural information and communication complexity >Distributed Tree Comparison with Nodes of Limited Memory
【24h】

Distributed Tree Comparison with Nodes of Limited Memory

机译：具有有限内存节点的分布式树比较

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

摘要

We consider the task of comparing two rooted trees with port labelings. Roots of the trees are joined by an edge and the comparison has to be carried out distributedly, by exchanging messages among nodes. If the two trees are isomorphic, all nodes must finish in a state YES, otherwise they have to finish in a state NO and break symmetry, nodes of one tree getting label 0 and of the other label 1. Nodes are modeled as identical automata, and our goal is to establish tradeoffs between the memory size of such an automaton and the efficiency of distributed tree comparison, measured either by the time or by the number of messages used for communication between nodes. We consider both the synchronous and the asynchronous communication and establish exact trade-offs in both scenarios. For the synchronous scenario we are concerned with memory vs. time trade-offs. We show that if the automaton has x bits of memory, where x ≥ clog n, for a small constant c, then the optimal time to accomplish the comparison task in the class of trees of size at most n and of height at most h > 1 is θ(max(h, n/x)). For the asynchronous scenario we study memory vs. number of messages trade-offs. We show that if the automaton has x bits of memory, where n ≥ x ≥ clog Δ, then the optimal number of messages to accomplish the comparison task in the class of trees of size at most n and of maximum degree at most Δ is θ(n~2/x).
机译：我们考虑比较带有端口标签的两棵根树的任务。树的根由一条边连接起来，并且必须通过在节点之间交换消息来比较地进行比较。如果两棵树是同构的，则所有节点必须以状态YES结束，否则它们必须以状态NO结束并破坏对称性，其中一棵树的节点获得标签0，另一棵树的节点获得标签1。我们的目标是在这种自动机的内存大小与分布式树比较效率之间建立折衷，可以通过时间或节点之间通信所使用的消息数量来衡量。我们同时考虑了同步通信和异步通信，并在两种情况下都建立了精确的权衡。对于同步方案，我们关注内存与时间的权衡。我们证明，如果自动机具有x位内存，其中x≥clog n，且常数c很小，则在大小最大为n且高度最大为h>的树类中完成比较任务的最佳时间1是θ（max（h，n / x））。对于异步方案，我们研究内存与消息权衡的数量之间的关系。我们证明如果自动机具有x位内存，其中n≥x≥clogΔ，则在大小最大为n且最大程度为Δ的树的类别中完成比较任务的最佳消息数为θ （n〜2 / x）。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号