1 Introduction

Fault-tolerant protocols are important for networked distributed systems that must cope with unreliable components. A fundamental primitive for synchronization among a group of parties is reliable broadcast, where a distinguished party broadcasts a value to the other parties; if the sender is correct, then all non-faulty parties should accept , and if the sender is faulty, all non-faulty parties should decide for the same value or not terminate the protocol at all. In asynchronous networks, which are the focus of this paper, no assumptions are made about network delays and the relative execution speed of the parties.