首页> 外文会议>Distributed computing and networking. >Interplay between (Im) perfect ness, Synchrony and Connectivity: The Case of Reliable Message Transmission
【24h】

Interplay between (Im) perfect ness, Synchrony and Connectivity: The Case of Reliable Message Transmission

机译:(Im)完美性,同步性和连通性之间的相互作用:可靠消息传输的情况

获取原文
获取原文并翻译 | 示例

摘要

For unconditionally reliable message transmission (URMT) in synchronous directed networks of n nodes, a subset of which may be malicious, it is well-known that the minimum connectivity requirements for zero-error (perfect) protocols to exist is strictly higher than those where a negligible yet non-zero error probability is allowed (Monte Carlo protocols) [12]. In this work, we study the minimum connectivity requirements for the existence of (a) synchronous Las Vegas, (b) asynchronous Monte Carlo, and (c) asynchronous Las Vegas protocols for URMT. Interestingly, we prove that in any network, a synchronous Las Vegas URMT protocol exists if and only if an asynchronous Monte Carlo URMT protocol exists too. We further show that in any network, an asynchronous Las Vegas URMT protocol exists if and only if a synchronous perfect protocol exists as well. Thus, our results establish an interesting interplay between (im)perfectness, synchrony and connectivity for the case of URMT.
机译:对于n个节点的同步定向网络中的无条件可靠消息传输(URMT),其中的一个子集可能是恶意的,众所周知,对于零错误(完美)协议的最低连接要求严格高于其中允许的误差可以忽略不计,但非零(Monte Carlo协议)[12]。在这项工作中,我们研究了(a)同步拉斯维加斯,(b)异步蒙特卡洛和(c)URMT异步拉斯维加斯协议的存在的最低连接要求。有趣的是,我们证明在任何网络中,当且仅当也存在异步Monte Carlo URMT协议时,才存在同步拉斯维加斯URMT协议。我们进一步证明,在任何网络中,当且仅当也存在同步完善协议时,才存在异步拉斯维加斯URMT协议。因此,对于URMT,我们的结果建立了(不完美),同步和连通性之间有趣的相互作用。

著录项

  • 来源
    《Distributed computing and networking.》|2012年|p.138-152|共15页
  • 会议地点 Hong Kong(HK);Hong Kong(HK)
  • 作者单位

    Center for Security, Theory and Algorithmic Research (C-STAR), International Institute of Information Technology, Hyderabad, 500032, India;

    Center for Security, Theory and Algorithmic Research (C-STAR), International Institute of Information Technology, Hyderabad, 500032, India;

    Center for Security, Theory and Algorithmic Research (C-STAR), International Institute of Information Technology, Hyderabad, 500032, India;

  • 会议组织
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类 计算机网络;计算机网络;
  • 关键词

相似文献

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

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号