<p>In order to develop solutions that perform actions as early as possible, analysis of distributed algorithms using epistemic logic has generally concentrated on “full-information protocols”, which may be inefficient with respect to space and computation time. The paper reconsiders the epistemic analysis of the problem of Simultaneous Byzantine Agreement with respect to weaker, but more practical, exchanges of information. This paper first clarifies some issues concerning both the specification of this problem and the knowledge based program characterizing its solution. One of these differences concerns the distinction between the notions of “nonfaulty” and “not yet failed”, on which there are variances in the literature. A second difference in the literature concerns the use of common knowledge versus common belief in the knowledge based program. The paper identifies situations where these notions are equivalent, but establishes that the version of the knowledge based program using common belief of the nonfaulty agent is more general. It is then shown that, when implemented relative to a given failure model and an information exchange protocol satisfying certain conditions, the common belief based knowledge based program yields a protocol that is optimal relative to solutions using the same information exchange. Conditions are also identified under which this implementation is also an optimum, but an example is provided that shows this does not hold in general.</p>