1999/08/12 by Dahlia Malkhi, Malkhi, Dahlia, Michael Merritt +3
Computer Science · #Cryptography and Security (cs.CR) #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Mobile Ad Hoc Networks #Parallel #Security in Wireless Sensor Networks #and Cluster Computing (cs.DC) #c.2.0 #c.2.4 #c.4 #cs.CR #cs.DC
paper · pdf · doi:10.48550/arxiv.cs/9908008
preprint of a paper to appear in the Distributed Computing Journal
arxiv created 1999/08/12 · openalex publication_date 1999/08/12 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A secure reliable multicast protocol enables a process to send a message to a group of recipients such that all correct destinations receive the same message, despite the malicious efforts of fewer than a third of the total number of processes, including the sender. This has been sh own to be a useful tool in building secure distributed services, albeit with a cost that typically grows linearly with the size of the system. For very large networks, for which this is prohibitive, we present two approaches for reducing the cost: First, we show a protocol whose cost is on the order of the number of tolerated failures. Secondly, we show how relaxing the consistency requirement to a probabilistic guarantee can reduce the associated cost, effectively to a constant.