Perfectly Reliable Message Transmission

We consider the problem of reliable message transmission between two synchronous players connected by n wires, some of which may be faulty. We show how to get reliability “for free”—reliable transmission of b bits involves a total communication of only O(b) bits, when b is large enough. We also construct an efficient Perfectly Secure Message Transmission Protocol.