Probabilistic, or randomized, algorithms are fast becoming as commonplace as conventional deterministic algorithms. This survey presents five techniques that have been widely used in the design of randomized algorithm...
详细信息
Probabilistic, or randomized, algorithms are fast becoming as commonplace as conventional deterministic algorithms. This survey presents five techniques that have been widely used in the design of randomized algorithms. These techniques are illustrated using 12 randomized algorithms-both sequential and distributed-that span a wide range of applications, including: primality testing (a classical problem in number theory), universal hashing (choosing the hash function dynamically and at random), interactive probabilistic proof systems (a new method of program testing), dining philosophers (a classical problem in distributed computing), and Byzantine agreement (reaching agreement in the presence of malicious processors). Included with each algorithm is a discussion of its correctness and its computational complexity. Several related topics of interest are also addressed, including the theory of probabilistic automata, probabilistic analysis of conventional algorithms, deterministic amplification, and derandomization of randomized algorithms. Finally, a comprehensive annotated bibliography is given.
In this study, we investigate the problem of accelerating distributed algorithms for solving linear equations over multi-agent networks. While almost all distributed algorithms in the literature assume that the equati...
详细信息
In this study, we investigate the problem of accelerating distributed algorithms for solving linear equations over multi-agent networks. While almost all distributed algorithms in the literature assume that the equations are not shared with the neighboring agents, it is shown that the assumption is not restrictive, and an algorithm has been proposed which can be used to determine the equations of the neighbors. We also present a numerical example to illustrate that the convergence rate of a distributed algorithm can be significantly improved by using the proposed algorithm.
A wireless sensor network consists of a large number of small, resource-constrained devices and usually operates in hostile environments that are prone to link and node failures. Computing aggregates such as average, ...
详细信息
A wireless sensor network consists of a large number of small, resource-constrained devices and usually operates in hostile environments that are prone to link and node failures. Computing aggregates such as average, minimum, maximum and sum is fundamental to various primitive functions of a sensor network, such as system monitoring, data querying, and collaborative information processing. In this paper, we present and analyze a suite of randomized distributed algorithms to efficiently and robustly compute aggregates. Our distributed Random Grouping (DRG) algorithm is simple and natural and uses probabilistic grouping to progressively converge to the aggregate value. DRG is local and randomized and is naturally robust against dynamic topology changes from link/node failures. Although our algorithm is natural and simple, it is nontrivial to show that it converges to the correct aggregate value and to bound the time needed for convergence. Our analysis uses the eigenstructure of the underlying graph in a novel way to show convergence and to bound the running time of our algorithms. We also present simulation results of our algorithm and compare its performance to various other known distributed algorithms. Simulations show that DRG needs far fewer transmissions than other distributed localized schemes.
This paper proposes an approach to the specification and model checking of a large, important class of distributed algorithms called control algorithms (CAs), which are superimposed on underlying distributed systems (...
详细信息
This paper proposes an approach to the specification and model checking of a large, important class of distributed algorithms called control algorithms (CAs), which are superimposed on underlying distributed systems (UDSs). The approach is based on rewriting logic by moving from its object level to the meta-level. We introduce the idea of specifying CAs as meta-programs that take the specifications of UDSs and automatically generate the specifications of the UDSs on which the CAs are superimposed (UDS-CAs). Due to many options, such as network topologies, even fixing the number of each kind of entities, such as mobile support stations (MSSs) and mobile hosts (MHs) in a mobile checkpointing algorithm, there are many instances of a UDS. To address the problem, we generate all possible initial states of a UDS for a fixed number of each kind of entities such that some constraints, such as MSSs strongly connected with a wired network, are fulfilled and conduct model checking for each of the initial states. We demonstrate the usefulness by reporting on a case study where a counterexample is found for some specific initial states but not for the other initial states, detecting a subtle flaw lurking in a mobile checkpointing algorithm.
This paper concerns a number of algorithmic problems on graphs and how they may be solved in a distributed fashion. The computational model is such that each node of the graph is occupied by a processor which has its ...
详细信息
This paper concerns a number of algorithmic problems on graphs and how they may be solved in a distributed fashion. The computational model is such that each node of the graph is occupied by a processor which has its own ID. Processors are restricted to collecting data from others which are at a distance at most t away from them in t time units, but are otherwise computationally unbounded. This model focuses on the issue of locality in distributed processing, namely, to what extent a global solution to a computational problem can be obtained from locally available data. Three results are proved within this model: A 3-coloring of an n-cycle requires time-OMEGA(log* n). This bound is tight, by previous work of Cole and Vishkin. Any algorithm for coloring the d-regular tree of radius r which runs for time at most 2r/3 requires at least OMEGA(square-root d) colors. In an n-vertex graph of largest degree-DELTA, an O(DELTA(2))-coloring may be found in time O(log* n).
Previous studies of program visualization have generally failed to provide convincing support for the benefits of algorithm animation in promoting the understanding of computations. This paper presents a study in whic...
详细信息
Previous studies of program visualization have generally failed to provide convincing support for the benefits of algorithm animation in promoting the understanding of computations. This paper presents a study in which the use of program visualization resulted in significantly better understanding of a distributed computation. Understanding was measured in terms of the number of correct responses to questions about the algorithm. The environment used in this study differs from that of previous studies in a number of aspects: it combines the use of distributed algorithm visualization, 3D visualization, and legends. In addition, the design of both the experiment and animation focuses on reducing cognitive noise.
Proving the correctness of distributed algorithms in dynamic networks is a hard task due to the time complexity and the highly dynamic behavior. In the literature, the existing solutions lack a consensus about their d...
详细信息
Proving the correctness of distributed algorithms in dynamic networks is a hard task due to the time complexity and the highly dynamic behavior. In the literature, the existing solutions lack a consensus about their developments and their proofs. Moreover, the proofs which have been presented are done manually. In this paper, we propose a reuse based approach for specifying and proving distributed algorithms in dynamic networks. It consists in developing a formal pattern using Event-B method, based on refinement techniques. The proposed pattern allows to handle topological events in dynamic networks and to characterize the concept of time. Our solution relies on evolving graphs as a powerful model to record the evolution of a network topology. To illustrate it, we present an example of a distributed counting algorithm. The proof statistics related to the development of the pattern and the algorithm show the efficiency of our solution.
Designing, tuning, and analyzing the performance of distributed algorithms and protocols are complex tasks. A major factor that contributes to this complexity is the fact that there is no single environment to support...
详细信息
ISBN:
(纸本)0769509517
Designing, tuning, and analyzing the performance of distributed algorithms and protocols are complex tasks. A major factor that contributes to this complexity is the fact that there is no single environment to support all phases of the development of a distributed algorithm. This paper presents Neko, an easy to use Java platform that provides a uniform and extensible environment for the various phases of algorithm design and performance evaluation: prototyping, tuning, simulation, deployment, etc.
The paper presents a proposed co-simulation platform for a realistic validation of distributed algorithms in smart grid with the integration of the multi-agent system. The platform uses a master framework called MOSAI...
详细信息
ISBN:
(数字)9781728152004
ISBN:
(纸本)9781728152011
The paper presents a proposed co-simulation platform for a realistic validation of distributed algorithms in smart grid with the integration of the multi-agent system. The platform uses a master framework called MOSAIK to manage and schedule all related simulators. A cyber-physical system is created for the operation. The physical system is a real-time simulator of the power grid; meanwhile, the cyber system is a cluster of independent agents with sparse communication. The Alternating direction method of multiplier (ADMM) for distributed optimal power flow is introduced and conducted to show the effectiveness of the proposed approach.
暂无评论