4 Characterization of \(\alpha ^*\)
For a graph assignment scheme on \(G = (V,E)\) and straggler probability \(p\), let \(G(p)\) be the random subgraph in which each edge of \(G\) is deleted independently with probability \(p\) (a straggling machine). The decoding vector \(w^*\) has one (possibly nonzero) coordinate \(w^*_e\) per edge \(e\) of \(G(p)\), and \(\alpha ^*_v = \sum _{e \ni v} w^*_e\) is the sum of weights of edges incident to \(v\).
For any edge \(e = (u,v)\) of \(G(p)\), the optimal \(\alpha ^*\) satisfies \(\alpha ^*_u + \alpha ^*_v = 2\).
At the optimum, the gradient of \(|\mathbb {1}- Aw|_2^2\) with respect to the free coordinates of \(w\) vanishes: \(0 = A^T(\mathbb {1}- Aw^*) = A^T(\mathbb {1}- \alpha ^*)\). The row of \(A^T\) indexed by edge \(e = (u,v)\) has ones exactly in coordinates \(u\) and \(v\), so \((1 - \alpha ^*_u) + (1 - \alpha ^*_v) = 0\), i.e. \(\alpha ^*_u + \alpha ^*_v = 2\).
For all vertices \(v\) in a single connected component of \(G(p)\), the value \(|1 - \alpha ^*_v|\) is the same.
For an edge \((u,v)\), Lemma 22 gives \(1 - \alpha ^*_u = -(1 - \alpha ^*_v) = \alpha ^*_v - 1\). Thus \(|1-\alpha ^*_u| = |1-\alpha ^*_v|\) across every edge, and this relationship extends through the whole connected component.
If a connected component of \(G(p)\) contains an odd cycle (is not bipartite), then \(\alpha ^*_v = 1\) for all vertices \(v\) in that component.
By Lemma 22 the sign of \(1 - \alpha ^*_v\) alternates along every edge of the component. Traversing an odd cycle returns to the starting vertex with the opposite sign, which is a contradiction unless \(1 - \alpha ^*_v = 0\) at every vertex of the cycle. By Lemma 23 the magnitude \(|1-\alpha ^*_v|\) is constant on the component, hence equals \(0\) everywhere, i.e. \(\alpha ^*_v = 1\).
If a connected component \(C = L \cup R\) of \(G(p)\) is bipartite with \(|L| \ge |R|\), then \(\alpha ^*_u = 1 + \tfrac {|L|-|R|}{|L|+|R|}\) for \(u \in R\) and \(\alpha ^*_v = 1 - \tfrac {|L|-|R|}{|L|+|R|}\) for \(v \in L\).
Each edge weight contributes to exactly one vertex in \(L\) and one in \(R\), so \(\sum _{u \in R} \alpha ^*_u = \sum _{v \in L} \alpha ^*_v\) (both equal the total edge weight). By Lemma 23, \(1 - \alpha ^*_v\) has constant magnitude on \(C\); by Lemma 22 it has one sign on \(L\) and the opposite on \(R\). Writing \(\alpha ^*_u = 1 + \delta \) on \(R\) and \(\alpha ^*_v = 1 - \delta \) on \(L\) and equating the two sums, \(|R|(1+\delta ) = |L|(1-\delta )\), which gives \(\delta = \tfrac {|L|-|R|}{|L|+|R|}\).
Given the set of non-straggling machines, \(w^*\) can be computed in \(O(m)\) time: perform a breadth-first search of \(G(p)\) to find connected components and the sides \(L,R\) of any bipartite component; set \(\alpha ^*_v\) on each component using Lemmas 24–25; then a depth-first search labels each edge with \(w^*_e\) so that the incident edge weights sum to \(\alpha ^*_v\).