Dave Ackley
3 HN recommenders · recommended in 8 months, 2015–2023
27:13 · 14K views · Jan 31, 2013
Dave Ackley demonstrates the Demon Horde Sort, an inherently robust sorting machine running in his Movable Feast Machine simulator. This is the uncut version with all details and side thoughts.
HN readers recommend it as the best introduction to robust-first computing, where randomness and fault tolerance are built into the architecture.
9 comments from Hacker News
A Movable Feast Machine [1] is a "Robust First" asynchronous distributed fault tolerant cellular-automata-like computer architecture. The video "Distributed City Generation" [2] demonstrates how you can program a set of Movable Feast Machine rules that build a self-healing city that fills all available space with urban sprawl, and even repairs itself after disasters! The paper "Local Routing in a new Indefinitely Scalable Architecture" [2] by Trent Small explains how those rules work, how the city streets adaptively learn how to route the cars to nearby buildings they desire to find, and illustrated the advantages of "Robust First" computing: Abstract: Local routing is a problem which most of us face on a daily basis as we move around the cities we live in. This study proposes several routing methods based on road signs in a procedurally generated city which does not assume knowledge of global city structure and shows its overall efficiency in a variety of dense city environments. We show that techniques such as Intersection-Canalization allow for this method to be feasible for routing information arbitrarily on an architecture with limited resources. This talk "Robust-first computing: Demon Horde Sort" [4] by Dave Ackley describes an inherently robust sorting machine, like "sorting gas", implemented with the open source Movable Feast Machine simulator, available on github [5]. A Movable Feast Machine is similar in many ways to traditional cellular automata, except for a few
I recently submitted a link about "Robust First Computing". It didn't get any response, but I'll repeat the link and description here, since it's certainly esoteric, but has some extremely important properties. Robust-First Computing: Distributed City Generation [LINK] A Movable Feast Machine [1] is a "Robust First" asynchronous distributed fault tolerant cellular-automata-like computer architecture. The video "Distributed City Generation" [2] demonstrates how you can program a set of Movable Feast Machine rules that build a self-healing city that fills all available space with urban sprawl, and even repairs itself after disasters! The paper "Local Routing in a new Indefinitely Scalable Architecture" [2] by Trent Small explains how those rules work, how the city streets adaptively learn how to route the cars to nearby buildings they desire to find, and illustrated the advantages of "Robust First" computing: Abstract: Local routing is a problem which most of us face on a daily basis as we move around the cities we live in. This study proposes several routing methods based on road signs in a procedurally generated city which does not assume knowledge of global city structure and shows its overall efficiency in a variety of dense city environments. We show that techniques such as Intersection-Canalization allow for this method to be feasible for routing information arbitrarily on an architecture with limited resources. This talk "Robust-first computing: Demon Horde Sort" [4] by
I've posted about this before, but it's worth repeating here: [LINK] DonHopkins on Oct 26, 2017 | parent | favorite | on: Cryptography with Cellular Automata (1985) [pdf] A "Moveable Feast Machine" is a "Robust First" asynchronous distributed fault tolerant cellular-automata-like computer architecture. It's similar to a Cellular Automata, but it different in several important ways, for the sake of "Robust First Computing". These differences give some insight into what CA really are, and what their limitations are. Cellular Automata are synchronous and deterministic, and can only modify the current cell: all cells are evaluated at once (so the evaluation order doesn't matter), so it's necessary to double buffer the "before" and "after" cells, and the rule can only change the value of the current (center) cell. Moveable Feast Machines are like asynchronous non-deterministic cellular automata with large windows that can modify adjacent cells. Here's a great example with an amazing demo and explanation, and some stuff I posted about it earlier: [LINK] Robust-first Computing: Distributed City Generation: [LINK] A Movable Feast Machine [1] is a "Robust First" asynchronous distributed fault tolerant cellular-automata-like computer architecture. The video "Distributed City Generation" [2] demonstrates how you can program a set of Movable Feast Machine rules that build a self-healing city that fills all available space with urban sprawl, and even repairs itself after disasters! The pa
Actually, the Moveable Feast Machine is a "Robust First" asynchronous distributed fault tolerant cellular-automata-like computer architecture that DOES reason about what might happen if computers randomly explode in mid-program! (One of my favorite topics, that I've written about in other threads!) [LINK] Check out how the city seamlessly regrows after you nuke it: [LINK] > Robust-first Computing: Distributed City Generation: A rough video demo of Trent R. Small's procedural city generation dynamics in the Movable Feast Machine simulator. See [LINK] for more information. And here's a robust, self-healing membrane, that tolerates random failures (like tiny little exploding computers): [LINK] >To demonstrate the robustness of three membrane implementations in the MFM, an instance of each was placed side by side and subjected to a failure probability of 5e-5 per site per EPS. That is, each site is erased, on average, every 20,000 event cycles. Intercellular Transport also demonstrates some robust chemical and biological programming metaphors: [LINK] >Two cells are interconnected by self-healing wire. The magenta substance is being passed from the cell in the west to the cell in the east. The black particles are an ectoplasm, allowing the membrane to identify sites outside of the cell. Similarly, the yellow and blue particles are an endoplasm specific to the cell in which they reside, allowing the membrane to identify sites inside of it. Demon Horde Sort exemplifies the Robust Fi
A "Moveable Feast Machine" is a "Robust First" asynchronous distributed fault tolerant cellular-automata-like computer architecture. It's similar to a Cellular Automata, but it different in several important ways, for the sake of "Robust First Computing". These differences give some insight into what CA really are, and what their limitations are. Cellular Automata are synchronous and deterministic, and can only modify the current cell: all cells are evaluated at once (so the evaluation order doesn't matter), so it's necessary to double buffer the "before" and "after" cells, and the rule can only change the value of the current (center) cell. Moveable Feast Machines are like asynchronous non-deterministic cellular automata with large windows that can modify adjacent cells. Here's a great example with an amazing demo and explanation, and some stuff I posted about it earlier: [LINK] Robust-first Computing: Distributed City Generation: [LINK] A Movable Feast Machine [1] is a "Robust First" asynchronous distributed fault tolerant cellular-automata-like computer architecture. The video "Distributed City Generation" [2] demonstrates how you can program a set of Movable Feast Machine rules that build a self-healing city that fills all available space with urban sprawl, and even repairs itself after disasters! The paper "Local Routing in a new Indefinitely Scalable Architecture" [2] by Trent Small explains how those rules work, how the city streets adaptively learn how to route the ca