16590593
An approach to hardware/software partitioning for multiple hardware devices model
Computer aided hardware/software partitioning is one of the key challenges in hardware/software co-design. This paper describes a new approach to hardware/software partitioning for multiple hardware-devices model. The partitioning is transformed into a reachability problem of timed automata, and the optimal solution can be obtained by means of an optimal reachability algorithm. To relax the initial condition of partitioning for optimization, two algorithms are designed to explore the dependency relations among processes in the sequential specification. Some experiments are conducted with model checker UPPAAL to show our approach is both effective and efficient.
15041582
Towards the Semantics and Verification of BPEL4WS
In this paper, we discuss the semantics of BPEL4WS language which is a de facto standard for specifying and execution workflow specification for web service composition and orchestration. We propose a language @m-BPEL that includes most primitive and structured activities of BPEL4WS, and define its semantics. As the Timed Automata (TA) is powerful in designing real-time models with multiple clocks and has well developed automatic tool support, we define a map from @m-BPEL into composable TA. Therefore, the properties we want to check can be verified in TA network correspondingly. Furthermore, we prove that the mapping from @m-BPEL to TA is a simulation, which means that the TA network simulates correctly the corresponding @m-BPEL specification. The case study with model checker Uppaal shows that our method is effective, and a Java supporting tool based on Uppaal model checker engine has been developed.
15937739
Semantics of BPEL4WS-Like Fault and Compensation Handling
BPEL4WS is one of the most important business process modelling languages. One distinct feature of it is the fully programmable fault and compensation handling mechanism, which allows the user to specify the compensation behaviors of processes in application-specific manners. In this paper, we present a formal operational semantics to a simplified version of BPEL4WS, with some important concepts related to fault and compensation handling proposed and discussed, especially, the compensation closure and the compensation context. We also discuss some insights into the BPEL4WS language and its implementation obtained from this study.
2194617
Model Checking Dynamic UML Consistency
UML is widely accepted and extensively used in software modeling. However, using different diagrams to model different aspects of a system brings the risk of inconsistency among diagrams. In this paper, we investigate an approach to check the consistency between the sequence diagrams and statechart diagrams using the SPIN model checker. To deal with the hierarchy structure of statechart diagrams, we propose a formalism called Split Automata, a variant of automata, which is helpful to bridge the statechart diagrams to SPIN efficiently. Compared with the existing work on model checking UML which do not have formal verification for their translation from UML to the model checker, we formally define the semantics and prove that the automatically translated model (i.e. Split Automata) does simulate the UML model. In this way, we can guarantee that the translated model does represent the original model.
6031727
Towards the Formal Model and Verification of Web Service Choreography Description Language
The Web Services Choreography Description Language (WS-CDL) is a W3C specification for the description of peer-to-peer collaborations of participants from a global viewpoint. For the rigorous development and tools support for the language, the formal semantics of WS-CDL is worth investigating. This paper proposes a small language CDL as a formal model of the simplified WSCDL, which includes important concepts related to participant roles and collaborations among them in a choreography. The formal operational semantics of CDL is given. Based on the formal model, we discuss further: 1) project a given choreography to orchestration views, which provides a basis for the implementation of the choreography by code generation; 2) translate WS-CDL to the input language of the model-checker SPIN, which allows us to automatically verify the correctness of a given choreography. An automatic translator has been implemented.
1611793
Type Checking Choreography Description Language
The Web Services Choreography Description Language (WS-CDL) is a W3C specification developed for the description of peer-to-peer collaborations of participants from a global viewpoint. Currently WS-CDL has no rigorous static type checking. We believe that introducing a type system will exclude many design and description errors, and ensure desirable properties of the choreography specifications. In this paper, we took a core language CDL, which covers most of the important features of the WS-CDL, and is more convenient for the study. We developed the abstract syntax and operational semantics of CDL, and defined a collection of rules which can be used to check if choreography is well-typed. Moreover, we also proved some type safety theorems for CDL in the sense that well-typed choreography cannot get stuck. We show how the use of type information can allow us to gain confidence in the correctness of choreography.
13480741
Source authentication in group communication systems
Many group communication systems need to enforce a restriction that limits members are authorized to send messages to the group. Receivers therefore need to authenticate message sources before the received messages are accepted. Source authentication in peer-to-peer systems is trivial: the two communication parties can agree on one pair key and use this key to authenticate each other. However, because the group key is shared by all members in a group system, it is quite challenging to identify the sender and determine its authorization. Furthermore, if the authorization can be changed at run-time, source authentication problem can be even harder. This paper presents a source authentication technique called TTA scheme (Transitive Trust Authentication). TTA supports source authentication as well as dynamic authorization change. In addition, its computation and communication overhead is low.
33218482
Some Algorithms for Extension Computation of Nonmonotonic Rule Systems
In this paper, we will place our emphasis on the problem of existence of extensions and on finding more efficient algorithms for computing extensions of nonmonotonic rule systems. First, in order to dedicate further research into nonmonotonic rule systems a new characterization and some new results are given. This characterization and these results lead to new algorithms for computing extensions. Second, a class of nonmonotonic rule systems, called regular nonmonotonic rule systems, is developed. The existence of extensions and semi-monotonicity of regular nonmonotonic rule systems are proved. Third, we prove that each regular nonmonotonic rule system has at most 1.47^n extensions, where n is the number of elements occurring in the system.
18186547
Experiences with a Mobile Testbed
This paper presents results from an eight-day network packet-trace of MosquitoNet. MosquitoNet allows users of laptop computers to switch seamlessly between a metropolitan-area wireless network and a wired network (10 Mbit/s Ethernet) available in offices and on-campus residences. Results include the amount of user mobility between the wired and wireless networks, the amount of mobility within the wireless network, an examination of application end-to-end delays, and an examination of overall packet loss and reordering in the wireless network. We find that the average mobile host switches between the wired and wireless networks 14 times during the trace and moves within the wireless network five times. Round trip latencies in the wireless network are very high, with a minimum of 0.2 seconds. Even higher end-to-end delays, of up to hundreds of seconds, are due to packet loss and reordering. These delays cause users to change their usage patterns when connected to the wireless network. We conclude that latency is a critical problem in the wireless network.
32094146
On Boolean Models for Quantified Boolean Horn Formulas
For a Quantified Boolean Formula \(({\it QBF })\) Φ=Qφ, an assignment is a function \(\cal M\) that maps each existentially quantified variable of Φ to a Boolean function, where φ is a propositional formula and Q is a linear ordering of quantifiers on the variables of Φ. An assignment \(\cal M\) is said to be proper, if for each existentially quantified variable y i , the associated Boolean function f i does not depend upon the universally quantified variables whose quantifiers in Q succeed the quantifier of y i . An assignment \(\cal M\) is said to be a model for Φ, if it is proper and the formula \(\phi^{\cal M}\) is a tautology, where \(\phi^{\cal M}\) is the formula obtained from φ by substituting f i for each existentially quantified variable y i . We show that any true quantified Horn formula has a Boolean model consisting of monotone monomials and constant functions only; conversely, if a QBF has such a model then it contains a clause–subformula in \({\it QHORN }\cap {\it SAT }\).
10845241
On Odd and Even Cycles in Normal Logic Programs
An odd cycle of a logic program is a simple cycle that has an odd number of negative edges in the dependency graph of the program. Similarly, an even cycle is one that has an even number of negative edges. For a normal logic program that has no odd cycles, while it is known that such a program always has a stable model, and such a stable model can be computed in polynomial time, we show in this paper that checking whether an atom is in a stable model is NP-complete, and checking whether an atom is in all stable models is co-NP complete, both are the same as in the general case for normal logic programs. Furthermore, we show that if a normal logic program has exactly one odd cycle, then checking whether it has a stable model is NP-complete, again the same as in the general case. For normal logic programs with a fixed number of even cycles, we show that there is a polynomial time algorithm for computing all stable models. Furthermore, this polynomial time algorithm can be improved significantly if the number of odd cycles is also fixed.