标题： 使用重放时钟追踪分布式算法 显示英文标题

标题： Tracing Distributed Algorithms Using Replay Clocks

摘要： 在本论文中，我们引入了重放时钟（RepCl），一种新颖的时钟基础设施，使我们能够对分布式计算进行离线分析。 重放时钟结构提供了一种方法，可以按照实际发生的方式重放计算，并能有效表示并发事件。 它基于向量时钟（VC）和混合逻辑时钟（HLC）所引入的结构，结合它们的基础设施以提供高效的重放。 有了这样的时钟，用户可以在考虑多个执行路径的同时重放计算，并检查在存在并发事件的情况下潜在路径可能采取的约束违反和特性。 具体而言，如果事件 e 必须在 f 之前发生，则重放时钟必须确保 e 在 f 之前被重放。另一方面，如果 e 和 f 可以以任何顺序发生，重放不应强制它们之间的顺序。 我们证明，如果时钟在 1ms 内同步，RepCl 可以用少于四个整数实现，适用于各种系统参数的 64 个进程。 此外，RepCl 的开销（计算时间戳和消息大小）与时钟的大小成正比。 通过在自定义分布式系统和 NS-3（一个最先进的网络模拟器）中的模拟，我们确定了 RepCl 的预期开销。 我们还确定了用户如何识别 RepCl 的可行性区域，在该区域内可以进行完整的重放。 使用 RepCl，我们为分布式计算提供了一个跟踪器，允许任何使用 RepCl 的计算被高效地重放。 可视化功能使用户能够以在线方式分析特定属性和约束，并能够独立考虑并发路径。 可视化功能提供了每个进程的视图以及基于 RepCl 为每个事件记录的时间的整个计算的整体视图。 显示英文摘要

摘要： In this thesis, we introduce replay clocks (RepCl), a novel clock infrastructure that allows us to do offline analyses of distributed computations. The replay clock structure provides a methodology to replay a computation as it happened, with the ability to represent concurrent events effectively. It builds on the structures introduced by vector clocks (VC) and the Hybrid Logical Clock (HLC), combining their infrastructures to provide efficient replay. With such a clock, a user can replay a computation whilst considering multiple paths of executions, and check for constraint violations and properties that potential pathways could take in the presence of concurrent events. Specifically, if event e must occur before f then the replay clock must ensure that e is replayed before f. On the other hand, if e and f could occur in any order, replay should not force an order between them. We demonstrate that RepCl can be implemented with less than four integers for 64 processes for various system parameters if clocks are synchronized within 1ms. Furthermore, the overhead of RepCl (for computing timestamps and message size) is proportional to the size of the clock. Using simulations in a custom distributed system and NS-3, a state-of-the-art network simulator, we identify the expected overhead of RepCl. We also identify how a user can then identify feasibility region for RepCl, where unabridged replay is possible. Using the RepCl, we provide a tracer for distributed computations, that allows any computation using the RepCl to be replayed efficiently. The visualization allows users to analyze specific properties and constraints in an online fashion, with the ability to consider concurrent paths independently. The visualization provides per-process views and an overarching view of the whole computation based on the time recorded by the RepCl for each event.