Paper Summary: Detecting Global Predicates Inward Distributed Systems Alongside Clocks

This is a 2000 newspaper past times Scott Stoller. The newspaper is most detecting global predicates inwards distributed systems.

There has been a lot of previous function on predicate detection (e.g., Marzullo & Neiger WDAG 1991, Verissimo 1993), exactly those function considered vector clock (VC) timestamped events sorted via happened-before (hb) relationship. This newspaper proposes a framework for predicate detection over events timestamped with approximately-synchronized (think NTP) physical-time (PT) clocks.

This was a tough/deep newspaper to read too a rewarding i every bit well. I intend this newspaper should have to a greater extent than involvement from distributed systems developers every bit it has applications to the cloud computing monitoring services. As you lot tin ship away meet inwards Facebook stack too Google stack, monitoring services are an indispensible element of large-scale cloud computing systems.

Motivation

Using PT for timestamping (and predicate detection) has several advantages over using VC. VC is O(N), whereas PT is a scalar. For capturing hb, VC assumes that all communication occur inwards the nowadays arrangement too at that spot are no backchannels, which is non practical for today's large-scale integrated arrangement of systems. Using PT alleviates the backchannel problem: fifty-fifty if at that spot is non straight communication path, if effect B happened inwards physical fourth dimension afterwards than effect A, thus nosotros tin ship away nevertheless position that effect A tin ship away comport upon effect B due to out-of-bound communication. Finally, using PT for timestamping allows the devops to hold upwards able to question the arrangement inwards relation to physical time, whereas VC fails to back upwards it.

It turns out that using PT too provides benefits over using VC inwards price of complexity of predicate detection. The worst illustration complexity for predicated detection using hb captured past times VC is Ω(E^N), where E is the maximum number of events executed past times each process, too north is the number of processes. On the other hand, the smaller the uncertainties inwards events' PT timestamps, i.e., the less the events overlap, the cheaper the PT-based predicate detection gets. With some assumptions on the inter-event spacing beingness larger than fourth dimension synchronization uncertainty, it is possible to direct maintain worst-case fourth dimension complexity for PT-based predicate detection to hold upwards O(3^N E N²) --- linear inwards E.

I volition say to a greater extent than on this betoken too how using our hybrid clocks tin ship away farther bring down toll of predicate detection at the destination of this post.

Computation model

A local computation has the degree e1, s1, e2, s2, e3, s3, where the ei are events, too the si are local states. A global nation of a distributed arrangement is a collection of local states.

Each effect e has an interval timestamp its(e), which is an interval with lower endpoint lwr(e) too upper endpoint upr(e). PT timestamping should satisfy the next conditions.
TS1: ∀ e: lwr(e) ≤ upr(e)
TS2: ∀ e1 with a succeeding effect e2 on the same process: lwr(e1) ≤ lwr(e2) too upr(e1)≤ upr(e2)
TS3: ∀ e1,e2: if e1 occurred earlier e2 inwards existent time, thus lwr(e1) ≤ upr(e2)

TS3 is the strongest alongside these assumptions. Still this is a fairly full general practical modeling of guess fourth dimension synchronization: The intervals of events produce non bespeak to hold upwards all equal across processes or fifty-fifty along the events on the same process.

Generic theory of consistent global states (CGS)

A consistent global nation (CGS) is a global cutting that could direct maintain occurred during the computation.

The newspaper shows that CGS lattice theory is non specific to hb exactly applies to whatever partial generic ordering gb on events, that satisfy TS2. Two local states are concurrent if they are non related past times gb. A global nation is consistent with abide by to gb if its constituent local states are pairwise concurrent.
consis^gb (g) ≡ ∀ i, j: i ≠ j: \neg (g(i) gb g(j))

By adopting PT instead of VC for timestamping too ordering, the newspaper defines ii ordering relations db ("definitely occurred before") too pb ("possibly occurred before") alongside events every bit follows.

e1 db e2 ≡ upr(e1) < lwr(e2)

e1 pb e2 ≡ ¬ (e2 db e1)
Notice how pb is elegantly defined inwards price of db.

By substituting db too pb orderings inwards the generic CGS framework above, the newspaper obtains definitions of three distinct detection modalities: Poss-db θ (“θ maybe held”), Def-db θ (“θ definitely held”), too Inst θ (“θ definitely held at a specific instant”). We beak most these detection modalities too developing efficient detection algorithms for them inwards the adjacent ii sections.

Detection based on strong effect ordering, db

