The Global Data Computation (GDC) problem in the asynchronous distributedcomputing model where processes are prone to crash failures is addressed. A protocol that solves this problem in an asynchronous distributed sy...
详细信息
The Global Data Computation (GDC) problem in the asynchronous distributedcomputing model where processes are prone to crash failures is addressed. A protocol that solves this problem in an asynchronous distributed system where processes can crash, but equipped with a perfect failure detector is presented. The most important property of the proposed protocol lies in its time optimality.
The development of algorithms with guaranteed work efficiency for any pattern of fragmentations and merges of the underlying network is addressed. Current results are discussed for the abstract setting where asynchron...
详细信息
The development of algorithms with guaranteed work efficiency for any pattern of fragmentations and merges of the underlying network is addressed. Current results are discussed for the abstract setting where asynchronous processors start performing tasks in isolation and where an adversary can force an arbitrary pattern of merges. Following a merge, processors are able to share their knowledge about the computational progress prior to the merge.
Assignment-based partitioning is proposed as a way to partition the monitoring work among the Condition Evaluators (CEs). In particular, each update is delivered to a subset of the N CEs, while assigned to a single CE...
详细信息
Assignment-based partitioning is proposed as a way to partition the monitoring work among the Condition Evaluators (CEs). In particular, each update is delivered to a subset of the N CEs, while assigned to a single CE among them. When a new update arrives at a particular CE, a quick assigment test is performed first. If an update has not been assigned to this CE, it can be processed very quickly. In this way, each CE is only responsible for those updates assigned to it, and overall its work is reduced to a fraction of the centralized case.
Finding a maximal or maximum matching in a graph is a well-understood problem for which efficient sequential algorithms exist. Applications of matchings in distributed settings make it desirable to find self-stabilizi...
详细信息
Finding a maximal or maximum matching in a graph is a well-understood problem for which efficient sequential algorithms exist. Applications of matchings in distributed settings make it desirable to find self-stabilizing asynchronous distributed solutions to these problems. We first present a self-stabilizing algorithm for finding a maximal matching in a general anonymous network under read/write atomicity with linear round complexity. This is followed by a self-stabilizing algorithm, with quadratic time complexity, for finding a maximum matching in a biparite network under composite atomicity. These results represent significant progress in the area of distributed algorithms for matchings.
The set of conditions that allow to solve the interactive consistency problem, denoted CB_IC, in the presence of fc crashes and fe erroneous proposals are characterized. Those are the conditions including input vector...
详细信息
The set of conditions that allow to solve the interactive consistency problem, denoted CB_IC, in the presence of fc crashes and fe erroneous proposals are characterized. Those are the conditions including input vectors such that their Hamming is at least 2fe+fc+1. A CB_IC protocol for the shared memory systems is also introduced. This protocol establishes a connection relating consensus, interactive consistency and error-correcting codes.
We present GS3, a distributed, scalable, self-configuration and self-healing algorithm for multi-hop wireless networks. The algorithm enables network nodes in a 2D plane to configure themselves into a cellular hexagon...
详细信息
We present GS3, a distributed, scalable, self-configuration and self-healing algorithm for multi-hop wireless networks. The algorithm enables network nodes in a 2D plane to configure themselves into a cellular hexagonal structure such that cells have tightly bounded geographic radius and low overlap between neighboring cells. The structure is self-healing under various perturbations, such as node joins, leaves, deaths, movements, and state corruptions. For instance, it slides as a whole if nodes in many cells die at the same rate. Moreover, its configuration and healing are scalable in three respects: first, local knowledge enables each node to maintain only limited information with respect to a constant number of nearby nodes;second, local healing guarantees that all perturbations are contained within a tightly bounded region with respect to the perturbed area and dealt with in a one-way message diffusion time across the region;third, only local coordination is needed in both configuration and self-healing.
We consider the following problem, which arises in the context of distributed Web computations. An aggregator aims to combine specific data from n sources. The aggregator contacts all sources at once. The time for eac...
详细信息
We consider the following problem, which arises in the context of distributed Web computations. An aggregator aims to combine specific data from n sources. The aggregator contacts all sources at once. The time for each source to return its data to the aggregator is independent and identically distributed according to a known distribution. The aggregator at some point stops waiting for data and returns an answer depending only on the data received so far. If the aggregator returns the aggregated information from k of the n sources at time t it obtains a reward Rk(t) that grows with k and decreases with t. The goal of the aggregator is to maximize its expected reward. We prove that for certain broad families of distributions and broad classes of reward functions, the optimal plan for the aggregator has a simple form and hence can be easily computed.
In this paper, we give a theoretical analysis of peer-to-peer (P2P) networks operating in the face of concurrent joins and unexpected departures. We focus on Chord, a recently developed P2P system that implements a di...
详细信息
In this paper, we give a theoretical analysis of peer-to-peer (P2P) networks operating in the face of concurrent joins and unexpected departures. We focus on Chord, a recently developed P2P system that implements a distributed hash table abstraction, and study the process by which Chord maintains its distributed state as nodes join and leave the system. We argue that traditional performance measures based on run-time are uniformative for a continually running P2P network, and that the rate at which nodes in the network need to participate to maintain system state is a more useful metric. We give a general lower bound on this rate for a network to remain connected, and prove that an appropriately modified version of Chord's maintenance rate is within a logarithmic factor of the optimum rate.
This paper presents a decentralized, peer-to-peer web cache called Squirrel. The key idea is to enable web browsers on desktop machines to share their local caches, to form an efficient and scalable web cache, without...
详细信息
This paper presents a decentralized, peer-to-peer web cache called Squirrel. The key idea is to enable web browsers on desktop machines to share their local caches, to form an efficient and scalable web cache, without the need for dedicated hardware and the associated administrative cost. We propose and evaluate decentralized web caching algorithms for Squirrel, and discover that it exhibits performance comparable to a centralized web cache in terms of hit ratio, bandwidth usage and latency. It also achieves the benefits of decentralization, such as being scalable, self-organizing and resilient to node failures, while imposing low overhead on the participating nodes.
We present energy efficient algorithms for leader election in single channel single-hop radio networks with no collision detection. We present a deterministic solution with sublogarithmic energy cost (the best previou...
详细信息
ISBN:
(纸本)9781581134858
We present energy efficient algorithms for leader election in single channel single-hop radio networks with no collision detection. We present a deterministic solution with sublogarithmic energy cost (the best previous result was O(log n)) and show a double logarithmic lower bound. We prove that this lower bound holds in a randomized case, in a certain sense. For the case, when the number n of active stations can be approximated in advance, we show a randomized algorithm with energy consumption O(log* n) that yields a result with high probability (the best previous result was O(log log n)).
暂无评论