Assume that each vertex of an arbitrary n-vertex tree T is assigned a nonnegative integer weight. this paper considers partitioning the vertices of tree T into p disjoint clusters such that the total weight of each cl...
详细信息
ISBN:
(纸本)9780769548791
Assume that each vertex of an arbitrary n-vertex tree T is assigned a nonnegative integer weight. this paper considers partitioning the vertices of tree T into p disjoint clusters such that the total weight of each cluster is at least l and at most u, where l and u are given integers with lthms for trees only allow that a cluster corresponds to a subtree, our algorithm also considers clusters containing several subtrees as long as these subtrees have the same parent node or their root vertices are adjacent siblings. We call this [l, u] sibling partitioning. We deal with two problems of [l, u] sibling partitioning for a given tree: the minimal partition problem is to find an [l, u] sibling partitioning withthe minimum number of clusters;the p-partition problem is to find an [l, u] sibling partitioning with a given number p of clusters. In this paper, we present the first polynomial-time algorithm to solve the two problems.
Explicit model-checking (MC) is a classical solution to find flaws in a security protocol. But it is well-known that for non trivial protocols, MC may enumerate state-spaces of astronomical sizes-the famous state-spac...
详细信息
ISBN:
(纸本)9780769548791
Explicit model-checking (MC) is a classical solution to find flaws in a security protocol. But it is well-known that for non trivial protocols, MC may enumerate state-spaces of astronomical sizes-the famous state-space explosion problem. distributed model checking is a solution but complex and subject to bugs: a MC can validate a model but miss an invalid state. In this paper, we focus on using a verification condition generator that takes annotated distributed algorithms and ensures their termination and correctness. We study five algorithms (one sequential and four distributed where three of them are dedicated and optimised for security protocol) of state-space construction as a first step towards mechanised verification of distributed model-checkers.
Capabilities are a more scalable and adaptive access control approach compared withthe conventional approaches such as ACLs, due to their being held and managed by users or agents in systems, but not the middleware. ...
详细信息
ISBN:
(纸本)9780769548791
Capabilities are a more scalable and adaptive access control approach compared withthe conventional approaches such as ACLs, due to their being held and managed by users or agents in systems, but not the middleware. this feature makes capabilities more suitable in distributed environments that have dynamic populations. Treaties have been proposed to enhance the capability approach by introducing sequences of actions, such that treaties can capture characteristics of behaviours, and provide finer control over accesses. However there is a new problem brought by the behaviour modeling of treaties which is called duplication problem, which concerns preventing users from gaining unauthorised behaviour by duplicating treaties. In this paper we discuss this problem and propose three models of treaty systems that aim to solve the duplication problem.
Energy consumption has increasingly become a serious problem in contemporary data centers. the electricity bill contributes a significant fraction of the Total Cost of Ownership (TCO), and it has been predicted to inc...
详细信息
ISBN:
(纸本)9780769548791
Energy consumption has increasingly become a serious problem in contemporary data centers. the electricity bill contributes a significant fraction of the Total Cost of Ownership (TCO), and it has been predicted to increase at an even faster pace in the following years. In an attempt to reduce the energy consumption in cloud infrastructures, we propose REST, an energy-efficient cloud storage built upon an open source cluster-based object store similar to GFS. It achieves high energy-efficiency by cleverly exploiting the redundancy and its asymmetric accesses existing in the system without compromising inherent well-established mechanisms, while maintaining reasonable performance level. By slightly altering the data-layout policy, REST can safely keep a large amount of redundant storage nodes in standby mode or even powered off most of the time. Deploying a sophisticated real-time workload monitor, it provides flexibility to power up standby or powered down nodes to accommodate the variations in workloads. In addition, trade-offs between energy and performance can be conveniently made by simply adjusting a trade-off metric in REST. the FileBench experimental results have demonstrated that power savings can be as high as 29%, still providing comparable or even better performance.
this paper presents a message passing interface called MATRIX for the MPMD(Multiple Program Multiple Data) type parallel application running on a distributed network. the proposed interface provides network abstractio...
详细信息
ISBN:
(纸本)9781467331104
this paper presents a message passing interface called MATRIX for the MPMD(Multiple Program Multiple Data) type parallel application running on a distributed network. the proposed interface provides network abstraction and peer-to-peer message transfer method to the application layer. the interface is designed to have scalability for a large-scale application. the concurrent application established on the proposed interface can be applied to a heterogeneous distributed network composed of multi-architectures and multi-OS machines. this paper describes the concepts, protocols and implementations of the message passing interface. Additionally, we present the remote file transfer and execution protocol called FTXP for large-scale applications on the message passing interface. For the verification of the proposed methods, we present an example of parallel application applied to a surveillance robot system composed of multi-architecture and multi-OS.
Commodity multi-core SMPs may generate an enormous amount of coherency traffic. However, the impact of coherence traffic and snoop filtering on parallel program scalability has not attracted sufficient attention. We e...
详细信息
ISBN:
(纸本)9780769547497
Commodity multi-core SMPs may generate an enormous amount of coherency traffic. However, the impact of coherence traffic and snoop filtering on parallel program scalability has not attracted sufficient attention. We experimentally analyze the shared data access patterns of four typical applications having different memory layout. An OpenMp optimized execution model is derived for each application with emphasis on data dependencies and implied coherence messages. Using an 8-core SMP we present the obtained speedups versus change in the number of cores and problem scale. A discussion of potential limitation on scalability due to the application or SMP is presented. To assess the coherence behavior and its impact on scalability of parallel programs, a synthetic benchmark which alternates the data block ownership among two cores of the same or different processors is presented. It is found that coherence overheads including snoop filtering are responsible of significant limitation on parallel program scalability. For 8-core SMPs, speedup can be reduced by factors of 2.5 and 5 for row-major and column-major access patterns as compared to the use of private data, respectively. A truly parallel coherence protocol implementation is needed to provide truly scalable shared-memory model.
Enterprise Service Bus (ESB) is an SOA-based software architecture for business application integration in distributed and heterogeneous environments. Most of open-source or commercial solutions offer the same set of ...
详细信息
ISBN:
(纸本)9781467347754;9781467347730
Enterprise Service Bus (ESB) is an SOA-based software architecture for business application integration in distributed and heterogeneous environments. Most of open-source or commercial solutions offer the same set of basic services such as message transformation, message routing, security, etc... however, none of them take advantage of the multicore/multiprocessor technologies which make possible the massively parallel processing. this work concerns performance evaluation of a massively parallel ESB oriented architecture (denoted MPAB). After a brief description of its main components, we present the results of this evaluation based on operational analysis.
In this paper, we study the dependency between MapReduce configuration parameters and network load of fixed-size MapReduce jobs during the shuffle phase;then we propose an analytical method to model this dependency. O...
详细信息
ISBN:
(纸本)9780769548791
In this paper, we study the dependency between MapReduce configuration parameters and network load of fixed-size MapReduce jobs during the shuffle phase;then we propose an analytical method to model this dependency. Our approach consists of three key phases: profiling, modeling, and prediction. In the first stage, an application is run several times with different sets of MapReduce configuration parameters (here number of map tasks and number of reduce tasks) to profile the network load of an application in the shuffle phase on a given cluster. then, the relation between these parameters and the network load is modeled by multivariate linear regression. For evaluation, three applications (WordCount, Exim Mainlog parsing, and TeraSort) are utilized to evaluate our technique on a 5-node MapReduce private cluster.
Group checkpointing is a fix between global checkpointing and log-based recovery. It features both reduced runtime overhead and localized recovery effect for improving the fault-tolerance performance of large-scale di...
详细信息
ISBN:
(纸本)9780769548791
Group checkpointing is a fix between global checkpointing and log-based recovery. It features both reduced runtime overhead and localized recovery effect for improving the fault-tolerance performance of large-scale distributed systems. However, parallel programs cannot efficiently benefit from this strategy, as they often involve synchronous or semi-synchronous interactions that incur extra idling delays between processes as well as between process groups. this paper presents an analytical study on such delays and the corresponding delay optimization strategies. Observing that certain parallel programs exhibit patterns of "synchronization groups", we develop a Synchronization-Induced Checkpoint protocol that manages checkpoints around such groups. the protocol keeps advantages of ordinary group checkpointing, and meanwhile minimizes the costs of synchronization-induced delays. We also broadly categorize the known synchronization patterns and establish their relations with suitable checkpoint strategies for parallel programs.
Adiabatic quantum computation has been proposed as quantum parallel processing with adiabatic evolution by using a superposition state to solve combinatorial optimization problem, then it has been applied to many prob...
详细信息
ISBN:
(纸本)9780769548791
Adiabatic quantum computation has been proposed as quantum parallel processing with adiabatic evolution by using a superposition state to solve combinatorial optimization problem, then it has been applied to many problems like satisfiability problem. Among them, Deutsch and Deutsch-Jozsa problems have been tried to be solved by using adiabatic quantum computation. In this paper, we modify the adiabatic quantum computation and propose to solve Bernstein-Vazirani problem more efficiently by a method with higher observation probability.
暂无评论