On Dynamic Distributed Computing

Details On Dynamic Distributed Computing On Dynamic Distributed Computing

2012-02-14

arxiv.org/abs/1202.3084v1

Computer Science

Distributed, Parallel, and Cluster Computing

Scientific paper

The history of distributed computing is strongly tied to the assumption of a static network composed predominantly of honest nodes. Yet, modern distributed systems not only are dynamic but exhibit a high level of churn. This paper sets the ground to achieve distributed computing in a highly dynamic environment despite the presence of an adversary controlling a large fraction of the nodes. Somewhat surprisingly, we prove that it is possible to efficiently maintain clusters of nodes with a majority of honest ones in each, within a system whose size can vary polynomially compared to its initial size. Dealing with such a highly dynamic setting was an open problem in distributed computing. Our construction provides a basic abstraction enabling for the first time several types of distributed coordination in a highly dynamic setting, such as peer sampling, broadcast, agreement and aggregation. In a nutshell, we are the first to achieve dynamic clustering with a low complexity, namely with a communication cost induced by each node arrival or departure that is polylogarithmic, with respect to $N$, the maximal size of the system, and this in presence of a static Byzantine adversary controlling a fraction $\bad \leq \frac{1}{2l^2}-\epsilon$ of the nodes (for some fixed constants $l>\sqrt 2$ and $\epsilon > 0$, independent of $N$). The clusters maintained are of size $O(\log^2 N)$, and all contain a majority of honest nodes with high probability. Our approach built on two algorithms: NOW (for Neighbors On Watch), which preserves the desired properties of the partition in the presence of high churn (up to a polynomial increase and decrease of the number of nodes), and OVER (for Over-Valued Erd\"os-R\'enyi graph), which maintains an overlay with high expansion coefficient and low degree on the graph of clusters.

Affiliated with

Also associated with

No associations

Rating

On Dynamic Distributed Computing does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Dynamic Distributed Computing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Dynamic Distributed Computing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-90040