关键词: 分布式系统, 重复元素, 布隆过滤器, 通信开销最小化, 机制设计

Abstract: The detection of persistent elements has many important applications in the fields of detecting intrusions in a distributed system, finding common interests, measuring the traffic, etc. Most of the existing state-of-the-art studies of detecting persistent elements have some problems such as false or missing report, high communication cost and great limitation so that they can hardly satisfy the requirement of some distributed applications. To solve these problems, the paper proposes a scheme to detect persistent elements in distributed monitoring system with the goal of minimizing the total communication cost during the whole detection process. First, the scheme filters out most of the irrelevant elements to reduce the overall communication overhead through multiple rounds of compressed data transferring between all monitors and the central coordinator. Then, we ensure that each round of the filtering is necessary and can achieve the best performance by adjusting parameters of filtering according to the theoretical analysis and derivation. With the technology of extended Bloom filter and the persistent spread estimation function, the scheme can work well no matter in the balanced environment or in the unbalanced environment. Finally, we perform extensive simulations to study the performance of the proposed mechanism, and the simulation results show the effectiveness of our scheme.

Key words: distributed system, persistent element, Bloom filter, communication cost minimization, mechanism design