Tracing Distributed Algorithms Using Replay Clocks

本论文介绍了回放时钟（RepCl），这是一种新型的时钟基础架构，可以让我们对分布式计算进行离线分析。回放时钟结构提供了一种方法，可以按照发生的顺序重放计算，有效地表示并发事件。它建立在向量时钟（VC）和混合逻辑时钟（HLC）引入的结构之上，将它们的基础架构结合起来，提供高效的重放。使用这样的时钟，用户可以在考虑多条执行路径的同时重放计算，并检查在存在并发事件的情况下可能出现的约束违规和属性。具体而言，如果事件e必须在f之前发生，则回放时钟必须确保e在f之前重放。另一方面，如果e和f可以以任何顺序发生，则重放不应强制它们之间的顺序。我们证明，如果时钟在1ms内同步，则可以使用不到4个整数的RepCl实现64个进程的各种系统参数。此外，RepCl的开销（用于计算时间戳和消息大小）与时钟的大小成比例。通过在自定义分布式系统和NS-3（最先进的网络模拟器）中进行模拟，我们确定了RepCl的预期开销。我们还确定了用户如何确定RepCl的可行性区域，在该区域内可以进行无缩减的重放。使用RepCl，我们提供了一种分布式计算追踪器，允许有效地重放使用RepCl的任何计算。该可视化工具允许用户以在线方式分析特定属性和约束，并能够独立考虑并发路径。该可视化工具基于RepCl为每个事件记录的时间提供了每个进程的视图和整个计算的总体视图。

论文介绍了replay clocks（RepCl）这种新型时钟基础设施，旨在解决离线分析分布式计算的问题。具体而言，RepCl提供了一种方法，可以回放计算过程，考虑多个执行路径，并检查并发事件的属性和约束违规。

RepCl结合了向量时钟（VC）和混合逻辑时钟（HLC）的基础设施，提供了高效的回放方式。通过RepCl，用户可以回放计算过程，同时考虑多个执行路径，并检查并发事件的属性和约束违规。

论文证明了RepCl可以在64个进程的各种系统参数下，使用少于四个整数进行实现，如果时钟在1ms内同步，则RepCl的开销（计算时间戳和消息大小）与时钟的大小成比例。论文使用自定义分布式系统和NS-3等工具进行了模拟实验，并确定了RepCl的预期开销。论文提供了基于RepCl的分布式计算追踪器，允许高效回放任何使用RepCl的计算，并提供了基于RepCl记录的事件时间的每个进程视图和整个计算的总体视图。

最近在这个领域中，还有一些相关的研究，例如《Scalable and Accurate Causality Tracking for Eventually Consistent Stores》和《Distributed Tracing with Multiple Clocks》等。