| 摘要: |
| 新型分布式软件的多个并行处理事务导致每个事务产生的事件按随机排序,如果这些事件的标记不完全或不可用,将无法区分这些事件到底属于哪个事务.将不完全标记事件的“剥离”问题转化成偶图最大权重完全匹配问题.对于事件间的转换时间是独立等同分布的情况,将所有可能状态(事件)划分为若干个割集,每个割集构成一个偶图.在这些偶图系统中,采用所提出的偶图最大权重完全匹配的改进算法进行分散匹配,通过拼接匹配结果得到各事务产生的最可能踪迹序列.仿真实验证实:该方法可以有效实现不完全标记的事务踪迹的“剥离”;与传统的偶图匹配方法相比,改进算法具有更高的匹配效率. |
| 关键词: 新型分布式软件 不完全标记 事务踪迹 偶图匹配 排列最大匹配算法 |
| DOI： |
| 分类号: |
| 基金项目: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 (湖南省自然科学基金). |
|
| Stripping Multiple Parallel Transaction Footprints with Incomplete Tokens |
|
MAN Jun-Feng1, LI Chang-Yun1,2, WEN Zhi-Cheng1, WEN Xiang-Bing1
|
|
1.School of Computer and Communication, Hunan University of Technology, Zhuzhou 412008, China;2.School of Computer Science, National University of Defense Technology, Changsha 410073, China
|
| 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. |
| Key words: new-type distributed software, incomplete token, transaction footprint, bigraph matching, rank-maximal matching algorithm |
