Simulating Authenticated Broadcasts to Derive Simple Fault-Tolerant Algorithms

Abstract

Fault-tolerant algorithms for distributed systems are simpler to develop and prove correct if messages can be authenticated. However, using digital signatures for message authentication usually incurs substantial overhead in communication and computation. To exploit the simplicity provided by authentication without this overhead, we present a broadcast primitive that simulates properties of authenticated broadcasts. This gives a methodology for deriving non-authenticated algorithm. We have applied this approach to various problems and in each case obtained simpler and more efficient solutions than those previously known.