具有O(n)消息复杂度的非阻塞检查点算法

摘要

为了用检查点设置及回卷恢复技术提高并行分布式系统容错性能时降低设置检查点的时间和空间开销，提出了一种非阻塞协调检查点算法。与传统的两阶段提交算法不同，该算法是单阶段提交算法，可跳过临时检查点阶段直接获得永久检查点，减少了同步控制消息的数量，加快了检查点的形成时间。它通过发送进程排除孤儿消息，实现了并行计算；通过设置检查点算法启动周期，解决中途消息问题。该算法的时间复杂度由通常的O（n^2）降低到O（n）．只需要n-1个同步消息。