اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدStore-Collect in the Presence of Continuous Churn with Application to Snapshots and Lattice Agreement
47
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We present an algorithm for implementing a store-collect object in an asynchronous crash-prone message-passing dynamic system, where nodes continually enter and leave. The algorithm is very simple and efficient, requiring just one round trip for a store operation and two for a collect. We then show the versatility of the store-collect object for implementing churn-tolera
قيم البحث
اقرأ أيضاً
We study expansion and information diffusion in dynamic networks, that is in networks in which nodes and edges are continuously created and destroyed. We consider information diffusion by {em flooding}, the process by which, once a node is informed,
it broadcasts its information to all its neighbors. We study models in which the network is {em sparse}, meaning that it has $mathcal{O}(n)$ edges, where $n$ is the number of nodes, and in which edges are created randomly, rather than according to a carefully designed distributed algorithm. In our models, when a node is born, it connects to $d=mathcal{O}(1)$ random other nodes. An edge remains alive as long as both its endpoints do. If no further edge creation takes place, we show that, although the network will have $Omega_d(n)$ isolated nodes, it is possible, with large constant probability, to inform a $1-exp(-Omega(d))$ fraction of nodes in $mathcal{O}(log n)$ time. Furthermore, the graph exhibits, at any given time, a large-set expansion property. We also consider models with {em edge regeneration}, in which if an edge $(v,w)$ chosen by $v$ at birth goes down because of the death of $w$, the edge is replaced by a fresh random edge $(v,z)$. In models with edge regeneration, we prove that the network is, with high probability, a vertex expander at any given time, and flooding takes $mathcal{O}(log n)$ time. The above results hold both for a simple but artificial streaming model of node churn, in which at each time step one node is born and the oldest node dies, and in a more realistic continuous-time model in which the time between births is Poisson and the lifetime of each node follows an exponential distribution.
We present an approach for efficiently taking snapshots of the state of a collection of CAS objects. Taking a snapshot allows later operations to read the value that each CAS object had at the time the snapshot was taken. Taking a snapshot requires a
constant number of steps and returns a handle to the snapshot. Reading a snapshotted value of an individual CAS object using this handle is wait-free, taking time proportional to the number of successful CASes on the object since the snapshot was taken. Our fast, flexible snapshots yield simple, efficient implementations of atomic multi-point queries on concurrent data structures built from CAS objects. For example, in a search tree where child pointers are updated using CAS, once a snapshot is taken, one can atomically search for ranges of keys, find the first key that matches some criteria, or check if a collection of keys are all present, simply by running a standard sequential algorithm on a snapshot of the tree. To evaluate the performance of our approach, we apply it to two search trees, one balanced and one not. Experiments show that the overhead of supporting snapshots is low across a variety of workloads. Moreover, in almost all cases, range queries on the trees built from our snapshots perform as well as or better than state-of-the-art concurrent data structures that support atomic range queries.
In the Lattice Agreement (LA) problem, originally proposed by Attiya et al. cite{Attiya:1995}, a set of processes has to decide on a chain of a lattice. More precisely, each correct process proposes an element $e$ of a certain join-semi lattice $L$ a
nd it has to decide on a value that contains $e$. Moreover, any pair $p_i,p_j$ of correct processes has to decide two values $dec_i$ and $dec_j$ that are comparable (e.g., $dec_i leq dec_j$ or $dec_j < dec_i$). LA has been studied for its practical applications, as example it can be used to implement a snapshot objects cite{Attiya:1995} or a replicated state machine with commutative operations cite{Faleiro:2012}. Interestingly, the study of the Byzantine Lattice Agreement started only recently, and it has been mainly devoted to asynchronous systems. The synchronous case has been object of a recent pre-print cite{Zheng:aa} where Zheng et al. propose an algorithm terminating in ${cal O}(sqrt f)$ rounds and tolerating $f < lceil n/3 rceil$ Byzantine processes. In this paper we present new contributions for the synchronous case. We investigate the problem in the usual message passing model for a system of $n$ processes with distinct unique IDs. We first prove that, when only authenticated channels are available, the problem cannot be solved if $f=n/3$ or more processes are Byzantine. We then propose a novel algorithm that works in a synchronous system model with signatures (i.e., the {em authenticated message} model), tolerates up to $f$ byzantine failures (where $f<n/3$) and that terminates in ${cal O}(log f)$ rounds. We discuss how to remove authenticated messages at the price of algorithm resiliency ($f < n/4$). Finally, we present a transformer that converts any synchronous LA algorithm to an algorithm for synchronous Generalised Lattice Agreement.
An immediate snapshot object is a high level communication object, built on top of a read/write distributed system in which all except one processes may crash. It allows a process to write a value and obtain a set of values that represent a snapshot
of the values written to the object, occurring immediately after the write step. Considering an $n$-process model in which up to $t$ processes may crash, this paper introduces first the $k$-resilient immediate snapshot object, which is a natural generalization of the basic immediate snapshot (which corresponds to the case $k=t=n-1$). In addition to the set containment properties of the basic immediate snapshot, a $k$-resilient immediate snapshot object requires that each set returned to a process contains at least $(n-k)$ pairs. The paper first shows that, for $k,t<n-1$, $k$-resilient immediate snapshot is impossible in asynchronous read/write systems. %Then the paper investigates the space of objects that %are impossible to solve in $n$-process $t$-crash read/write systems. Then the paper investigates a model of computation where the processes communicate with each other by accessing $k$-immediate snapshot objects, and shows that this model is stronger than the $t$-crash model. Considering the space of $x$-set agreement problems (which are impossible to solve in systems such that $xleq t$), the paper shows then that $x$-set agreement can be solved in read/write systems enriched with $k$-immediate snapshot objects for $x=max(1,t+k-(n-2))$. It also shows that, in these systems, $k$-resilient immediate snapshot and consensus are equivalent when $1leq t<n/2$ and $tleq kleq (n-1)-t$. Hence, %thanks to the problem map it provides, the paper establishes strong relations linking fundamental distributed computing objects (one related to communication, the other to agreement), which are impossible to solve in pure read/write systems.
In this work, we consider distributed agreement tasks in microbial distributed systems under stochastic population dynamics and competitive interactions. We examine how competitive exclusion can be used to solve distributed agreement tasks in the mic
robial setting. To this end, we develop a new technique for analyzing the time to reach competitive exclusion in systems with two competing species under biologically realistic population dynamics. We use this technique to analyze a protocol that exploits competitive interactions to solve approximate majority consensus efficiently in microbial systems. To corroborate our analytical results, we use computer simulations to show that these consensus dynamics occur within practical time scales.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
