Brief Announcement: The Fault-Tolerant Cluster-Sending Problem
Brief Announcement: The Fault-Tolerant Cluster-Sending Problem
复制标题
简要公告：容错集群发送问题
DOI：
10.4230/lipics.disc.2019.45
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Mohammad Sadoghi
中科院分区：
文献类型：
--
作者：
Jelle Hellings;Mohammad Sadoghi
传统上，能够容忍拜占庭行为的容错分布式系统的开发主要集中在共识协议上，它支持完全复制的设计。然而，对于更复杂的高性能拜占庭分布式系统的开发，更专门的容错通信原语是必要的。
The development of fault-tolerant distributed systems that can tolerate Byzantine behavior has traditionally been focused on consensus protocols, which support fully-replicated designs. For the development of more sophisticated high-performance Byzantine distributed systems, more specialized fault-tolerant communication primitives are necessary, however.
In this brief announcement, we identify the cluster-sending problem - the problem of sending a message from one Byzantine cluster to another Byzantine cluster in a reliable manner - as such an essential communication primitive. We not only formalize this fundamental problem, but also establish lower bounds on the complexity of this problem under crash failures and Byzantine failures. Furthermore, we develop practical cluster-sending protocols that meet these lower bounds and, hence, have optimal complexity. As such, our work provides a strong foundation for the further exploration of novel designs that address challenges encountered in fault-tolerant distributed systems.