This paper introduces a novel, fast atomic-snapshot protocol for asynchronous message-passing systems. In the process of defining what "fast" means exactly, we spot a few interesting issues that arise when conventional time metrics are applied to long-lived asynchronous algorithms. We reveal some gaps in latency claims made in earlier work on snapshot algorithms, which hamper their comparative time-complexity analysis. We then come up with a new unifying time-complexity metric that captures the latency of an operation in an asynchronous, long-lived implementation. This allows us to formally grasp latency improvements of our atomic-snapshot algorithm with respect to the state-of-the-art protocols: optimal latency in fault-free runs without contention, short constant latency in fault-free runs with contention, the worst-case latency proportional to the number of active concurrent failures, and constant amortized latency.

We consider consensus protocols in the model that is most commonly considered for use in state machine replication, as initiated by Dwork-Lynch-Stockmeyer, then by Castro-Liskov in 1999 with "PBFT." Such protocols guarantee, assuming n players out of which t < n/3 are maliciously corrupted, that the honest players output the same valid value within a finite number of messages, after the (unknown) point in time where both: the network becomes synchronous, and a designated player (the leader) is honest. The state of the art (Hotstuff, PODC'19), achieves linear communication complexity, but at the cost of additional latency, due to one more round-trip with the leader. Furthermore, it relies on constant-size threshold signatures schemes (TSS), for which all prior-known constructions require a costly interactive (or trusted) setup. We remove all of these limitations. The communication bottleneck of PBFT lies in the subprotocol, denoted as "view change," in which the leader forwards 2t+1 signed messages to each player. Then, each player checks that these 2t+1 messages satisfy some predicate, which we denote "non-supermajority''. We replace this with a responsive subprotocol, with linear communication complexity, that enables players to check this predicate. Its construction is elementary, since it requires only black box use of any TSS. In the full version of our paper \citemalicious2 we achieve three things. Firstly, we further optimize this subprotocol from succinct arguments of many signed messages, which we instantiate from Attema-Cramer-Rambaud \cite[2021-3-9 version]ACR20. As an introduction to these methods, we discuss here the simplest case, which is the construction in \citeACR20 of the first logarithmic-sized TSS with transparent setup. Second, we also address another complexity challenge pointed in Hotstuff, namely, that protocols with fast termination in favorable runs, have so far quadratic complexity, due to an even more complex view change. Third, we enable halting in finite time with (amortized) linear complexity, which was an unsolved question so far when external validity is required.

This paper puts a new light on computational secret sharing with a view towards distributed storage environments. It starts with revisiting the security model for encrypted data protection against key exposure. The goal of this revisiting is to take advantage of the characteristics of distributed storage in order to design faster key leakage resisting schemes, with the same security properties as the existing ones in this context of distributed storage.