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.
