We introduce and investigate a distributed computation model for querying the Web. Web queries are computed by interacting automata running at different nodes in the Web. The automata which we are concerned with can b...
详细信息
ISBN:
(纸本)9781581135077
We introduce and investigate a distributed computation model for querying the Web. Web queries are computed by interacting automata running at different nodes in the Web. The automata which we are concerned with can be viewed as register automata equipped with an additional communication component. We identify conditions necessary and sufficient for systems of automata to compute Web queries, and investigate the computational power of such systems.
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...
ISBN:
(纸本)9781581134858
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 bipartite network under composite atomicity. These results represent significant progress in the area of distributed algorithms for matchings.
Protecting agents from host attacks is a pressing security concern in networked environments supporting mobile agents. In this paper, we consider a black hole: a highly harmful host that disposes of visiting agents up...
详细信息
ISBN:
(纸本)9781581134858
Protecting agents from host attacks is a pressing security concern in networked environments supporting mobile agents. In this paper, we consider a black hole: a highly harmful host that disposes of visiting agents upon their arrival, leaving no observable trace of such a destruction. The task to identify the location of the harmful host is clearly dangerous for the searching agents. We study under what conditions and at what cost a team of autonomous asynchronous mobile agents can successfully accomplish this task; we are concerned with solutions that are generic (i.e., topology-independent). We study the size of the optimal solution (i.e., the minimum number of agents needed to locate the black hole), and the cost of the minimal solution (i.e., the number of moves performed by the agents executing a size-optimal solution protocol). We establish tight bounds on size and cost depending on the a priori knowledge the agents have about the network, and on the consistency of the local labellings. In particular, we prove that: with topological ignorance Δ + 1 agents are needed and suffice, and the cost is Θ(n2), where Δ is the maximal degree of a node and n is the number of the nodes in the network; with topological ignorance but in presence of sense of direction only two agents suffice and the cost is Θ(n2); and with complete topological knowledge only two agents suffice and the cost is Θ(n log n). All the upper-bound proofs are constructive.
The proceedings contains 43 papers. Topics discussed include distributedcomputing, time complexity, concurrent distributed queuing, quorum systems probes, abstraction, cone-based distributed topology control algorith...
详细信息
The proceedings contains 43 papers. Topics discussed include distributedcomputing, time complexity, concurrent distributed queuing, quorum systems probes, abstraction, cone-based distributed topology control algorithm, hybrid mix networks and semantic reasoning.
Leslie Lamport was the first to pose many of the fundamental questions about synchronization that drive much of our community's research, even today. In this paper, we revisit some of Lamport's classic questio...
详细信息
Leslie Lamport was the first to pose many of the fundamental questions about synchronization that drive much of our community's research, even today. In this paper, we revisit some of Lamport's classic questions in a modern context. In particular, we consider some of the implications.
An adding network is a distributed data structure that supports a concurrent, lock-free, low-contention implementation of a fetch&add counter. We give a lower bound showing that adding networks have inherently hig...
详细信息
An adding network is a distributed data structure that supports a concurrent, lock-free, low-contention implementation of a fetch&add counter. We give a lower bound showing that adding networks have inherently high latency. We prove that our lower bound is tight.
Mutual exclusion is a topic that Leslie Lamport has returned to many times throughout his career. This article, which is being written in celebration of Lamport's sixtieth birthday, is an attempt to survey some of...
详细信息
Mutual exclusion is a topic that Leslie Lamport has returned to many times throughout his career. This article, which is being written in celebration of Lamport's sixtieth birthday, is an attempt to survey some of his many contributions to research on this topic.
distributed queuing is a fundamental problem in distributedcomputing, arising in a variety of applications. The challenge in designing a distributed queuing algorithm is to minimize message traffic and delay. This pa...
详细信息
ISBN:
(纸本)9781581133837
distributed queuing is a fundamental problem in distributedcomputing, arising in a variety of applications. The challenge in designing a distributed queuing algorithm is to minimize message traffic and delay. This paper gives a novel competitive analysis of the Arrow distributed queuing protocol under concurrent access. We analyze the combined latency of r simultaneously requests, and derive a competitive ratio of s · log r, where s is the stretch of a preselected spanning tree in the network. Our analysis employs a novel greedy characterization of the way the Arrow protocol orders concurrent requests, and yields a new lower bound on the quality of the nearest-neighbor heuristic for the Traveling Salesperson Problem.
We present a mix network that achieves efficient integration of public-key and symmetric-key operations. This hybrid mix network is capable of natural processing of arbitrarily long input elements, and is fast in both...
详细信息
ISBN:
(纸本)9781581133837
We present a mix network that achieves efficient integration of public-key and symmetric-key operations. This hybrid mix network is capable of natural processing of arbitrarily long input elements, and is fast in both practical and asymptotic senses. While the overhead in the size of input elements is linear in the number of mix servers, it is quite small in practice. In contrast to previous hybrid constructions, ours has optimal robustness, that is, robustness against any minority coalition of malicious servers.
暂无评论