Broadcast and Multicast: Two Paradigms for Fault-Tolerant Distributed Computing

广播和多播是许多最先进的容错分布式系统的核心范例。尽管它们具有根本的重要性，但这些范式尚未被完全理解。它们的许多方面仍未得到探索，许多关键问题仍有待解决。本研究的目标是对容错广播和多播的基础有更深的理解。工作重点是可靠广播、因果广播和原子广播以及相应的组播公式。调查将包括几种类型的故障模型和通信网络背景下的以下问题：(1)规范、算法的发展，以及防止由故障过程发起的广播和多播不一致和污染的新问题的下界。(2)因果广播和多播的算法和下界的发展。(3)开发同时具有时间效率和消息效率的可靠和原子广播协议，其性能随着实际发生的故障数量的增加而优雅地降低。

Broadcast and Multicast are paradigms that are central to many state- of-the-art fault-tolerant distributed systems. Despite their fundamental importance, these paradigms are not yet completely understood. Many of their aspects are still unexplored and many crucial issues remain to be solved. The goal of this research is to develop a deeper understanding of the foundations of fault-tolerant broadcasts and multicasts. The work will focus on Reliable Broadcast, Causal Broadcast and Atomic Broadcast and the corresponding multicast formulations. The investigation will include the following problems in the context of several types of failure models and communication networks: (1) development of specifications, algorithms, and lower bounds for the new problem of preventing inconsistency and contamination via broadcasts and multicasts initiated by faulty processes. (2) development of algorithms and lower bounds for Causal Broadcasts and Multicasts. (3) development of Reliable and Atomic Broadcast protocols that are simultaneously time-efficient and message-efficient, with a performance that gracefully degrades as the number of failures that actually occur increases.