In 2004, Klavins et al. introduced the use of graph grammars to describe-and to program-systems of self-assembly. It turns out that these graph grammars can be embedded in a graph rewriting characterization of distrib...
详细信息
ISBN:
(纸本)9781605583969
In 2004, Klavins et al. introduced the use of graph grammars to describe-and to program-systems of self-assembly. It turns out that these graph grammars can be embedded in a graph rewriting characterization of distributed systems that was proposed by Degano and Montanari over twenty years ago. By applying techniques obtained from this observation, we prove a generalized version of Soloveichik and Winfree's theorem on local determinism. We also obtain a canonical method to simulate asynchronous constant-size-message-passing models of distributedcomputing with systems of self-assembly.
Routing topologies for distributed hashing in peer-to-peer networks are classified into two categories: deterministic and randomized. A general technique for constructing deterministic routing topologies is presented....
详细信息
ISBN:
(纸本)9781581137088
Routing topologies for distributed hashing in peer-to-peer networks are classified into two categories: deterministic and randomized. A general technique for constructing deterministic routing topologies is presented. Using this technique, classical parallel interconnection networks can be adapted to handle the dynamic nature of participants in peer-to-peer networks. A unified picture of randomized routing topologies is also presented. Two new protocols are described which improve average latency as a function of out-degree. One of the protocols can be shown to be optimal with high probability. Finally, routing networks for distributed hashing are revisited from a systems perspective and several open design problems are listed.
This paper presents a general methodology for building message-passing peer-to-peer systems capable of performing prefix search for arbitrary user-defined names. Our methodology allows to achieve even load distributio...
详细信息
ISBN:
(纸本)9781581137088
This paper presents a general methodology for building message-passing peer-to-peer systems capable of performing prefix search for arbitrary user-defined names. Our methodology allows to achieve even load distribution, high fault-tolerance, and low-congestion concurrent query execution. This is the first known peer-to-peer system for prefix search with such properties. The essence of this methodology is a plug and play paradigm for designing a peer-to-peer system as a modular composition of arbitrary concurrent data structures.
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.
We introduce a distributed algorithm for clock synchronization in sensor networks. Our algorithm assumes that nodes in the network only know their immediate neighborhoods and an upper bound on the network's diamet...
详细信息
We introduce a distributed algorithm for clock synchronization in sensor networks. Our algorithm assumes that nodes in the network only know their immediate neighborhoods and an upper bound on the network's diameter. Clock-synchronization messages are only sent as part of the communication-assumed to be reasonably frequent-that already takes place among nodes. The algorithm has the gradient property of [R. Fan, N. Lynch, Gradient clock synchronization, distributedcomputing 18 (2006) 255-266], achieving an O(1) worst-case skew between the logical clocks of neighbors. The algorithm's actions are such that no constant lower bound exists on the rate at which logical clocks progress in time, and for this reason the lower bound of [R. Fan, N. Lynch, Gradient clock synchronization, distributedcomputing 18 (2006) 255-266;L Meier, L Thiele, Brief announcement: Gradient clock synchronization in sensor networks, in: proceedings of the twenty-Fourth annual ACM symposium on principles of distributedcomputing, 2005, p. 238] that forbids a constant clock skew between neighbors does not apply. (C) 2008 Elsevier Inc. All rights reserved.
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.
Quorum systems serve as a basic tool providing a uniform and reliable way to achieve coordination in a distributed system. They are used for distributed and replicated databases, name servers, mutual exclusion, and di...
详细信息
Quorum systems serve as a basic tool providing a uniform and reliable way to achieve coordination in a distributed system. They are used for distributed and replicated databases, name servers, mutual exclusion, and distributed access control and signatures. Traditionally, two basic methods have used to evaluate quorum systems: the first is the analytical approach. The second approach is simulation. This paper proposes an empirical approach to evaluate systems. The results of the evaluation are presented.
This paper introduces two consistency criteria, causal consistency and causal serializability, in the context of systems composed of sequential processes that execute transactions. Causal consistency is the weaker cri...
详细信息
This paper introduces two consistency criteria, causal consistency and causal serializability, in the context of systems composed of sequential processes that execute transactions. Causal consistency is the weaker criterion: in addition to the sequentiality on transactions issued by each process, it considers only dependency on transactions due to a read-from relation. The second criterion, causal serializability, lies between causal consistency and serializability and is a consistency criterion strong enough to satisfy a wide range of applications.
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.
暂无评论