No Arabic abstract
Events in distributed systems include sending or receiving messages, or changing some state in a node. Not all events are related, but some events can cause and influence how other, later events, occur. For instance, a reply to a received mail message is influenced by that message, and maybe by other prior messages also received. This article brings an introduction to classic causality tracking mechanisms and covers some more recent developments. The presentation is supported by a new graphical notation that allows an intuitive interpretation of the causality relations described.
Gradecast is a simple three-round algorithm presented by Feldman and Micali. The current work presents a very simple algorithm that utilized Gradecast to achieve Byzantine agreement. Two small variations of the presented algorithm lead to improved algorithms for solving the Approximate agreement problem and the Multi-consensus problem. An optimal approximate agreement algorithm was presented by Fekete, which supports up to 1/4 n Byzantine nodes and has message complexity of O(n^k), where n is the number of nodes and k is the number of rounds. Our solution to the approximate agreement problem is optimal, simple and reduces the message complexity to O(k * n^3), while supporting up to 1/3 n Byzantine nodes. Multi consensus was first presented by Bar-Noy et al. It consists of consecutive executions of l Byzantine consensuses. Bar-Noy et al., show an optimal amortized solution to this problem, assuming that all nodes start each consensus instance at the same time, a property that cannot be guaranteed with early stopping. Our solution is simpler, preserves round complexity optimality, allows early stopping and does not require synchronized starts of the consensus instances.
Many blockchain consensus protocols have been proposed recently to scale the throughput of a blockchain with available bandwidth. However, these protocols are becoming increasingly complex, making it more and more difficult to produce proofs of their security guarantees. We propose a novel permissionless blockchain protocol OHIE which explicitly aims for simplicity. OHIE composes as many parallel instances of Bitcoins original (and simple) backbone protocol as needed to achieve excellent throughput. We formally prove the safety and liveness properties of OHIE. We demonstrate its performance with a prototype implementation and large-scale experiments with up to 50,000 nodes. In our experiments, OHIE achieves linear scaling with available bandwidth, providing about 4-10 Mbps transaction throughput (under 8-20 Mbps per-node available bandwidth configurations) and at least about 20x better decentralization over prior works.
We present a model for a vacuum-like effective medium composed of the absorbing and gain media under the special designed parameters. Within the linear response theory, we prove that any pulse signal (with or without a discontinuity) through such a kind of vacuum-like effective media is always equal to the light speed in vacuum () without any distortion. As well known that the group velocity in anomalous or normal dispersive media may be smaller or larger than, or even become negative, but the discontinuous point always propagates at the velocity . Therefore we present some discussions on different definitions of the signals, based on the light pulses with a well-defined shape or with a sudden change, for trying to understand two possibilities for the signal velocity without violating the causality.
In this paper, we study local and global broadcast in the dual graph model, which describes communication in a radio network with both reliable and unreliable links. Existing work proved that efficient solutions to these problems are impossible in the dual graph model under standard assumptions. In real networks, however, simple back-off strategies tend to perform well for solving these basic communication tasks. We address this apparent paradox by introducing a new set of constraints to the dual graph model that better generalize the slow/fast fading behavior common in real networks. We prove that in the context of these new constraints, simple back-off strategies now provide efficient solutions to local and global broadcast in the dual graph model. We also precisely characterize how this efficiency degrades as the new constraints are reduced down to non-existent, and prove new lower bounds that establish this degradation as near optimal for a large class of natural algorithms. We conclude with a preliminary investigation of the performance of these strategies when we include additional generality to the model. These results provide theoretical foundations for the practical observation that simple back-off algorithms tend to work well even amid the complicated link dynamics of real radio networks.
Deep neural networks (deep learning) have emerged as a technology of choice to tackle problems in natural language processing, computer vision, speech recognition and gameplay, and in just a few years has led to superhuman level performance and ushered in a new wave of AI. Buoyed by these successes, researchers in the physical sciences have made steady progress in incorporating deep learning into their respective domains. However, such adoption brings substantial challenges that need to be recognized and confronted. Here, we discuss both opportunities and roadblocks to implementation of deep learning within materials science, focusing on the relationship between correlative nature of machine learning and causal hypothesis driven nature of physical sciences. We argue that deep learning and AI are now well positioned to revolutionize fields where causal links are known, as is the case for applications in theory. When confounding factors are frozen or change only weakly, this leaves open the pathway for effective deep learning solutions in experimental domains. Similarly, these methods offer a pathway towards understanding the physics of real-world systems, either via deriving reduced representations, deducing algorithmic complexity, or recovering generative physical models. However, extending deep learning and AI for models with unclear causal relationship can produce misleading and potentially incorrect results. Here, we argue the broad adoption of Bayesian methods incorporating prior knowledge, development of DL solutions with incorporated physical constraints, and ultimately adoption of causal models, offers a path forward for fundamental and applied research. Most notably, while these advances can change the way science is carried out in ways we cannot imagine, machine learning is not going to substitute science any time soon.