Theorem 4 — randomized block snoopy caching is optimally -competitive
ProvedNonuniformCompetitive.Snoopy.optimal_ratioConsider a block snoopy-caching multiprocessor system with block size , reduced to a single block : processors, block-transfer cost , and any initial state ( shared, or private to one cache). Let
Then:
- no randomized on-line algorithm is -competitive against an oblivious adversary from for any ;
- some randomized on-line algorithm is -competitive against an oblivious adversary from .
Here -competitive means that for some constant and every admissible request sequence , . The optimal deterministic ratio for the same problem is (Karlin, Manasse, Rudolph, Sleator 1988), so randomization gives a strictly better ratio for every , tending to as .
Formalization Note Three conventions are added relative to the printed statement, all from the paper's own setting. (i) : the lower bound needs a second processor. (ii) One block: the proof of Theorem 4 reduces a multi-block system to independent single-block problems (p. 551). (iii) Admissible sequences: every write of processor directly follows a read or write of , the form of "every write is preceded by a read to the same block" (p. 550) that the proof uses. Both claims are stated for every initial state; the additive constant may depend on , and .
import Mathlib import Definitions.Def_NonuniformCompetitive_Snoopy_ep import Definitions.Def_NonuniformCompetitive_Snoopy_model import Definitions.Def_NonuniformCompetitive_Snoopy_randomized
namespace NonuniformCompetitive.Snoopy
/-- Theorem 4 (Karlin, Manasse, McGeoch, Owicki, Algorithmica 11 (1994), p. 551), for the
single-block snoopy-caching task system of §3.1 (p. 550) with `n ≥ 2` processors and block size
`p − 1` (block-transfer cost `p ≥ 1`), from every initial state `s₀`:
1. no randomized on-line algorithm is `c`-competitive against an oblivious adversary for any
`c < e_p / (e_p − 1)`;
2. some randomized on-line algorithm is `e_p / (e_p − 1)`-competitive.
Competitiveness is over admissible request sequences (every write of processor `i` directly
follows a read or write of `i`). -/
theorem optimal_ratio (n p : ℕ) (hn : 2 ≤ n) (hp : 1 ≤ p) (s₀ : State n) :
(∀ (A : RandomizedAlgorithm n p) (c : ℝ), A.IsCompetitiveFrom s₀ c → ep p / (ep p - 1) ≤ c) ∧
∃ A : RandomizedAlgorithm n p, A.IsCompetitiveFrom s₀ (ep p / (ep p - 1)) := by sorry
end NonuniformCompetitive.Snoopy
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.