Many activities in business process management, such as process retrieval, process mining, and process integration, need to determine the similarity between business processes. Along with many other relational behavior semantics, Transition Adjacency Relation (abbr. TAR) has been proposed as a kind of behavioral gene of process models and a useful perspective for process similarity measurement. In this article we explain why it is still relevant and necessary to improve TAR or pTAR (i.e., projected TAR) computation efficiency and put forward a novel approach for TAR computation based on Petri net unfolding. This approach not only improves the efficiency of TAR computation, but also enables the long-expected combined usage of TAR and Behavior Profiles (abbr. BP) in process model similarity estimation.

Sharing process models on the web has emerged as a common practice. Users can collect and share their experimental process models with others. However, some users always feel confused about the shared process models for lack of necessary guidelines or instructions. Therefore, several process translators have been proposed to explain the semantics of process models in natural language (NL). We find that previous studies suffer from information loss and generate semantically erroneous descriptions that diverge from original model behaviors. In this paper, we propose a novel process translator named BePT (Behavior-based Process Translator) based on the encoder-decoder paradigm, encoding a process model into a middle representation and decoding the representation into NL descriptions. Our theoretical analysis demonstrates that BePT satisfies behavior correctness, behavior completeness and description minimality. The qualitative and quantitative experiments show that BePT outperforms the state-of-the-art baselines.

There is a growing interest in socio-technical networks that encompass people, process and technology. They capture connections among technical artifacts and human resources. Existing studies have shown that social networks among resources that collaborate to work on a business process instance have

An adaptive process management system (APMS) allows for flexible, dynamic, and even ad hoc adaptation of processes based on case data, context, and events. These processes may arise in various domains such as business, healthcare, etc. In knowledge-intensive environments, it is important that APMS technology ensures error-free process execution and compliance with semantic constraints. However, most process design tools handle only syntactic constraints. This restricts their value in real-world applications considerably. This paper proposes a novel approach to check the compliance of process models against semantic constraints and the validity of process change operations using mixed-integer programming (MIP). The MIP formulation allows us to describe existential, dependency, ordering, and various other relationships among tasks along with business policies in a standard way. In addition to incorporating the semantic constraint specifications into an MIP formulation, we introduce three novel ideas in this paper: (1) the notion of degree of compliance of processes to constraints based on a penalty function, (2) the concepts of full and partial validity of change operations, and (3) the idea of compliance by compensation. Thus, compensation operations derived from compliance degree can transform a noncompliant process into a compliant one both at design and execution time. We illustrate our approach in the context of a healthcare workflow as a way to reduce medical errors and argue that it is more elegant and superior to a pure logic-based approach. Complex scenarios with multiple concurrent processes (and constraints across them) for a single patient are also considered.

Engaging patients in the management of their health care can improve the quality of their care and enhance their experience while making more efficient use of care provider resources, especially for chronic diseases. However, health care system complexity and the challenge of consumer health literac

In recent years, many algorithms have been proposed to extract process models from process execution logs. The process models describe the ordering relationships between tasks in a process in terms of standard constructs like sequence, parallel, choice, and loop. Most algorithms assume that each trace in a log represents a correct execution sequence based on a model. In practice, logs are often noisy, and algorithms designed for correct logs are not able to handle noisy logs. In this paper we share our key insights from a study of noise in process logs both real and synthetic. We found that all process logs can be explained by a block-structured model with two special self-loop and optional structures, making it trivial to build a fully accurate process model for any given log, even one with inaccurate data or noise present in it. However, such a model suffers from low quality. By controlling the use of self-loop and optional structures of tasks and blocks of tasks, we can balance the quality and accuracy trade-off to derive high-quality process models that explain a given percentage of traces in the log. Finally, new quality metrics and a novel quality-based algorithm for model extraction from noisy logs are described. The results of the experiments with the algorithm on real and synthetic data are reported and analyzed at length.

