Failure detectors. There is a connection between account- ability and failure detectors. A failure detector is designed to provide each process in the system with some advice, typically a list of processes that are faulty in some manner. However, failure detectors tend to have a different set of goals. They are used during an execution to help make progress, while accountability is usually about what can be determined post hoc after a problem occurs. They provide advice to a process, rather than proofs of culpability that can be shared. They tend to be designed for use in fully asynchronous systems (i.e., to capture synchrony assumptions), and protocols that rely on them tend to assume that t < n/3. 4To be precise, they refer to this situation as one where a malicious process is permanently suspected but never exposed; our goal is to guarantee that at least n/3 malicious processes are exposed, in their terminology. 5Note that this requires Byzantine users have a large mining power if proof-of-work is needed for block creation. Most of the work in this area has focused on detecting crash failures (see, e.g., [8]). There has been some interesting work extending this idea to detecting Byzantine failures [15, 16, 20, 24]. Malkhi and Xxxxxx [24] introduced the concept of an unreliable Byzantine failure detector that could detect quiet processes, i.e., those that did not send a message when they were supposed to. They showed that this was sufficient to solve Byzantine Agreement. Kihlstrom, Moser, and Xxxxxxx-Xxxxx [20] continue this direction, considering failures of both omission and commis- sion. Of note, they define the idea of a mutant message, i.e., a message that was received by multiple processes and claimed to be identical (e.g., had the same header), but in fact was not. The Polygraph Protocol is designed so that only malicious users sending a mutant message can cause disagreement. In fact, the main task of accountability in this paper is identifying processes that were supposed to broadcast a single message to everyone and instead sent different messages to different processes. ≤ Maziéres and Shasha propose SUNDR [25] that detects Byzantine behaviors in a network file system if all clients are honest and can communicate directly. Polygraph clients request multiple signatures from servers so that they do not need to be honest. Li and Maziéres [23] improves on SUNDR with BFT2F, a weakly consistent protocol when the number of failures is n/3 t < 2n/3 and its BFTx variant th...
