Re:A conversation with Sussman on AI and asynchronous progra...
by edwardkmett on Thursday October 15, 2015 @10:21PM
(#10397134)
Without the propagators themselves being monotone they don't have enough to ensure determinism. They also don't have a guarantee of termination. e.g. repeatedly taking Heron steps on a rational interval approximation to compute the sqrt of 2 will continue to ascend the lattice indefinitely, as it isn't complete.
That said, they have many of the elements of the solution. With monotonicity this starts to resemble the more recent work on Lasp, which is being used explicitly to tackle the domain you mention: (strong) eventual consistency: or Kuper's work on LVars, where she drops the idempotent condition fairly early on in the thesis to get closer to CmRDTs, but which then burdens reads in a way that makes them automatically monotone.
The "propagator" paper would be more interesting if there was a use case in the paper. The basic idea is to have a graph of computational elements, but insist that the elements be commutative, associative, and idempotent. Under those restrictions, you get the same answer despite race conditions, which leads to a simple model of asynchronous programming. But what is this good for? I could sort of see a theorem prover that works like this. Beyond logic problems, it's harder to find an application.
This might be a good way to implement consistent-eventually systems. Those are hard to get right, and having to build them out of elements which have the propagator components might help. Not sure this is possible, but it's worth a try if you have to solve that problem.