Sequencing a Six-Service Migration Under Dependency Rules
A platform team must migrate six services to a new cluster, one at a time, with no two migrations running concurrently. The services are auth (A), billing (B), catalog (C), search (D), notifications (N) and gateway (G). The rules are:
- G must migrate last.
- A must migrate before B and before D.
- C must migrate before D.
- N must migrate after B.
- B must migrate before C.
- D must not migrate immediately after C, because a cache warm-up window is required between them.
The team has five working days for the first five services and reserves day six for G. A vendor asks whether C and N can be swapped in the circulated draft order A, B, C, D, N, G. A second draft, A, B, N, C, D, G, has also been circulated. The team lead believes the rules leave at least four valid orders and wants the earliest possible day for search (D).
1. Determine every valid order for the first five services. Is the team lead right that there are at least four?
Read the worked answer
There are exactly four valid orders.
Derivation:
- Rule 1 puts G on day six, so days 1–5 hold A, B, C, D, N.
- Rules 2, 3 and 5 give the chain A < B < C < D. Since A precedes B, C and D, and N must follow B (rule 4), A must be day 1.
- Days 2–5 hold B, C, D, N. B can only be day 2 or day 3: if B were day 4, then C, D and N would each need a slot after it, but only day 5 remains.
B on day 2: C, D, N fill days 3–5 with C < D, giving (C,D,N), (C,N,D), (N,C,D). Rule 6 eliminates (C,D,N) because D would immediately follow C. Survivors: A B C N D and A B N C D.
B on day 3: day 2 is the only slot before B, and N must come after B, so day 2 must be C. D and N then take days 4 and 5 in either order, and D never immediately follows C. Survivors: A C B D N and A C B N D.
Total: four. The lead's belief is correct - and the circulated draft A, B, C, D, N, G is in fact invalid under rule 6.
2. What is the earliest day on which search (D) can be migrated, and how many valid orders achieve it?
Read the worked answer
Day 4, achieved by exactly one order: A, C, B, D, N, G.
Lower bound: rules 2 and 3 require both A and C before D, so D cannot be earlier than day 3. Suppose D were day 3. Then A and C occupy days 1 and 2, and since A must be day 1, C would be day 2 - putting D immediately after C, which rule 6 forbids. So D cannot be day 3 and must be day 4 or later.
Day 4 is reachable: A, C, B, D, N puts D on day 4 with B sitting between C and D, satisfying rule 6. All of rules 1–5 are also satisfied.
In the three other valid orders - A B C N D, A B N C D and A C B N D - D falls on day 5. So only one order attains the earliest day.
The team should be aware of what it is trading: pulling D forward forces B to day 3 and pushes N to day 5, which is the latest any of the five can be scheduled.
3. Is rule 6 redundant given rules 2–5? What relative orders are fixed across all valid schedules?
Read the worked answer
Rule 6 is not redundant.
Without it, the B-on-day-2 case yields three orders rather than two, adding A B C D N. That order satisfies every other rule - A first, C before D, N after B - so rule 6 is the only thing distinguishing A B C D N from A B C N D. It also matters for the earliest-D question: dropping it would let D move to day 3, which is exactly the schedule the cache warm-up window forbids.
Fixed across all four orders: A is always day 1; G is always day 6; A precedes everything else; C precedes D; B precedes D; B precedes N; every service precedes G.
Not fixed: the relative order of B and C (B may be day 2 or day 3), the relative order of C and N, and the position of N (day 3, 4 or 5).
Practical use: any schedule that violates a fixed relation is wrong without further checking, while any proposed change that only swaps B and C, or C and N, needs to be tested against rule 6 before it is accepted.