Parallelizing combinatorial problems usually requires problem-specific synchronization: custom lock ordering, careful data partitioning, race condition analysis. Each problem gets its own parallel implementation, and the correctness argument is bespoke. If the problem structure changes, the synchronization strategy must be redesigned.
Alves and Garg (arXiv:2603.13147) observe that many combinatorial problems share a common structure: they can be expressed as reaching a state where no local predicate is “forbidden.” A forbidden state is one where a local condition is violated — a relaxation is needed for shortest paths, a proposal is unstable for stable marriage, a constraint is broken for scheduling. The solution is any global state where no local state is forbidden.
This structure forms a lattice: the set of all possible global states is partially ordered by a componentwise ordering, and advancing a forbidden local state always moves the system upward in the lattice. The key property (lattice-linearity) guarantees that advances from different components commute — doing advance A then advance B produces the same result as doing B then A. This means no synchronization is needed: threads can advance forbidden states in parallel, lock-free, and the system converges to the solution regardless of the execution order.
The framework LLP-FW implements this. The developer specifies only two things: how to check if a local state is forbidden, and how to advance it. The runtime handles parallelism, work distribution, and termination detection. Applied to seven problems (shortest paths, BFS, stable marriage, job scheduling, transitive closure, parallel reduction, 0-1 knapsack), the generic framework matches or approaches the performance of custom-built parallel solutions optimized for each individual problem.