Current approaches for service adaptation focus on either the message interface aspect or the control flow interface aspect separately. Our work recognizes that message adaptation may affect control flow adaptation and vice versa in complex ways. Hence an integrated approach is necessary. We propose a framework for integration and identify a set of extendible message adaptation patterns to solve typical message mismatches. In addition we give an algorithm for generating new message adapter on the fly so as to integrate control flow considerations into message adaptation. Finally we show how these individual patterns can be combined by another algorithm to create a complete adapter for two processes. The advantages of our method are illustrated with a case study. We present the design of a prototype and show XSLT code for implementing the message transformation.

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 finegrained 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.

This paper presents a pair of role-based access control models for workflow systems, collectively known as the W-RBAC models. The first of these models, W0-RBAC is based on a framework that couples a powerful RBAC-based permission service and a workflow component with clear separation of concerns for ease of administration of authorizations. The permission service is the focus of the work, providing an expressive logic-based language for the selection of users authorized to perform workflow tasks, with preference ranking. W1-RBAC extends the basic model by incorporating exception handling capabilities through controlled and systematic overriding of constraints.

XRL (eXchangeable Routing Language) is an instance-based workflow language that uses XML for the representation of process definitions and Petri nets for its semantics. Since XRL is instance-based, workflow definitions can be changed on-the-fly and sent across organizational boundaries. These features are vital for today's dynamic and networked economy. However, the features also enable subtle, but highly disruptive, cross-organizational errors. On-the-fly changes and one-of-a-kind processes are destined to result in errors. Moreover, errors of a cross-organizational nature are difficult to repair. In this paper, we show soundness properties of XRL constructs by using a novel constructive approach. We also describe a software tool based on XML and Petri-net technologies for verifying XRL workflows.

