Abstract: In mobile environments, unspecified numbers of transactions
arrive in continuous streams. To prove correctness of their
concurrent execution a method of modelling an infinite number of
transactions is needed. Standard database techniques model fixed
finite schedules of transactions. Lately, techniques based on temporal
logic have been proposed as suitable for modelling infinite schedules.
The drawback of these techniques is that proving the basic
serializability correctness condition is impractical, as encoding (the
absence of) conflict cyclicity within large sets of transactions results
in prohibitively large temporal logic formulae. In this paper, we show
that, under certain common assumptions on the graph structure of
data items accessed by the transactions, conflict cyclicity need only
be checked within all possible pairs of transactions. This results in
formulae of considerably reduced size in any temporal-logic-based
approach to proving serializability, and scales to arbitrary numbers
of transactions.
Abstract: Existing work in temporal logic on representing the
execution of infinitely many transactions, uses linear-time temporal
logic (LTL) and only models two-step transactions. In this paper,
we use the comparatively efficient branching-time computational tree
logic CTL and extend the transaction model to a class of multistep
transactions, by introducing distinguished propositional variables
to represent the read and write steps of n multi-step transactions
accessing m data items infinitely many times. We prove that the
well known correspondence between acyclicity of conflict graphs
and serializability for finite schedules, extends to infinite schedules.
Furthermore, in the case of transactions accessing the same set of
data items in (possibly) different orders, serializability corresponds
to the absence of cycles of length two. This result is used to give an
efficient encoding of the serializability condition into CTL.
Abstract: Most of the concurrent transactional protocols consider
serializability as a correctness criterion of the transactions execution.
Usually, the proof of the serializability relies on mathematical proofs
for a fixed finite number of transactions. In this paper, we introduce
a protocol to deal with an infinite number of transactions which are
iterated infinitely often. We specify serializability of the transactions
and the protocol using a specification language based on temporal
logics. It is worthwhile using temporal logics such as LTL (Lineartime
Temporal Logic) to specify transactions, to gain full automatic
verification by using model checkers.
Abstract: Most real world systems express themselves formally
as a set of nonlinear algebraic equations. As applications grow, the
size and complexity of these equations also increase. In this work, we
highlight the key concepts in using the homotopy analysis method
as a methodology used to construct efficient iteration formulas for
nonlinear equations solving. The proposed method is experimentally
characterized according to a set of determined parameters which
affect the systems. The experimental results show the potential and
limitations of the new method and imply directions for future work.