My writings hunt for latest activity on composing self-stabilizing systems didn't output item useful. The layered stabilization idea was already in location by the first 2000s, and nothing essential seems to have been added since. Frustrating.
So I decided to assault the issue using the tangible example I have. I had composed a rely-guarantee TLA+ example of a retry storm as two components alongside contracts. That example reproduces metastable nonaccomplishment since the construction that worked from fine states unsuccessful to activity whenever a ample daze removes the basis case that let the two conditions clasp all another up.
Searching for rely-guarantee based construction from all state, turned up a 2017 authority theory document by Kim, Arcak and Seshia, "A Small Gain Theorem for Parametric Assume-Guarantee Contracts". This document does approximately what I want: discharging circular reasoning between two components without layering or blocking. But it comes alongside several grave limitations. In their formalism, a component is an input-output connection on signals, and contracts connect an input border to an output bound. This is a memoryless perspective of a component, so it is not imaginable to province backlog accumulating from former rounds. That rules out queues, among another helpful distributed systems concepts. It additionally has no association to stabilization. The document does not conversation concerning a variant/potential function and convergence reasoning. But there are motionless pieces there value stealing toward a compositional theory of self-stabilization and metastability. Below I try to activity this out... slightly unsuccessfully.
Understanding Parametric Assume-Guarantee Contracts
In our first model, the retrier's justify was conditional and partial: "if the queue is under 6, I dispatch no retries". This agreement does not say item concerning whenever the queue is at 18. Since the "if" circumstance fails, the commitment is vacuously satisfied and the component owes us nothing.
The parametric assume-guarantee paper's big idea is to compose a entire family of contracts that shield everywhere, fairly than penning one commitment alongside a precondition.
Tired: If the queue is under 6, no retries.
Wired: Whatever the queue dimension $L$ turns out to be, I dispatch at most $\lambda(L)$ retries.
Recall that my constants from the example are $S=3$ units of server capability per round, $A_{max}=2$ maximum caller arrivals per round, and a retry timeout of $T=2$ rounds, which makes the latency threshold $S \cdot T = 6$. This makes $\lambda(L) = \lfloor (L-6)/2 \rfloor$, which gives us:
| if the queue is at most... | ...I dispatch at most this many retries |
|---|---|
| 6 | 0 |
| 8 | 1 |
| 10 | 2 |
| 12 | 3 |
| 14 | 4 |
| 16 | 5 |
| 18 | 6 |
The old agreement is motionless in there, as the top row: $\lambda(6)=0$ says "queue under 6 method at most zero retries". Although the old agreement is invalid at queue dimension of 18, under the parametrized assume-guarantee method all row of the array gets a promise. So we get a bundle of average contracts, one per badness flat $p$:
$$\varphi_a = \bigvee_p \psi_a(p)$$
$$\varphi_g = \bigwedge_p \left( \psi_a(p) \Rightarrow \psi_g(\lambda(p)) \right)$$
The assumption side, $\varphi_a$, is a disjunction since the levels are alternatives. The surroundings volition be at one of them, whichever one it happens to be. "Queue at most 6, or at most 8, or at most 10, or..." is satisfied by basically any environment, so there is no letter cover remaining to autumn exterior of.
The justify side, $\varphi_g$, is a conjunction complete the identical levels. Since the obligations are cumulative, we owe all of them at once. Rows whose circumstance is false disbursal us nothing, and since the levels are nested, multiple use at formerly and the tightest wins. When queue is at 7, "at most 8" applies, and the component owes us at most 1 retry; "at most 10" additionally applies and it additionally owes us at most 2, but the archetypal case already implies that. Monotonicity becomes key here.
Deriving the Small Gain Rule
What is the regulation that says whenever specified a iteration settles? The document calls this the small acquire theorem. Let me commencement by explaining the intuition.
You have seen this happen, right? When a microphone gets in forefront of a speaker, the mic picks up sound, and the amp boosts it. The speaker plays this back, which the mic picks it up again. Each lap about that iteration multiplies the sound, and you comprehend a elevated thrown squeal.
To quantify this procedure we need one figure per component: how much badness out per component of badness in. That is the slope of the component's reply function, and authority theory calls it the component's gain.
When we sequence the two components, and nourish a nudge $x$ into the first, incline $g_1$, and $g_1 x$ comes out. When we nourish that into the second, incline $g_2$, and $g_2 g_1 x$ comes out. One lap has multiplied the nudge by $g_1 g_2$. After $k$ laps the nudge is $(g_1 g_2)^k$ times its first size. If the merchandise is under one, the laps shrink geometrically and the iteration settles. If it is complete one, it diverges. The evidence is from the geometric series.
The small acquire theorem is so elegant, it gives us a earth outcome that covers all starting province at once. But the small acquire setup is limited. In our case, two things halt us from using this shortcut.
First, this needs direct lines. Our retrier has a direct incline $1/2$, but our server does not. Its portion of assistance goes as $f/(f+d)$, so its incline depends on anywhere the queues are. So, there is no sole figure to multiply.
Second, and worse, the shortcut assumes badness is one number. Our scheme has two queues that behave differently: caller activity $q_f$, and duplicates $q_d$. A border on one is not a border on the other. So a lap about our iteration takes a brace of numbers to a brace of numbers.
Underneath the two restrictions lies the memoryless perspective of a component I complained concerning in the introduction. In this setup a acquire is an input-output relation: it says how much of what arrives is passed along. There is no slot in it for how much of my own backlog is motionless sitting current from former rounds. Queues are mostly backlog, and that is what the next division is about.
Dealing alongside Two Queues and Four Slopes
Let's track the two queues. We can compose the circular as a regulation on the brace (fresh queue $f$, copy queue $d$) by applying arrivals, applying retries, applying the proportional assistance divided to fig out the next pair. We afterward ask whether any brace maps to itself.
One brace does: $(f,d) = (8,4)$. Here the total queue is 12, so the three units of capability divided two to caller and one to duplicates. Two caller served cancels the two arrivals exactly. The retry charge is $(8-6)/2 = 1$, and one copy served cancels that exactly. So next rounds, the queues are motionless in balance.
The inquiry is what happens if we commencement near this balance point. Start at $(9,4)$ and does the scheme autumn back, or run away? To answer we need to cognize how a small nudge propagates.
I volition preserve you the calculation but current is the table.
| effect on next \(f\) | effect on next \(d\) | |
|---|---|---|
| per component of \(f\) | \(11/12\) | \(7/12\) |
| per component of \(d\) | \(1/6\) | \(5/6\) |
Let's commencement alongside the diagonal. Here we logic concerning what happens if we add one item to a queue, how much bigger does that queue get next round? For this reasoning, lone the server is involved, and we get $11/12$ and $5/6$, which are the fraction of that item motionless sitting there next round.
Now, let's regard the off-diagonal, which is concerning cross-queue interaction. If you add one item to this queue, how much bump would it logic for the another queue next round? The server is engaged in this calculation since what one queue takes the another loses because of the divided of activity at the server. The retrier is additionally engaged since its pending figure tracks the caller queue, and the retries it sends district in the copy queue. The figure $7/12$ consists of $1/2$ from the retrier (with $T=2$, one additional item in the caller queue eventually produces one additional retry, but dispersed complete two rounds) affirmative $1/12$ from the server. The another off-diagonal figure $1/6$ is from the server alone, because of the additional copy diluting fresh's portion of the S=3 capability split.
Tracking downward the Instability
The paper's small acquire theorem suggests us to multiply the gains about the iteration and inspect that the merchandise is under one.
Let's choose the two entries on the off-diagonal of the table. These say that a longer caller queue makes additional duplicates ($7/12$, the consequence of $f$ on next $d$) and additional duplicates starve the caller assistance ($1/6$, the consequence of $d$ on next $f$). Since these affect the communication of the two components, let's call that coupling. When we multiply them, we get $\frac{7}{12} \cdot \frac{1}{6} = \frac{7}{72} \approx 0.1$. That says, a nudge sent formerly about the iteration returns a tenth of its size. This says the scheme is stable alongside a aspect of ten to spare. But it is wrong, since it says lone two of the four numbers in that table.
The two numbers on the diagonal, $11/12$ and $5/6$, depict the another flank of the coin: How much of all queue is motionless there next round, alongside the another queue playing no part. Recall that the two of these arrive from the server alone. Let's call this one memory. The small acquire theorem says lone the coupling and ignores the memory.
When we obtain the recollection into account, the genuine per-round multiplier becomes $1.19$, which is complete one, so nearly any disturbance grows fairly than decays.
We get that figure through norm linear stability analysis. We appearance for a nudge $(x,y)$ that the array fair scales by several aspect $r$. With entries $a,c$ on top and $b,d$ below, that method $ax+cy=rx$ and $bx+dy=ry$. When we resolve all for $y/x$, set them equal, and we get the table's trait polynomial: $$r^2 - (a+d)\,r + (ad - bc) = 0$$
The two roots of a quadratic add up to the negative of the center coefficient and multiply to the changeless term. So our two factors (eigenvalues) add to $a+d$ (trace) and multiply to $ad-bc$ (determinant).
The trace comes from the diagonal only: $11/12 + 5/6 = 1.75$. Coupling shows up in the determinant as a subtraction: $0.76 - 0.10 = 0.67$.
If we autumn the coupling, the determinant returns to $0.76$ alongside the trace unchanged, giving us $0.92$ and $0.83$, the two under one. If we reconstruct the coupling, the determinant falls to $0.67$, which splits the identical sum into $1.19$ and $0.56$, anywhere one aspect is complete 1, orthography trouble.
This arithmetic additionally explains the two known fixes. A retry prosperity zeroes the $7/12$ entry; fresh-first assistance zeroes the $1/6$. Either way nothing is subtracted from the determinant and the factors autumn rear to $0.92$ and $0.83$. Each queue motionless carries complete additional than 80% of itself all round, but alongside no coupling to nourish that carryover the backlog drains 8% a circular alternatively of expanding 19%.
Capping the queues is another type of the identical move. A cap of $M$ on the caller queue method the retrier can never emit additional than $(M-6)/T$ retries, which is a difficult ceiling on the $7/12$ coupling entry. This is a form of retry prosperity again. The backlog drains lone if the ceiling sits under the headroom: at $M=7$ the cap allows zero retries and all commencement drains, during at $M=8$ it allows one retry, and another attractors commencement appearing in the space. Doing a simulation clear shows that complete $M=8$, the cap limits the divergence but does not forestall the failure. Instead of expanding without limit, the queues ascend to the ceiling and stay. At $M=40$ the scheme parks at $(39,38)$: of the three units served per round, one does helpful activity and two go to duplicates of requests already in flight. That is the extremely definition of metastability.
The Upshot
The parametric assume-guarantee document gave me a improved way to compose a component's commitment as a family of contracts indexed by how bad the surroundings is. But it did not provision me a formula for construction for applicable systems. Since the paper's example is memoryless and uses one scalar, it didn't use to our example. I got the four slopes by penning out how the two queues develop together, which meant abandoning construction for that step. However, it's value noting that all term in that array comes from a sole component, and the $7/12$ is fair the retrier's $1/2$ added to the server's $1/12$. So there may be a way to activity construction out current in the future.
