###
DOI:
Journal of Software:2010.21(zk):224-237

不完全标记的多个并行事务踪迹的“剥离”
满君丰,李长云,文志诚,温向兵
(湖南工业大学 计算机与通信学院,湖南 株洲 412008;湖南工业大学 计算机与通信学院,湖南 株洲 412008; 国防科学技术大学 计算机学院,湖南 长沙 410073)
Stripping Multiple Parallel Transaction Footprints with Incomplete Tokens
MAN Jun-Feng,LI Chang-Yun,WEN Zhi-Cheng,WEN Xiang-Bing
(School of Computer and Communication, Hunan University of Technology, Zhuzhou 412008, China;School of Computer and Communication, Hunan University of Technology, Zhuzhou 412008, China; School of Computer Science, National University of Defense Technology, Changsha 410073, China)
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 2390   Download 2261
Received:June 15, 2010    Revised:December 10, 2010
> 中文摘要: 新型分布式软件的多个并行处理事务导致每个事务产生的事件按随机排序,如果这些事件的标记不完全或不可用,将无法区分这些事件到底属于哪个事务.将不完全标记事件的“剥离”问题转化成偶图最大权重完全匹配问题.对于事件间的转换时间是独立等同分布的情况,将所有可能状态(事件)划分为若干个割集,每个割集构成一个偶图.在这些偶图系统中,采用所提出的偶图最大权重完全匹配的改进算法进行分散匹配,通过拼接匹配结果得到各事务产生的最可能踪迹序列.仿真实验证实:该方法可以有效实现不完全标记的事务踪迹的“剥离”;与传统的偶图匹配方法相比,改进算法具有更高的匹配效率.
Abstract:Multiple parallel transactions in new-type distributed software result in that the events produced by them are randomly ranked. If the tokens of these events are incomplete or unavailable, they can’t be distinguished to belong to which transaction. In this paper, the problem of stripping events with incomplete tokens is converted into maximum-weight perfect matching of bigraph system. If the transition time among these events is independently and identically distributed, all possible states (events) are separated into multiple cutsets, each of them becomes a bigraph system. The improved algorithm of maximum-weight perfect matching is adopted to finish respective matching, and then the matching results are spliced to gain the most possible footprint sequences produced by these transactions. Simulation experiments confirm that our method can effectively strip transaction footprints with incomplete tokens. Compared to traditional bigraph matching algorithm, the improved one has higher efficiency.
文章编号:     中图分类号:    文献标志码:
基金项目:Supported by the National Natural Science Foundation of China under Grant No.60773110 (国家自然科学基金); the Post-Doctoral Science Foundation of China under Grant No.20080440216 (博士后基金); the Natural Science Foundation of Hu’nan Province of China under Grant No.09JJ6087 (湖南省自然科学基金). Supported by the National Natural Science Foundation of China under Grant No.60773110 (国家自然科学基金); the Post-Doctoral Science Foundation of China under Grant No.20080440216 (博士后基金); the Natural Science Foundation of Hu’nan Province of China under Grant No.09JJ6087 (湖南省自然科学基金).
Foundation items:
Reference text:

满君丰,李长云,文志诚,温向兵.不完全标记的多个并行事务踪迹的“剥离”.软件学报,2010,21(zk):224-237

MAN Jun-Feng,LI Chang-Yun,WEN Zhi-Cheng,WEN Xiang-Bing.Stripping Multiple Parallel Transaction Footprints with Incomplete Tokens.Journal of Software,2010,21(zk):224-237