The atomic snapshot object (ASO) can be seen as a generalization of the atomic read/write register. ASO divides the object into$n$segments such that each node can update its own segment, and instantaneously scan all segments of the object. ASO is a powerful data structure that has many important applications, such as update-query state machines, linearizable conflict-free replicated data types, generalized lattice agreement, and cryptocurrency as in the form of an asset transfer object. This paper studies ASO in asynchronous message passing systems and proposes a framework for implementing efficient fault-tolerant snapshot objects. Denote by$D$the maximum message delay and$k$the actual number of failures in an execution. Our framework derives two ASO algorithms: •A crash-tolerant ASO algorithm that achieves O(√k. D) time complexity for both update and scan operations, and achieves amortized constant time operations if there are Ω(√k) operations. •A Byzantine ASO algorithm that achieves O(k.D) time complexity for both update and scan operations, and achieves amortized constant time operations if there is no Byzantine node in a given execution. The framework can also be adapted to implement sequentially consistent snapshot objects (SSO) that complete scan operations locally without any communication, and have the same time complexlty for update onerations as in our ASO algorithms.

Shared register emulations on top of message-passing systems provide an illusion of a simpler shared memory system which can make the task of a system designer easier. Numerous shared register applications have a considerably high read-to-write ratio. Thus, having algorithms that make reads more efficient than writes is a fair trade-off.Typically, such algorithms for reads and writes are asymmetric and sacrifice the stringent consistency condition atomicity, as it is impossible to have fast reads for multi-writer atomicity. Safety is a consistency condition that has has gathered interest from both the systems and theory community as it is weaker than atomicity yet provides strong enough guarantees like "strong consistency" or read-my-write consistency. One requirement that is assumed by many researchers is that of the reliable broadcast (RB) primitive, which ensures the "all or none" property during a broadcast. One drawback is that such a primitive takes 1.5 rounds to complete and requires server-to-server communication.This paper implements an efficient multi-writer multi-reader safe register without using a reliable broadcast primitive. Moreover, we provide fast reads or one-shot reads - our read operations can be completed in one round of client-to-server communication. Of course, this comes with the price of requiring more servers when compared to prior solutions assuming reliable broadcast. However, we show that this increased number of servers is indeed necessary as we prove a tight bound on the number of servers required to implement Byzantine-fault tolerant safe registers in a system without reliable broadcast.We extend our results to data stored using erasure coding as well. We present an emulation of single-writer multi-reader safe register based on MDS codes. The usage of MDS codes reduces storage and communication costs. On the negative side, we also show that to use MDS codes and at the same time achieve one-shot reads, we need even more servers.

Fault-tolerant distributed consensus is an important primitive in many large-scale distributed systems and applications. The consensus problem has been investigated under various fault models in the literature since the seminal work by Lamport et al. in 1982. In this paper, we study the exact consensus problem in a new faulty link model, namely global asymmetric Byzantine (GAB) link model. Our link-fault model is simple, yet to our surprise, not studied before. In our system, all the nodes are fault-free and each pair of nodes can communicate directly with each other. In the GAB link model, up to f directed links may become Byzantine, and have arbitrary behavior. Non-faulty links deliver messages reliably. In our model, it is possible that the link from node a to node b is faulty, but the link from node b to node a is fault-free. Unlike some prior models with a local constraint, which enforced a local upper bound on the number of failure links attached to each node, we adopt the global constraint, which allows any link to be corrupted in the GAB model. These global and asymmetric features distinguish our model from all prior faulty link models. In our GAB model, we study the consensus problem in both synchronous and asynchronous systems. We show that 2f + 1 nodes is both necessary and sufficient for solving synchronous consensus, whereas 2f+2 nodes is the tight condition on resilience for solving asynchronous consensus. We also study the models where faulty links are mobile (or transient), i.e., the set of faulty links might change from round to round. We show that 2f + 3 nodes is necessary and sufficient for a family of algorithms that update local state in an iterative fashion.

Emulating a shared register can mask the intricacies of designing algorithms for asynchronous message-passing systems subject to crash failures, since it allows them to run algorithms designed for the simpler shared-memory model. Typically such emulations replicate the value of the register in multiple servers and require readers and writers to communicate with a majority of servers. The success of this approach for static systems, where the set of nodes (readers, writers, and servers) is fixed, has motivated several similar emulations for dynamic systems, where nodes may enter and leave. However, existing emulations need to assume that the system eventually stops changing for a long enough period or that the system size is bounded. This paper presents the first emulation of a register supporting any number of readers and writers in a crash-prone system that can withstand nodes continually entering and leaving and imposes no upper bound on the system size. The algorithm works as long as the number of nodes entering and leaving during a fixed time interval is at most a constant fraction of the system size at the beginning of the interval, and as long as the number of crashed nodes in the system is at most a constant fraction of the current system size. The paper includes a lower bound on the fraction of correct nodes that is strictly larger than the fraction sufficient to solve the problem in the static case.