Propagators

Please log in to watch this conference skillscast.

There are a lot of algorithms that revolve around iterating a form of information propagation until it attains a deterministic fixed point. CRDTs, Datalog, SAT solving, functional reactive programming, and constraint programming all fit into this mold.

One framework for these sorts of algorithms is the notion of a “propagator” due to Sussman and Radul, but until now little rigor has applied to know how such algorithms terminate with consistent results.

Another framework is Lindsey Kuper’s work on the notion of “lattice variables” (LVars), which addresses termination, parallelism and eventual consistency well, but not iteration.

By blending these frameworks, I’ll build up a series of sufficient conditions for propagators to terminate with consistent results and proceed to show how we can use this common framework to steal insights and quirks from each individual domain to try to optimize the rest.

YOU MAY ALSO LIKE:

• Unboxing Haskell (SkillsCast recorded in May 2022)
• Rust Nation 23 (in London on 16th - 17th February 2023)
• F# eXchange 2023: In-Person (in London on 7th - 8th March 2023)
• Source Talks: On Scala #4 (Online Meetup on 30th January 2023)
• Haskell In Person: Bring Your Project, Get help with your code & socialise (in Berlin on 1st February 2023)
• Teaching Haskell...To High Schoolers! (SkillsCast recorded in December 2022)
• Teaching Haskell...To High Schoolers! (SkillsCast recorded in December 2022)