Many essential fundamental services for networked distributed systems (ad hoc, wireless or sensor) involve maintaining a global predicate over the entire network (defined by some invariance relation on the global stat...
详细信息
ISBN:
(纸本)9783540747413
Many essential fundamental services for networked distributed systems (ad hoc, wireless or sensor) involve maintaining a global predicate over the entire network (defined by some invariance relation on the global state of the network) by using local knowledge at each of the participating nodes. the participating nodes can no longer keep track of even a small fraction of the knowledge about the global network due to limited storage. We need a new paradigm of localized distributed algorithms, where a node takes simple actions based on local knowledge of only its immediate neighbors and yet the system achieves a global objective. Self-stabilization is a relatively new paradigm for designing such localized distributed algorithms for networks;it is an optimistic way of looking at system fault tolerance and scalable coordination;it provides a cost effective built-in safeguard against transient failures that might corrupt data in a distributed system. We introduce self-stabilizing protocol design withthe example of a total dominating set in a network graph and discuss some open problems.
the monitor construct has been implemented in several concurrent and/or parallel programming languages for shared-memory system environments, Extensions of the monitor to support process synchronization in distributed...
详细信息
ISBN:
(纸本)9783540747413
the monitor construct has been implemented in several concurrent and/or parallel programming languages for shared-memory system environments, Extensions of the monitor to support process synchronization in distributed systems have also been proposed. But, most existing work only provides the architecture design of the distributed monitor. there is no discussion about the algorithmic and implementation issues. Also, none of them consider how to implement conditional variables. In this paper, we present the design and implementation of a distributed monitor construct, named DisMoniC, for programming process synchronization in distributed systems. DisMoniC is generic in the sense that it can be used with any distributed mutual exclusion (DME) algorithm to implement exclusive access to the monitor operations. Time-efficient algorithms are proposed to implement conditional process synchronization in the distributed monitor. We also present performance evaluation of the proposed construct.
A coloring of a graph G=(V,E) is a partition of {V-1, V-2... V-k} of V into k independent sets called color classes. A vertex v is an element of V-i is called a Grundy vertex if it is adjacent to at least one vertex i...
详细信息
ISBN:
(纸本)9783540747413
A coloring of a graph G=(V,E) is a partition of {V-1, V-2... V-k} of V into k independent sets called color classes. A vertex v is an element of V-i is called a Grundy vertex if it is adjacent to at least one vertex in color class V-j, for every jthe partial Grundy coloring, every color class contains at least one Grundy vertex. Such a coloring gives a partitioning of the graph into clusters for which every cluster has a clusterhead (the Grundy vertex) adjacent to some other clusters. Such a decomposition is very interesting for large distributed systems and networks. In this paper, we propose a distributed algorithm to maintain the partial Grundy coloring of any graph G when an edge is added.
Recently superpeers are introduced to improve the performance of P2P systems. A superpeer is a node in a P2P system that operates as a server for a set of clients. By exploiting heterogeneity, the superpeer paradigm a...
详细信息
ISBN:
(纸本)9783540747413
Recently superpeers are introduced to improve the performance of P2P systems. A superpeer is a node in a P2P system that operates as a server for a set of clients. By exploiting heterogeneity, the superpeer paradigm allows P2P systems to run more efficiently. this paper proposes a hierarchy-adaptive P2P topology DAHP2P and a hierarchical routing, algorithm Hroute. Peers are grouped into clusters according to proximity and super peers form the upper-level overlay, the number of hierarchy is self-adaptively changed according to the number of nodes in the system, a hierarchical routing algorithm is designed to reduce the routing hops. Simulation results show that Hroute can significantly reduce the expected number of hops and latency of message routing, and loads of peers at different layers are relatively balanceable.
Traditional parallel schedulers running on cluster supercomputers support only static scheduling, where the number of processors allocated to an application remains fixed throughout the execution of the job. this resu...
详细信息
ISBN:
(纸本)9783540747413
Traditional parallel schedulers running on cluster supercomputers support only static scheduling, where the number of processors allocated to an application remains fixed throughout the execution of the job. this results in under-utilization of idle system resources thereby decreasing overall system throughput. In our research, we have developed a prototype framework called ReSHAPE, which supports dynamic resizing of parallel NIPI applications executing on distributed memory platforms. the resizing library in ReSHAPE includes support for releasing and acquiring processors and efficiently redistributing application state to a new set of processors. In this paper, we derive an algorithm for redistributing two-dimensional block-cyclic arrays from P to Q processors, organized as 2-D processor grids. the algorithm ensures a contention-free communication schedule for data redistribution if P-r <= Q(r) and P-c <= Q(c). In other cases, the algorithm implements circular row and column shifts on the communication schedule to minimize node contention.
作者：
Tian, DaxinLiu, YanhengLi, BinJilin Univ
Coll Comp Sci & Technol Changchun 130012 Peoples R China Jilin Univ
Key Lab Symbol Computat & Knowledge Engn Minist Educ Changchun 130012 Peoples R China Jilin Univ
Math Coll Changchun 130012 Peoples R China
One of the most challenging problems in anomaly detection is to develop scalable algorithms which are capable of dealing with large audit data, network traffic data, or alter data. In this paper a distributed neural n...
详细信息
ISBN:
(纸本)9783540747413
One of the most challenging problems in anomaly detection is to develop scalable algorithms which are capable of dealing with large audit data, network traffic data, or alter data. In this paper a distributed neural network based on Hebb rule is presented to improve the speed and scalability of inductive learning. the speed is improved by randomly splitting a large data set into disjoint subsets and each subset data is presented to an independent neural network, these networks can be trained in distributed and each one in parallel. the analysis of completeness and risk bounds of competitive Hebb learning proof that the distributed Hebb neural network can avoid the accuracy being degraded as compared to running a single algorithm withthe entire data. the experiments are performed on the KDD'99 Data set, which is a standard intrusion detection benchmark. Comparisons with other approaches on the same benchmark demonstrate the effectiveness and applicability of the proposed method.
Formal concept analysis has been successfully applied as a data mining framework whereby target patterns come in the form of intent families and implication bases. Since their extraction is a challenging task, especia...
详细信息
ISBN:
(纸本)9783540747413
Formal concept analysis has been successfully applied as a data mining framework whereby target patterns come in the form of intent families and implication bases. Since their extraction is a challenging task, especially for large datasets, parallel techniques should be helpful in reducing the computational effort and increasing the scalability of the approach. In this paper we describe a way to parallelize a recent divide-and-conquer method computing boththe intents and the Duquenne-Guiges implication basis of dataset. Wile intents admit a straightforward computation, adding the basis - whose definition is recursive poses harder problems, in particular, for parallel design. A first, and by no means final, solution relies on a partition of the basis that allows the crucial and inherently sequential step of redundancy removal to be nevertheless split into parallel subtasks. A prototype implementation of our method, called PARCIM, shows a nearly linear acceleration w.r.t. its sequential counter-part.
Some challenges in the mobile grid environments are not handled by some related works, for example, adapting to heterogeneous interfaces of different mobile devices (PDAs and cellular) for submission and monitoring of...
详细信息
ISBN:
(纸本)9783540747413
Some challenges in the mobile grid environments are not handled by some related works, for example, adapting to heterogeneous interfaces of different mobile devices (PDAs and cellular) for submission and monitoring of applications in grid environments. this article presents an approach that employs the workflow concept for providing automated and adapted features for executing applications in grid mobile configurations. the approach, coined as SuMMIT, enabled to consume less battery energy of PDAs and more agility for submitting and monitoring applications in comparison with some related works. In addition, the SuMMIT environment provides an execution flow adjustment, in case of disconnection, matching requirements of submitted application and options defined by the user. the SuMMIT also has adapted and optimized characteristics according to some limitations and problems found in different devices.
It is a challenging issue whether scientific applications are suitable for Imagine architecture. To address this problem, this paper presents a novel architecture-based optimization for the key techniques of mapping s...
详细信息
ISBN:
(纸本)9783540747413
It is a challenging issue whether scientific applications are suitable for Imagine architecture. To address this problem, this paper presents a novel architecture-based optimization for the key techniques of mapping scientific applications to Imagine. Our specific contributions include that we achieve fine kernel granularity and choose necessary arrays to organize appropriate streams. Specially, we develop a new stream program generation algorithm based on the architecture-based optimization. We implement our algorithm to some representative scientific applications on ISIM simulation of Imagine, compared the corresponding FORTRAN programs running on Itanium 2. the experimental results show that the optimizing stream programs can efficiently improve computational intensiveness, enhance locality of LRF and SRF, avoid index stream overhead and enable parallelism to utilize ALUs. It is certain that Imagine is efficient for many scientific applications.
暂无评论