29316025
Optimizing the costs of hierarchical quorum consensus
We study the problem of how to minimize the cost of maintaining consistency among at least N copies of an object in an enviroment where the mix of read and write operations can vary. Quorum consensus requires that read and write operations must assemble appropriate quorums before an operation can succeed. The cost of an operation is proportional to the size of a quorum, and the objective is obviously to minimize the cost while still maintaining consistency. It is known that the quorum size can be reduced by organizing a number of copies into logical structures such as grids and hierarchies. In this paper, we show (a) how methods based on grids and hierarchies can be treated in a common framework, and (b) how these hierarchies can be optimized so as to minimize the cost of consensus. Of course, the optimal solution depends upon the mix of read and write operations that is present. Consequently, given N copies of an object and a ratio of write operations F, our algorithms determine the optimal values for the number of levels in the hierarchy and the read/write quorum sizes at each level. The algorithms, which run in O(N1.63) and O(N2) time, were tested, and the results are reported and discussed.
59757838
Operating System Support for Data Management.
45847616
EROICA: A Rule-Based Approach to Organizational Policy Management in Workflow Systems
Conventional workflow management systems have been criticized for being too rigid in dealing with changes in organizational policies, in particular for the lack of flexible mechanisms for handling complex role resolution. In this paper we describe a rule-based approach (EROICA) for managing organizational policies in workflow systems. Our approach extends the well-known ECA (event-condition-action) approach used in database systems by elevating roles, objects and time intervals to first class citizens, hence the term EROICA (event-role-object-interval-condition-action). In this paper, we focus on the development of a flexible role resolution mechanism that operates under various business constraints specified with EROICA rules. We further discuss the issues of architecture and implementation and demonstrate that the EROICA framework is promising in making next generation of workflow systems more powerful and flexible.
206778468
A performance study of general grid structures for replicated data
Recently, there has been considerable interest in the study of replica-control protocols which are based on organizing several copies of an object into logical structures, such as rectangular grids. In addition to high availability, another objective in exploiting such structures is to improve the degree of load sharing in a system. The authors extend the scope of grid structures to general grids, which allow holes in various positions of a rectangular structure and are useful to consider because they often produce availabilities that are higher than solid grids, where every position must be occupied by a node. In addition to proposing an improvement to the existing grid protocol, new insights are offered into the performance of the grids, from both availability and load sharing points of view. Algorithms for designing grids to maximize availability independently and also in conjunction with a load sharing constraint are given.<<ETX>>
14897390
Meta workflows as a control and coordination mechanism for exception handling in workflow systems
A higher level control and coordination mechanism is required for exception handling in workflow systems. This paper describes such a framework based on events, states, and a new kind of process called a meta workflow. Meta workflows have five kinds of meta activities and facilitate control over base workflows. We describe the framework and illustrate it with examples to show its features. The paper gives an architecture for incorporating it into existing workflows and also provides a formal semantics of execution. This framework can be used in Web services, supply chains, and inter-organizational applications where coordination requirements are complex, and flexible and adaptable workflows are needed. It is also useful for handling not just failure recovery but also various kinds of special situations, which arise frequently in web-based applications.
16012186
A fine-grained, controllable, user-to-user delegation method in RBAC
This paper addresses the issues surrounding user-to-user delegation in RBAC. We show how delegations can be incorporated into the RBAC model in a simple and straightforward manner. A special feature of the model is that it allows fine-grained control over what rights a user wishes to delegate as opposed to delegation at the role level where all the rights of a role must be delegated. In addition, the model provides a rich set of controls regarding further delegations of a right, generic constraints that further control delegations, and an innovative model for revocations. Properties of both delegation and revocation are discussed, and our work is compared with other related research.
23929618
Organelle DB: an updated resource of eukaryotic protein localization and function
Organelle DB () is a web-accessible relational database presenting a supplemented catalog of organelle-localized proteins and major protein complexes. Since its release in 2004, Organelle DB has grown by 20% to encompass over 30 000 proteins from 138 eukaryotic organisms. Each protein in Organelle DB is presented with its subcellular localization, primary sequence and a detailed description of its function, as available. All records in Organelle DB have been annotated using controlled vocabulary from the Gene Ontology consortium. Protein localization data are inherently visual, and Organelle DB is a significant repository of biological images, housing 1500 micrographs of yeast cells carrying stained proteins. Furthermore, we report here the development of Organelle View, an extension of Organelle DB for the interactive visualization of organelles and subcellular structures in the budding yeast Saccharomyces cerevisiae. Organelle View offers a dimensional representation of a yeast cell; users can search Organelle View for proteins of interest, and the organelles housing these proteins will be highlighted in the cell image. Among other applications, Organelle View may serve as an educational aid engaging introductory biology students through a visually ‘fun’ interface. Organelle View can be accessed from the Organelle DB home page or directly at .
2872380
Building Edge-Failure Resilient Networks
AbstractWe consider the design of resilient networks that are fault tolerant
 against link failures. Resilience against link failures can be built
 into the network by providing backup paths, which are used in
 the eventuality of an edge failure occurring on a primary path in the
 network. We consider several network design problems in this context;
 these problems are motivated by the requirements of current high-speed
 optical networks. In all the following problems the objective is to
 provide resilience in networks while minimizing the cost incurred.
 The main problem under consideration in this paper is that of backup
 allocation: this problem takes as its input an already provisioned 
 primary network and a parameter k, and allocates backup capacity 
 on the edges of the underlying network so that all the demand can be 
 routed even in the presence of k edge failures. We also consider a 
 variant of this problem where the primary network has a tree topology, 
 and it is required that the restored network retains a tree topology. 
 We then address the problem of simultaneous primary and backup
 allocation: we are given specifications of the traffic to be
 handled, and the goal is to provision both the primary as well as
 the backup network. Finally, we investigate a single-commodity
 problem motivated by a pragmatic scenario in which the primary
 network is not known in advance and demands between source--sink
 pairs arrive online.
