16727710
Semantics based transaction management techniques for replicated data
Data is often replicated in distributed database applications to improve availability and response time. Conventional multi-copy algorithms deliver fast response times and high availability for read-only transactions while sacrificing these goals for updates. In this paper, we propose a multi-copy algorithm that works well in both retrieval and update environments by exploiting special application semantics. By subdividing transactions into various categories, and utilizing a commutativity property, we demonstrate cheaper techniques and show that they guarantee correctness. A performance comparison between our techniques and conventional ones quantifies the extent of the savings.
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.
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>>
59757838
Operating System Support for Data Management.
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.
7308298
Data streaming algorithms for accurate and efficient measurement of traffic and flow matrices
The traffic volume between origin/destination (OD) pairs in a network, known as traffic matrix, is essential for efficient network provisioning and traffic engineering. Existing approaches of estimating the traffic matrix, based on statistical inference and/or packet sampling, usually cannot achieve very high estimation accuracy. In this work, we take a brand new approach in attacking this problem. We propose a novel data streaming algorithm that can process traffic stream at very high speed (e.g., 40 Gbps) and produce traffic digests that are orders of magnitude smaller than the traffic stream. By correlating the digests collected at any OD pair using Bayesian statistics, the volume of traffic flowing between the OD pair can be accurately determined. We also establish principles and techniques for optimally combining this streaming method with sampling, when sampling is necessary due to stringent resource constraints. In addition, we propose another data streaming algorithm that estimates flow matrix, a finer-grained characterization than traffic matrix. Flow matrix is concerned with not only the total traffic between an OD pair (traffic matrix), but also how it splits into flows of various sizes. Through rigorous theoretical analysis and extensive synthetic experiments on real Internet traffic, we demonstrate that these two algorithms can produce very accurate estimation of traffic matrix and flow matrix respectively.
28468806
Space-code bloom filter for efficient per-flow traffic measurement
Per-flow traffic measurement is critical for usage accounting, traffic engineering, and anomaly detection. Previous methodologies are either based on random sampling (e.g., Cisco's NetFlow), which is inaccurate, or only account for the "elephants". We introduce a novel technique for measuring per-flow traffic approximately, for all flows regardless of their sizes, at very high-speed (say, OC768). The core of this technique is a novel data structure called space code bloom filter (SCBF). A SCBF is an approximate representation of a multiset; each element in this multiset is a traffic flow and its multiplicity is the number of packets in the flow. The multiplicity of an element in the multiset represented by SCBF can be estimated through either of two mechanisms-maximum likelihood estimation (MLE) or mean value estimation (MVE). Through parameter tuning, SCBF allows for graceful tradeoff between measurement accuracy and computational and storage complexity. SCBF also contributes to the foundation of data streaming by introducing a new paradigm called blind streaming. We evaluate the performance of SCBF through mathematical analysis and through experiments on packet traces gathered from a tier-1 ISP backbone. Our results demonstrate that SCBF achieves reasonable measurement accuracy with very low storage and computational complexity
1151748
Scalable and Efficient Data Streaming Algorithms for Detecting Common Content in Internet Traffic
Recent research on data streaming algorithms has provided powerful tools to efficiently monitor various characteristics of traffic passing through a single network link or node. However, it is often desirable to perform data streaming analysis on the traffic aggregated over hundreds or even thousands of links/nodes, which will provide network operators with a holistic view of the network operation. Shipping raw traffic data to a centralized location (i.e., “raw aggregation”) for streaming analysis is clearly not a feasible approach for a large network. In this paper, we propose a set of novel distributed data streaming algorithms that allow scalable and efficient monitoring of aggregated traffic without the need for raw aggregation. Our algorithms target the specific network monitoring problem of finding common content in the Internet traffic traversing several nodes/links, which has applications in network-wide intrusion detection, early warning for fast propagating worms, and detection of hot objects and spam traffic. We evaluate our algorithms through extensive simulations and experiments on traffic traces collected from a tier-1 ISP. The experimental results demonstrate that our algorithms can effectively detect common content in the traffic traversing across a large network.
43715944
Performance Analysis and Scheduling of Stochastic Fork-Join Jobs in a Multicomputer System
The authors model a parallel processing system comprising several homogeneous computers interconnected by a communication network. Jobs arriving to this system have a linear fork-join structure. Each fork of the job gives rise to a random number of tasks that can be processed independently on any of the computers. Since exact analysis of fork-join models is known to be intractable, the authors resort to obtaining analytical bounds to the mean job response time of the fork-join job. For jobs with a single fork-join and, probabilistic allocation of tasks of the job to the N processors, they obtain upper and lower bounds to the mean job response time. Upper bounds are obtained using the concept of associated random variables and are found to be a good approximation to the mean job response time. A simple lower bound is obtained by neglecting queueing delays. They also find two lower bounds that include queueing delays. For multiple fork-join jobs, they study an approximation based on associated random variables. Finally, two versions of the join-the-shortest-queue (JSQ) allocation policy (i.e., JSQ by batch and JSQ by task) are studied and compared, via simulations and diffusion limits. >
1630993
Join-distinct aggregate estimation over update streams
There is growing interest in algorithms for processing andquerying continuous data streams (i.e., data that is seenonly once in a fixed order) with limited memory resources.Providing (perhaps approximate) answers to queries over suchstreams is a crucial requirement for many application environments;examples include large IP network installations where performancedata from different parts of the network needs to be continuouslycollected and analyzed.
The ability to estimate the number of distinct (sub)tuples inthe result of a join operation correlating two data streams (i.e.,the cardinality of a projection with duplicate elimination over ajoin) is an important requirement for several data-analysisscenarios. For instance, to enable real-time traffic analysis andload balancing, a network-monitoring application may need toestimate the number of distinct (<i>source</i>,destination) IP-address pairs occurring in the stream of IP packetsobserved by router <i>R</i><inf>1</inf>,where the source address is also seen in packets routed through adifferent router <i>R</i><inf>2</inf>.Earlier work has presented solutions to the individual problems ofdistinct counting and join-size estimation (without duplicateelimination) over streams. These solutions, however, arefundamentally different and extending or combining them to handleour more complex "Join-Distinct" estimation problem is far fromobvious. In this paper, we propose the <i>first</i>space-efficient algorithmic solution to the general Join-Distinctestimation problem over continuous data streams (our techniques canactually handle general <i>update streams</i>comprising tuple deletions as well as insertions). Our estimatorsare probabilistic in nature and rely on novel algorithms forbuilding and combining a new class of hash-based synopses (termed"JD <i>sketches</i>") for individual update streams. Wedemonstrate that our algorithms can provide low error,high-confidence Join-Distinct estimates using only small space andsmall processing time per update. In fact, we present lower boundsshowing that the space usage of our estimators is within smallfactors of the best possible for the Join-Distinct problem.Preliminary experimental results verify the effectiveness of ourapproach.