Research On The Problem Of Transaction Behavior Footprint With Incomplete Tokens

In the open dynamic and difficult-to-control distributed softwareenvironment，events are not generated in normal order resulted fromparallel processing of multiple transactions. if the tokens of these eventsare incomplete or unavailable，then the event sources of each footprintcan not be identified by time stamp information of event and tokens oftransaction instance，which will hinder the subsequent analysis andforecasting of the behavior. This paper discusses the problem under twokinds of different situations, constructs a transaction behavior footprintsmodel with incomplete tokens, translates the problem of incomplete tokenbehavior footprint into the problem of network maxflow，and introduces anew augmenting path algorithm. Based on this algorithm，the paperdesigns footprints marking algorithm，and finds the event source forfootprint which lost tokens.The major tasks of this paper include:(1) Establish the behavior footprints model with incomplete tokens.Firstly, if the transition time of transactions in different state isindependent and identically distributed, and the transition in differentstates accords with situation of Markov Property, first, we establishtwo-state model which only has the beginning and end state. Then wetranslate this model into the problem of network flow about directedacyclic，and mark all footprints of the event by looking for augmentingpath. At last, based on the theory，we optimize the multiple states model,adopt state division algorithm，and convert multiple states model into twostates model.(2) Design footprint marking algorithm. First, the paper translates themodel of multiple states into the problem of Maximum flow. After thatbased on the traditional augmenting path algorithm， it relaxes theconstraint conditions on looking for augmenting path，This paper putsforward a new augmenting path algorithm, This algorithm selects theshort enough augmenting path every time and limits maximum capacityfor augmenting path, in order to reduce the number of augmenting path.At last, the paper designs footprints marking algorithm for the differenttwo situations with incomplete tokens, and finds the event source for behavior footprint which lost tokens.(3)Simulation and performance analysis. In two different incompletetokens situations, the simulation experiment has proved that footprintmarking algorithm has validity and accuracy, And performance test isconducted to verify practicality of this algorithm.