8829443
Exploring the trade-off between label size and stack depth in MPLS routing
Multiprotocol label switching or MPLS technology is being increasingly deployed by several of the largest Internet service providers to solve problems such as traffic engineering and to offer IP services like virtual private networks (VPNs). In MPLS, the analysis of the packet (network layer) header is performed just once, and each packet is assigned a stack of labels, which is examined by subsequent routers when making forwarding decisions. Despite the fact that MPLS is becoming widespread on the Internet, we know essentially very little about the performance one can achieve with it, and about the intrinsic trade-offs in its use of resources. In this paper, we undertake a comprehensive study of the label size versus stack depth trade-off for MPLS routing protocols on lines and trees. We show that in addition to LSP tunneling, label stacks can also be used to dramatically reduce the number of labels required for setting up MPLS LSPs in a network. Based on this observation, we develop routing algorithms and prove lower bounds for two basic problems: (1) fixed label routing: given a fixed number of labels, we want to minimize the stack depth, and (2) fixed stack routing: given a bound on the stack depth, we want to minimize the number of labels used. Our simulation results validate our approach, demonstrating that our novel protocols enable MPLS routing on large trees with few labels and small stack sizes. Thus, our MPLS routing algorithms are applicable to a number of practical scenarios involving the provisioning of VPNs and multicast trees.
995281
Deterministic wavelet thresholding for maximum-error metrics
Several studies have demonstrated the effectiveness of the wavelet, decomposition as a tool for reducing large amounts of data down to compact, wavelet synopses that can be used to obtain fast, accurate approximate answers to user queries. While conventional wavelet synopses are based on greedily minimizing the overall root-mean-squared (i.e., L2-norm) error in the data approximation, recent work has demonstrated that such synopses can suffer from important problems, including severe bias and wide variance in the quality of the data reconstruction, and lack of non-trivial guarantees for individual approximate answers. As a result, probabilistic thresholding schemes have been recently proposed as a means of building wavelet synopses that try to probabilistically control other approximation-error metrics, such as the maximum relative error in data-value reconstruction, which is arguably the most important for approximate query answers and meaningful error guarantees.One of the main open problems posed by this earlier work is whether it is possible to design efficient deterministic wavelet-thresholding algorithms for minimizing non-L2 error metrics that are relevant to approximate query processing systems, such as maximum relative or maximum absolute error. Obviously, such algorithms can guarantee better wavelet synopses and avoid the pitfalls of probabilistic techniques (e.g., "bad" coin-flip sequences) leading to poor solutions. In this paper, we address this problem and propose novel, computationally efficient schemes for deterministic wavelet thresholding with the objective of optimizing maximum-error metrics. We introduce an optimal low polynomial-time algorithm for one-dimensional wavelet thresholding--our algorithm is based on a new Dynamic-Programming (DP) formulation, and can be employed to minimize the maximum relative or absolute error in the data reconstruction. Unfortunately, directly extending our one-dimensional DP algorithm to multi-dimensional wavelets results in a super-exponential increase in time complexity with the data dimensionality. Thus, we also introduce novel, polynomial-time approximation schemes (with tunable approximation guarantees for the target maximum-error metric) for deterministic wavelet thresholding in multiple dimensions.
1501195
On a bidirected relaxation for the MULTIWAY CUT problem
In the MULTIWAY CUT problem, we are given an undirected edge-weighted graph G = (V, E) with ce denoting the cost (weight) of edge e. We are also given a subset S of V, of size k, called the terminals. The objective is to find a minimum cost set of edges whose removal ensures that the terminals are disconnected.In this paper, we study a bidirected linear programming relaxation of MULTIWAY CUT. We resolve an open problem posed by Vazirani [Approximation Algorithms, first ed., Springer, Berlin, Heidelberg, 2001], and show that the integrality gap of this relaxation is not better than that for a geometric linear programming relaxation given by Calinescu et al. [J. Comput. System Sci. 60(3) (2000) 564-574], and may be strictly worse on some instances.