# Online cycle detection but not quite: the Featherstitch problem

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?

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