Weight Updates. When the T iterations of an epoch k are complete, we reduce the weight vector (wi) in preparation for epoch k + 1. According to The Gap Lemma, if an individual deviation score dev(i) is too large, i is bad w.h.p., and if a correlation score corr(i, j) is too large, B ∩ {i, j} ∅ w.h.p., so reducing both i and j’s weights by the same amount preserves Invariant 1. With this end in mind, Weight-Update (Algorithm 3) constructs a complete, vertex- and edge-capacitated graph G on [n], finds a fractional maximal matching µ in G, then docks the weights of i and j by µ(i, j), for each edge (i, j). Definition 1 (Fractional Maximal Matching). Let G = (V, E, cV , cE) be a graph where cV : V → R≥0 are vertex capacities and cE : E → R≥Σ0 are edge capacities. A function µ : E → R≥0 is a feasible fractional matching if µ(i, j) ≤ cE(i, j) and j µ(i,Σj) ≤ cV (i). It is maximal if it is not strictly dominated by any feasible µ′. The saturation level of i is j µ(i, j); it is saturated if this equals cV (i). An edge (i, j) is saturated if µ(i, j) = cE(i, j). (Note that contrary to convention, a self-loop (i, i) only counts once against the capacity of i, not twice.) Rounding Weights Down. Recall that if p participates in a blackboard BBt, that every other process can compute the weight vector computed from p’s local view BB(p,t−1) through blackboard t — 1. The processes use a unified weight vector in which wi is derived only from i’s local view:
