For some k > 0, the k-circle formation problem asks a swarm of autonomous mobile robots to form disjoint circles. Each such circle is restricted to be centered at one of the pre-fixed points given in the plane. Eac...
详细信息
For some k > 0, the k-circle formation problem asks a swarm of autonomous mobile robots to form disjoint circles. Each such circle is restricted to be centered at one of the pre-fixed points given in the plane. Each circle must contain exactly k robots at distinct positions. The k-circle formation problem has already been studied under one axis agreement. In this work, the robots are assumed to be completely disoriented, i.e., they neither have any agreement on a global coordinate system nor have any agreement on a common chirality. The robots are identical, anonymous, oblivious, and homogeneous. They operate in Look-Compute-Move cycles under a fair asynchronous scheduler. In this setting, all the initial configurations and values of k for which the k-circle formation problem is deterministically unsolvable have been characterized. A deterministic distributed algorithm has been proposed that deterministically solves the k-circle formation problem for the remaining configurations and values of k.
MapReduce frameworks allow programmers to write distributed, data-parallel programs that operate on multisets. These frameworks offer considerable flexibility to support various kinds of programs and data. To understa...
详细信息
MapReduce frameworks allow programmers to write distributed, data-parallel programs that operate on multisets. These frameworks offer considerable flexibility to support various kinds of programs and data. To understand the essence of the programming model better and to provide a rigorous foundation for optimizations, we present an abstract, functional model of MapReduce along with a number of customization options. We demonstrate that the MapReduce programming model can also represent programs that operate on lists, which differ from multisets in that the order of elements matters. Along with the functional model, we offer a cost model that allows programmers to estimate and compare the performance of MapReduce programs. Based on the cost model, we introduce two transformation rules aiming at performance optimization of MapReduce programs, which also demonstrates the usefulness of our model. In an exploratory study, we assess the impact of applying these rules to two applications. The functional model and the cost model provide insights at a proper level of abstraction into why the optimization works. Copyright (c) 2014 John Wiley & Sons, Ltd.
We present an adaptive how synchronization protocol that permits synchronized delivery of data to and from geographically distributed sites. Applications include inter-stream synchronization, synchronized delivery of ...
详细信息
We present an adaptive how synchronization protocol that permits synchronized delivery of data to and from geographically distributed sites. Applications include inter-stream synchronization, synchronized delivery of information in a multisite conference, and synchronization for concurrency control in distributed computations. The contributions of this protocol in the area of flow synchronization are the ability to synchronize over arbitrary topologies, the introduction of an adaptive synchronization delay, the flexibility to maintain multiple synchronization groups, and the use of a modular architecture that permits the application to tailor synchronization calculations to its service requirements. We take advantage of network protocols capable of maintaining network clock synchronization in the millisecond range.
Phylogenetic analysis is an area of computational biology concerned with the reconstruction of evolutionary relationships between organisms, genes, and gene families. Maximum likelihood evaluation has proven to be one...
详细信息
Phylogenetic analysis is an area of computational biology concerned with the reconstruction of evolutionary relationships between organisms, genes, and gene families. Maximum likelihood evaluation has proven to be one of the most reliable methods for constructing phylogenetic trees. The huge computational requirements associated with maximum likelihood analysis means that it is not feasible to produce large phylogenetic trees using a single processor. We have completed a fully cross platform coarse-grained distributed application, DPRml, which overcomes many of the limitations imposed by the current set of parallel phylogenetic programs. We have completed a set of efficiency tests that show how to maximise efficiency while using the program to build large phylogenetic trees. The software is publicly available under the terms of the GNU general public licence from the system webpage at http://***/distributed.
The authors present a study of the validation of a dependable local area network providing multipoint communication services based on an atomic multicast protocol. This protocol is implemented in specialized communica...
详细信息
The authors present a study of the validation of a dependable local area network providing multipoint communication services based on an atomic multicast protocol. This protocol is implemented in specialized communication servers, that exhibit the fail-silent property, i.e. a kind of halt-on-failure behavior enforced by self-checking hardware. The tests that have been carried out utilize physical fault injection and have two objectives: (1) to estimate the coverage of the self-checking mechanisms of the communication servers, and (2) to test the properties that characterize the service provided by the atomic multicast protocol in the presence of faults. The testbed that has been developed to carry out the fault-injection experiments is described, and the major results are presented and analyzed. It is concluded that the fault-injection test sequence has evidenced the limited performance of the self-checking mechanisms implemented on the tested NAC (network attachment controller) and justified (especially for the main board) the need for the improved self-checking mechanisms implemented in an enhanced NAC architecture using duplicated circuitry.< >
In this paper we investigate P systems whose compartments contain sets of symbol-objects rather than multisets of objects, as it is common in membrane computing. If the number of membranes cannot grow, then in this fr...
详细信息
In this paper we investigate P systems whose compartments contain sets of symbol-objects rather than multisets of objects, as it is common in membrane computing. If the number of membranes cannot grow, then in this framework we can characterize exactly the regular languages. If membrane creation or membrane division is allowed, then the Parikh sets of recursively enumerable languages can be generated. The last result also implies the universality of P systems with active membranes (with multisets of symbol-objects) without polarizations. (c) 2006 Elsevier B.V. All rights reserved.
Commit protocols have been proposed for use in a variety of concurrent-computing applications. The author has developed two condition sets that can help you determine when to use a commit protocol and when to avoid them.
Commit protocols have been proposed for use in a variety of concurrent-computing applications. The author has developed two condition sets that can help you determine when to use a commit protocol and when to avoid them.
The world-wide computing infrastructure on the growing computer network technology is a leading technology to make a variety of information services accessible through the Internet for every user from the high-perform...
详细信息
The world-wide computing infrastructure on the growing computer network technology is a leading technology to make a variety of information services accessible through the Internet for every user from the high-performance computing users through many of personal computing users. The important feature of such services is location transparency;information can be obtained irrespective of time or location in virtually shared manner. In this article, we overview Ninf, an ongoing global network-wide computing infrastructure project which allows users to access computational resources including hardware, software and scientific data distributed across a wide area network. Preliminary performance result on measuring software and network overhead is shown, and that promises the future reality of world-wide network computing. (C) 1999 Elsevier Science B.V. All rights reserved.
We consider distributed-memory parallel machines that support the FIFO delivery of messages among processors, and present an asynchronous distributed algorithm that ensures the FIFO delivery of messages among tasks th...
详细信息
We consider distributed-memory parallel machines that support the FIFO delivery of messages among processors, and present an asynchronous distributed algorithm that ensures the FIFO delivery of messages among tasks that migrate in such machines. For the concurrent migration of a set K of tasks, the algorithm requires O(nm(K)) interprocessor messages and O(n) time to run, where n is the number of processors in the system and m(K), is the number of pairs of communicating tasks involving the migrating tasks. However, for a great number of current distributed-memory architectures, these complexities can be reduced to O(m(K)) and O(1), respectively.
暂无评论