Featherstitch (Frost et al., 2007) is an approach for representing data consistency requirements for disk storage. This question concerns a graph-theoretic problem (§4.1 in the paper) that its implementation requires, but the original authors sidestepped by using a relatively crude heuristic.

My take at formalizing the problem is as follows. There is a fixed set $B$ of blocks known ahead of time ($\lvert B\rvert\sim 10^9$ or so). There is, at each point in time, a directed acyclic graph $(P,D)$ of patches and dependencies (let’s say $\lvert P\rvert\sim 10^6$, $\operatorname{ord} p\sim 10^2$) and each patch $p\in P$ is associated to a single block $\operatorname{blk}p \in B$. A patch $p$ is said to head a block-level cycle if there is a path $p\to\cdots\to q\to\cdots\to r$ with $\operatorname{blk}p =\operatorname{blk}r\neq \operatorname{blk}q$; note that this is a stronger condition than $\operatorname{blk}p$ lying on a cycle in the “direct image” graph $(B, \{(\operatorname{blk}p, \operatorname{blk}q) \mid (p,q)\in D, \operatorname{blk}p\neq\operatorname{blk}q\})$.

Initially, the graph is empty. At each time step, either (1) a fresh patch is added to the graph, and all its dependencies are specified; or (2) a patch that does not depend on any others is removed from the graph, and all dependencies on it are discarded. The problem is to say, in reasonable time, (1) when a newly added patch heads a block-level cycle (no other block-level cycles can be created); or (2) which patches that previously headed block-level cycles no longer do.

I don’t expect there to be a ready-made solution, but does this at least look feasible or is it too similar to things that are known to be hard? What about if we allow for (not a lot of) false positives?

  • $\begingroup$ I don't see how to do better than online transitive closure, which will presumably be too expensive for your particular parameters. $\endgroup$
    – D.W.
    Commented Jun 18, 2021 at 2:47


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.