论文标题
有效的两层监视器，用于部分同步分布式系统（技术报告）
Efficient Two-Layered Monitor for Partially Synchronous Distributed Systems (Technical Report)
论文作者
论文摘要
监视分布式系统以确保其正确性是一个具有挑战性且昂贵但必不可少的问题。这是具有挑战性的，因为尽管执行分布式系统会在事件之间创建部分顺序，但监视器通常只观察到该部分顺序的一个序列化。这意味着，即使观察到的序列化与系统规格一致，监视器也不能假设系统是正确的，因为其他一些未观察到的序列化可能与系统规格不一致。保证所有这些未观察到的违规行为的现有解决方案需要大量时间和大时钟的组合，例如o（n）大小的向量时钟。 我们提出了一种新的，有效的两层监测方法，该方法克服了早期监视器的时间和空间限制。第一层是不精确但有效的，第二层是精确的，但（相对）效率低下。我们表明，这两层的组合将监测的成本降低了85-95％。此外，两层监视器允许使用O（1）大小的混合逻辑时钟。
Monitoring distributed systems to ensure their correctness is a challenging and expensive but essential problem. It is challenging because while execution of a distributed system creates a partial order among events, the monitor will typically observe only one serialization of that partial order. This means that even if the observed serialization is consistent with the system specifications, the monitor cannot assume that the system is correct because some other unobserved serialization can be inconsistent with the system specifications. Existing solutions that guarantee identification of all such unobserved violations require some combination of lots of time and large clocks, e.g. O(n) sized Vector Clocks. We present a new, efficient two-layered monitoring approach that overcomes both the time and space limitations of earlier monitors. The first layer is imprecise but efficient and the second layer is precise but (relatively) inefficient. We show that the combination of these two layers reduces the cost of monitoring by 85-95%. Furthermore, the two-layered monitor permits the use of O(1) sized Hybrid Logical Clocks.
