Traditionally, the problems of Byzantine agreement, consensus, and interactive consistency are studied in a fully connected network with processors in malicious failure only. Such problems are re-examined with the assumption of malicious faults on both processors and links. The proposed protocols use the minimal number of message exchanges to make each fault-free processor reach a common agreement for the cases of processor failure, link failure, or processor and link failure.