Abstract: Cloud computing provides great opportunities for distributed and parallel Skyline query in large multi- dimensional datasets. Simultaneously, the inherent high frequency of failures in large-scale datacenters posts new challenges to query reliability. Existing researches focus on improving the response time, progressiveness and load balancing, etc. of Skyline algorithms, but they become disabled in the presence of failures. To solve this problem, this paper proposes a fault-tolerant parallel Skyline algorithm (FTPS). With failures detection and tasks migration, FTPS can detect failures quickly and migrate the computation tasks to a duplicate node. When failures happen, the query processing is also guaranteed. Theoretical analysis and extensive experiments prove that FTPS performs well in fault-tolerance without deteriorating other performances of Skyline query.

Key words: Skyline query, distributed and parallel computing, cloud computing, data center, fault-tolerance

摘要： 云计算为分布并行Skyline查询提供强大存储能力和计算能力的同时, 其大规模数据中心固有的故障频发特性给可靠Skyline查询处理带来极大挑战。现有研究致力于提高Skyline算法的响应时间、渐进性、负载均衡等各项性能, 不能保证故障情况下查询继续正确执行。为此, 提出一种容错并行Skyline查询算法(fault-tolerant parallel Skyline, FTPS)。该算法通过故障监测和任务迁移, 使得能够在查询过程中及时发现故障, 并将故障节点的计算任务迁移到副本节点, 保证查询的正确执行。理论分析和实验证明, FTPS算法能够在不影响正常Skyline查询处理性能的情况下获取较好的容错处理性能。

关键词: Skyline查询, 分布并行计算, 云计算, 数据中心, 容错