Substituting db ordering inwards the generic theory of CGS, nosotros larn Poss-db too Def-db. A computation satisfies Poss-db Q iff there exists some interleaving of events that is consistent with db too inwards which the arrangement passes through a global nation satisfying predicate Q. A computation satisfies Def-db Q iff for every interleaving of events that is consistent with db, Q holds. These ii are analog to Poss-hb too Def-hb for the hb relation on the CGS framework. Figure 1 illustrates the nuance betwixt Poss-db too Def-db. If Q holds alone at CGS <3,1>, thus Poss-db holds, exactly Def-db would non since computation mightiness direct maintain taken <2,2> path instead of <3,1> path too Q does non concur at <2,2>. Def-db would concur if Q holds inwards both <3,1> too <2,2>. Or,  instead if Q holds alone at CGS <2,1>, thus Def-db nevertheless holds.


As nosotros mentioned inwards the beginning, the lineament of fourth dimension synchronization comport upon the toll of predicate detection. If the bounds on the offsets are comparable to or smaller than the hateful interval betwixt events that potentially truthify or falsify θ, thus the number of global states that must hold upwards checked is comparable to the number of global states that the arrangement genuinely passed through during execution, which is O(NE). In contrast, the number of global states considered inwards the asynchronous hb illustration is O(E^N).

Assume the interval betwixt consecutive events at a procedure is at to the lowest degree τ.
For Poss-db too Def-db worst-case fourth dimension complexities are every bit follows:
- if τ > 2ε, O(3^N E N²)
- if τ ≤ 2ε, O((4ε/τ +2)^{N-1} E N²)

This minute alternative is the problematic zone. For τ << ε the fourth dimension complexity of detection algorithm grows quickly. The figure below illustrates this, too shows how number of CGS alter with abide by to E too the ratio μ/ε, where μ is the hateful inter-event time.

Detection based on weak effect ordering, pb

In contrast to db, pb is a full gild too non a partial order.

Substituting pb ordering inwards the generic theory of CGS, nosotros larn Poss-pb too Def-pb. In fact, pb collapses Def-pb too Pos-pb into one, Inst. This is because at that spot are no alternate-paths inwards the pb computation. pb looks at inevitable global states, i.e., SCGS. The below computation has alone ii SCGSs (1,2) too (3,2).


This is similar to Properly detection past times Fromentin too Raynal 1997. The computation contains O(NE) local states too at that spot are alone O(NE) SCGSs. And, the worst illustration fourth dimension complexity of algorithm: O((N log N) E)

This is genuinely depression cost. So, where is the catch?

It turns out Inst detection is non enough/complete. Inst may missy some CGSs every bit illustrated below. (The newspaper doesn't explicitly beak over this, thus this gave me some confusion earlier I could figure this out.)

How would hybrid time/clocks benefit

In Stoller's world, you lot bespeak to brand a binary alternative earlier hand: kicking the bucket either with VC- or PT- based timestamping too detection.

But, going with VC becomes disadvantageous inwards many cases: when at that spot isn't plenty communication to innovate plenty hb restrictions. PT tin ship away too kicking the bucket rattling disadvantageous: when μ/ε << 1. (Figure vi shows how apace number of CGSs to reckon tin ship away grow inwards this region.)


Even worse, inside the same arrangement you lot tin ship away direct maintain VC kicking the bucket disadvantegous inwards some regions/phases of computation too PT inwards others. (You tin ship away direct maintain excited communication caused past times closeby events inside ε. So for ε inwards 10ms, you lot tin ship away direct maintain several regions where μ/ε to hold upwards <<1. This increases the complexity of Deff-db too Poss-db greatly. Especially for large N.)

We had late introduced hybrid clocks, too inwards item hybrid vector clocks (HVC). With HVC you lot don't direct maintain to pick out i over another; HVC offers you lot the lowest toll detection of VC too PT at whatever point. Moreover piece VC is of  O(N) size, with HVC thank you lot to loosely-synchronized clock supposition it is possible to continue the sizes of HVC to hold upwards a twosome entries at each process. HVC captures the communications inwards the timestamps too provides the best of VC too PT worlds.

We are investigating these issues with my colleague Sandeep Kulkarni at Michigan State, every bit utilization of our NSF supported projection on highly auditable distributed systems.

It too looks similar the db too pb relations should direct maintain applications to linearizability/serializability inwards distributed databases. And it volition hold upwards interesting to investigate these further.

Share this post