• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Parallel and Distributed Systems >Self-stabilizing distributed queuing
【24h】

Self-stabilizing distributed queuing

机译：自稳定分布式排队

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

摘要

Distributed queuing is a fundamental coordination problem arising in a variety of applications, including distributed shared memory, distributed directories, and totally ordered multicast. A distributed queue can be used to order events, user operations, or messages in a distributed system. This paper presents a new self-stabilizing distributed queuing protocol. This protocol adds self-stabilizing actions to the arrow distributed queuing protocol, a simple path-reversal protocol that runs on a spanning tree of the network. We present a proof that the protocol stabilizes to a stable state irrespective of the (perhaps faulty) initial state, and also present an analysis of the time until convergence. The self-stabilizing queuing protocol is structured as a layer that runs on top of any self-stabilizing spanning tree protocol. This additional queuing layer is guaranteed to stabilize in time bounded by a constant number of message delays across an edge, thus establishing that the stabilization time for distributed queuing is not much more than the stabilization time for spanning tree maintenance. The key idea in our protocol is that the global predicate defining the legality of a protocol state can be written as the conjunction of many purely local predicates, one for each edge of the spanning tree.
机译：分布式排队是各种应用程序中出现的基本协调问题，包括分布式共享内存，分布式目录和完全有序的多播。分布式队列可用于对分布式系统中的事件，用户操作或消息进行排序。本文提出了一种新的自稳定分布式排队协议。该协议向箭头分布式排队协议添加了自稳定操作，箭头分布式排队协议是在网络的生成树上运行的简单路径反转协议。我们提供了一个证明，该协议可以稳定到稳定状态，而与（可能是错误的）初始状态无关，并且还提供了对收敛之前的时间的分析。自稳定排队协议被构造为在任何自稳定生成树协议之上运行的层。保证该附加排队层在时间上稳定，该时间受到跨边缘的消息延迟的恒定数量的限制，从而确定了分布式排队的稳定时间不多于生成树维护的稳定时间。我们协议中的关键思想是，可以将定义协议状态合法性的全局谓词写为许多纯局部谓词的结合，每个生成谓词用于生成树的每个边缘。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号