Methods, systems, and apparatus, including computer programs encoded on computer storage media, for consensus system downtime recovery. One of the methods includes: multicasting a pre-prepare message to at least some of the backup nodes; obtaining (Q−1) or more prepare messages respectively from (Q−1) or more of the backup nodes, wherein the prepare messages each indicate an acceptance of the pre-prepare message by the corresponding backup node; storing the pre-prepare message and the (Q−1) or more prepare messages; multicasting a commit message to at least some of the backup nodes, the commit message indicating that the primary node agrees to the (Q−1) or more prepare messages; and obtaining, respectively from Q or more nodes among the primary node and the backup nodes, Q or more commit messages each indicating that the corresponding node agrees to (Q−1) or more prepare messages received by the corresponding node.