Recently there has been a resurgence of interest in quorum-based methods for maintaining consistency of a group of replicated servers as a way to achieve load balancing in addition to high availability. We describe a SuperGrid protocol that performs well for small number of items (less than 100) and evaluate its performance analytically and through simulation experiments. Although it has been shown that it is possible to construct quorum systems where the load is O(1//spl radic/N) and the availability is exp(-/spl Omega/(/spl radic/N)), these asymptotic results do not perform very well when the number of items is relatively small. In such cases, our results show that the Supergrid protocol outperforms the recent Crumbling Walls protocol and the Paths system. It is also simple and easy to implement.

There are several well-known techniques for knowledge discovery such as neural networks, discriminant analysis, etc. This article compares the forecasting accuracy of five models (two parametric and three nonparametric) and proposes composite (or hybrid) methods based on combining the individual methods. Basically, a composite classifier makes use of “trained” models whose “expertise” is combined to obtain an optimal classifier. All the methods are illustrated and evaluated using marketing data related to the problem of deciding whether a supermarket should carry a new product. All methods except one performed considerably better on predicting the reject decision accurately than the accept decision. However, when hybrid methods were devised and tested, the performance on “accept” decisions improved dramatically, while the overall performance was almost the same as before. Moreover, no pure method dominated any of the four hybrid methods. We also performed a cost analysis to show that, depending upon the ratio of the costs of Type 1 and Type 2 errors, the hybrid methods could outperform all the pure methods in terms of total profit for the supermarket.

We describe a randomized, fully distributed algorithm for distributed consensus and evaluate its performance assuming probabilistically bounded message delay. Each node randomly contacts a few other nodes and incorporates their values into its own value. All the nodes are able to reach consensus in this manner after a few rounds. The results show that the randomized algorithm is flexible, efficient and robust, and offers several advantages over a deterministic algorithm.

This paper describes a fast, reliable, scalable and efficient broadcast protocol called HPP (hierarchical propagation protocol) for weak-consistency replica management. It is based on organizing the nodes in a network into a logical hierarchy and maintaining a limited amount of state information at each node. It ensures that messages are not lost due to failures or partitions and minimizes redundancy. Furthermore, the protocol allows messages to be diffused while nodes are down provided the parent and child nodes of a failed node are alive. Moreover, the protocol allows nodes to be moved in the logical hierarchy and the network to be restructured dynamically in order to improve performance, while still ensuring that no messages are lost while the switch takes place and without disturbing normal operation. A performance study of the protocol in terms of availability and propagation delay indicates that the protocol reduces the delay by a factor of four compared to a protocol that does not diffuse messages past failed nodes.

Geographical Information Systems (GIS) involve the manipulation of large spatial data sets, and the performance of these systems is often determined by how these data sets are organized on secondary storage (disk). This paper describes a simulation study investigating the performance of two non-recursive spatial clustering methods the Inverted Naive and the Spiral methods in extensive detail and comparing them with the Hilbert fractal method that has been shown in previous studies to outperform other recursive clustering methods. The paper highlights the importance of analysing the sample variance when evaluating the relative performance of various spatial ordering methods. The clustering performance of the methods is examined in terms of both the mean and variance values of the number of clusters (runs of consecutive disk blocks) that must be accessed to retrieve a query region of a given size and orientation. The results show that, for a blocking factor of 1, the mean values for the Spiral method are the best, and on average, about 30% better than for the other two methods. In terms of variance, the inverted naive method is the best followed by the Spiral and Hilbert methods, in that order. We also study the impact of varying query size and the skew ratio (between the X and Y dimensions) for each method. While these performance results do not generalize for higher blocking factors, we believe that they are useful for both researchers and practitioners to know because several previous studies have also examined this special case, and also because it has important implications for the performance of GIS applications.

The authors study the quorumcasting problem which is a generalization of multicasting. While multicasting consists of sending a message to a select group of m nodes in a system of n nodes, quorumcasting sends a message to any q out of these m nodes. The need to communicate with an arbitrary q-subset of a predefined set arises in many distributed applications, such as distributed synchronization and updating a replicated resource. Two straightforward solutions are to send the message to individual members one at a time until q members have responded and to use multicasting to deliver the message to all members. The former solution will have excessive delay and the latter can cause congestion in nodes and/or in the network. The solutions proposed here use a minimum cost tree spanning a q-subset. By choosing an appropriate set of q nodes, the communications cost can be minimized. They present several heuristics to find low cost solutions for the quorumcast routing problem and evaluate the heuristics by comparing their solutions with exact solutions obtained from enumerating the solution space. The heuristic solutions are also compared with "random" solutions, where the q quorum sites are selected at random, and then the problem is treated like a multicast. The results of their tests show that the heuristics compare favorably with the optimal solutions, and that the random solutions perform rather poorly in comparison with the heuristics.>

The author describes an efficient data structure called the G-tree (or grid tree) for organizing multidimensional data. The data structure combines the features of grids and B-trees in a novel manner. It also exploits an ordering property that numbers the partitions in such a way that partitions that are spatially close to one another in a multidimensional space are also close in terms of their partition numbers. This structure adapts well to dynamic data spaces with a high frequency of insertions and deletions, and to nonuniform distributions of data. We demonstrate that it is possible to perform insertion, retrieval, and deletion operations, and to run various range queries efficiently using this structure. A comparison with the BD tree, zkdb tree and the KDB tree is carried out, and the advantages of the G-tree over the other structures are discussed. The simulated bucket utilization rates for the G-tree are also reported.>

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.>

High availabilityof data is clearly a very important goal in a distributed system.Most previous studies have concentrated on the unconstrained maximization of availability, disregarding communications costs.Here we model this problem as one of minimizing commumcations costs subject to availability constraints.Two models for such constrained optimization are presented: The first characterizes availability deterministically, while the second one does so probabilistitally.Other simpler models that are special cases of these two basic models and that arise from making simplifying assumptions such as equal vote values or constant intersite communications costs are also discussed.We describe a semi-exhaustive algorithm and efficient heuristics for solving each model.The algorithms utilize a novel signature-based method for identifying equivalent vote combinations, and an efficient procedure for computing availability.Computational results for the various algorithms are also given.

A randomized algorithm for vote assignment is described. Given a collection of sites where copies of a file are replicated, and the individual site reliabilities, the algorithm assigns votes to sites so as to maximize overall availability. It is based on the concept of simulated annealing which has been successfully applied for various complex problems (for instance, the traveling salesman problem) for which no efficient optimal algorithm is known. The authors tested their algorithm for 5-, 6-, 7-, 8-, and 9-site examples and compared the vote assignments produced by it with those produced by an optimal algorithm based on solving an integer programming model. The results produced by the randomized algorithm were remarkably close to those produced by the optimal one.>

A novel algorithm for managing replicated data is presented. The proposed method is based on organizing the copies of an object into a logical, multilevel hierarchy, and extending the quorum consensus algorithm to such an environment. Several properties of the method are derived and optimality conditions are given for minimizing the quorum size. It is shown that, given a collection of n copies of an object, the method allows a quorum to be formed with n/sup 0.63/ copies versus ((n+1)/2) copies in the case of the majority voting algorithm. Tradeoffs between the proposed method and three other quorum-based methods are discussed, and the main features of each method are highlighted.>

A class of algorithms for synchronizing a large number of identical copies of an object is described, and its performance is evaluated. The method is based on organizing a group of objects into a multilevel hierarchy and extending the quorum consensus algorithm to such an environment. The performance of the algorithm is compared, in terms of availability and message cost, with that of two other methods, majority voting and dynamic voting using a simulation model. Although the author's method uniformly outperforms the other two methods in terms of average message cost, no single method is found to dominate in terms of availability. The conditions under which each method performs well are identified.>

Three issues in the context of escrow-based methods, are addressed. It is shown that full serializability can be guaranteed for escrow transactions by means of repeat semantics, that is, a transaction which fails is rerun in a special mode. The author describes a crash recovery protocol consistent with the concurrency control scheme used. An analysis is made, by means of a simulation model, of several different borrowing policies for escrow transactions and the best one is identified.>

Many algorithms for replicated data concurrency control are based on voting methods. Techniques are developed for optimizing the assignment of votes in an environment where intersite communications costs are nonuniform and individual site reliabilities vary. These techniques apply to all algorithms that are based on voting. Availability is considered as a realistic measure of reliability, and so is incorporated in an optimization model. The optimization model is based on minimizing communications costs subject to a given availability constraint. A semi-exhaustive algorithm is described for solving this model. The algorithm utilizes a signature-based method for identifying equivalent vote combinations and an efficient technique for computing availability. It is compared to an equal vote assignment to estimate the extent of possible savings in communications costs.>

Results of a previous comparison study (A. Kumar and M. Stonebraker, 1987) between a conventional transaction manager and an operating system (OS) transaction manager indicated that the OS transaction manager incurs a severe performance penalty and appears to be feasible only in special circumstances. Three approaches for enhancing the performance of an OS transaction manager are considered. The first strategy is to improve performance by reducing the cost of lock acquisition and by compressing the log. The second strategy explores the possibility of still further improvements from additional semantics to be built into an OS transaction system. The last strategy is to use a modified index structure that makes update operations less expensive to perform. The results show that the OS will have to implement essentially all of the specialized tactics for transaction management that are currently used by a database management system (DBMS) in order to match DBMS performance.>

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.

Abstract Survivability of a node vulnerable network is often assessed in terms of the (node) connectivity of the graph that represents the logical topology of the network. When the damage causing events have widespread impact then, owing to the physical layout of the network facilities, each event can destroy several nodes. As a survivability measure, therefore, we define the generalized connectivity as the minimum number of events (rather than the minimum number of node removals) required to disconnect the network. To model the possible effects of damage causing events, we introduce the notion of a dependence graph on the nodes of the network and a set of admissible cliques in this graph. Nodes that are nonadjacent in the dependence graph are independent, i. e., they cannot be damaged by the same event, and each event destroys an admissible clique of nodes. We present techniques for calculating or bounding the generalized connectivity of given network graphs, and for synthesizing minimum link networks with prescribed generalized connectivity.