Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userStateless Computation
62
0
0.0
(
0
)
Added by
Adva Zair
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We present and explore a model of stateless and self-stabilizing distributed computation, inspired by real-world applications such as routing on todays Internet. Processors in our model do not have an internal state, but rather interact by repeatedly mapping incoming messages (labels) to outgoing messages and output values. While seemingly too restrictive to be of interest, stateless computation encompasses both classical game-theoretic notions of strategic interaction and a broad range of practical applications (e.g., Internet protocols, circuits, diffusion of technologies in social networks). We embark on a holistic exploration of stateless computation. We tackle two important questions: (1) Under what conditions is self-stabilization, i.e., guaranteed convergence to a legitimate global configuration, achievable for stateless computation? and (2) What is the computational power of stateless computation? Our results for self-stabilization include a general necessary condition for self-stabilization and hardness results for verifying that a stateless protocol is self-stabilizing. Our main results for the power of stateless computation show that labels of logarithmic length in the number of processors yield substantial computational power even on ring topologies. We present a separation between unidirectional and bidirectional rings (L/poly vs. P/poly), reflecting the sequential nature of computation on a unidirectional ring, as opposed to the parallelism afforded by the bidirectional ring. We leave the reader with many exciting directions for future research.
rate research
Read More
Mass surveillance of the population by state agencies and corporate parties is now a well-known fact. Journalists and whistle-blowers still lack means to circumvent global spying for the sake of their investigations. With Spores, we propose a way for journalists and their sources to plan a posteriori file exchanges when they physically meet. We leverage on the multiplication of personal devices per capita to provide a lightweight, robust and fully anonymous decentralised file transfer protocol between users. Spores hinges on our novel concept of e-squads: ones personal devices, rendered intelligent by gossip communication protocols, can provide private and dependable services to their user. Peoples e-squads are federated into a novel onion routing network, able to withstand the inherent unreliability of personal appliances while providing reliable routing. Spores performances are competitive, and its privacy properties of the communication outperform state of the art onion routing strategies.
In public distributed ledger technologies (DLTs), such as Blockchains, nodes can join and leave the network at any time. A major challenge occurs when a new node joining the network wants to retrieve the current state of the ledger. Indeed, that node may receive conflicting information from honest and Byzantine nodes, making it difficult to identify the current state. In this paper, we are interested in protocols that are stateless, i.e., a new joining node should be able to retrieve the current state of the ledger just using a fixed amount of data that characterizes the ledger (such as the genesis block in Bitcoin). We define three variants of stateless DLTs: weak, strong, and probabilistic. Then, we analyze this property for DLTs using different types of consensus.
The continuous increase in performance requirements, for both scientific computation and industry, motivates the need of a powerful computing infrastructure. The Grid appeared as a solution for inexpensive execution of heavy applications in a parallel and distributed manner. It allows combining resources independently of their physical location and architecture to form a global resource pool available to all grid users. However, grid environments are highly unstable and unpredictable. Adaptability is a crucial issue in this context, in order to guarantee an appropriate quality of service to users. Migration is a technique frequently used for achieving adaptation. The objective of this report is to survey the problem of strong migration in heterogeneous environments like the grids, the related implementation issues and the current solutions.
A critical challenge for modern system design is meeting the overwhelming performance, storage, and communication bandwidth demand of emerging applications within a tightly bound power budget. As both the time and power, hence the energy, spent in data communication by far exceeds the energy spent in actual data generation (i.e., computation), (re)computing data can easily become cheaper than storing and retrieving (pre)computed data. Therefore, trading computation for communication can improve energy efficiency by minimizing the energy overhead incurred by data storage, retrieval, and communication. This paper hence provides a taxonomy for the computation vs. communication trade-off along with quantitative characterization.
We introduce the Adaptive Massively Parallel Computation (AMPC) model, which is an extension of the Massively Parallel Computation (MPC) model. At a high level, the AMPC model strengthens the MPC model by storing all messages sent within a round in a distributed data store. In the following round, all machines are provided with random read access to the data store, subject to the same constraints on the total amount of communication as in the MPC model. Our model is inspired by the previous empirical studies of distributed graph algorithms using MapReduce and a distributed hash table service. This extension allows us to give new graph algorithms with much lower round complexities compared to the best known solutions in the MPC model. In particular, in the AMPC model we show how to solve maximal independent set in $O(1)$ rounds and connectivity/minimum spanning tree in $O(loglog_{m/n} n)$ rounds both using $O(n^delta)$ space per machine for constant $delta < 1$. In the same memory regime for MPC, the best known algorithms for these problems require polylog $n$ rounds. Our results imply that the 2-Cycle conjecture, which is widely believed to hold in the MPC model, does not hold in the AMPC model.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
