Skip to content
Hallway
0:00 / 0:00

#movablefeastmachine#robust-firstcomputing#demonhordesort

Robust-first computing: Demon Horde Sort (full version)

Dave Ackley

6.1K subscribers • 5 videos on Hallway

YouTube
  • Recommended by 3 people: 3 on Hacker News.
  • A classic. People kept recommending it from 2015 to 2023.
  • Presented by Dave Ackley

Advanced. Deep dive for people who know the field.

14K views13 years ago3 recommendations

Computer scienceSystems programmingAlgorithmsData structuresConcurrency and parallelism

Dave Ackley demonstrates the Demon Horde Sort, an inherently robust sorting algorithm running on the Movable Feast Machine simulator.

A demonstration of the 'Demon Horde Sort', an inherently robust sorting machine. This is the uncut raw version, with all its details, repetition, and side thoughts. See youtube.com/watch?v=lbgzXndaNKk for a 12 min cut-down version.

Why it's here

3 people recommend this

What people say. Recommended as a fascinating demonstration of robust-first computing and fault-tolerant cellular automata architectures.

DonHopkinson Hacker News • Recommends

On “Robust-First Computing: Distributed City Generation (2015) [video]”

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 o…
View on Hacker News

DonHopkinson Hacker News • Recommends

On “Esoteric programming paradigms”

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 Arch…
View on Hacker News

Kapuraon Hacker News • Recommends

On “It Probably Works: Probabilistic algorithms are all around us”

Fantastic article. Probabilistic algorithm design is fascinating to me because it's all about making sure that the system behaves as expected, rather than every individual operation being perfect. Implementing most random algorithms in practise strongly reminds me of studies of populations & behaviours of organic life (which is much better than the rube goldberg/spaghetti factories which sometimes arise as "solutions" to complex problems). Another interesting related field is Dave Ackley's Robustness-First Computing model1, which operates with every atomic computational cell having some elements of randomness built in. 1 link to this video
View on Hacker News

DonHopkinson Hacker News • Recommends

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-…
View on Hacker News

DonHopkinson Hacker News • Recommends

On “A Conversation with Language Creators: Guido, James, Anders and Larry [video]”

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…
View on Hacker News

DonHopkinson Hacker News • Recommends

On “Can Programming Be Liberated from the von Neumann Style? (1977) [pdf]”

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 necessa…
View on Hacker News

camel-cdron Hacker News • Recommends

On “Artificial Life Creation T-0 and Launching”

As I understood it: The T2 tiles are "normal" microcomputers, that run a special software stack implementing the cellular automata. The tiles communicate over the connections, and essentially just act like a bigger automata grid. But the interesting part is that there is no global synchronization, and this architecture could be scaled indefinitely wide, by just adding more tiles. The impressive/hard part is creating the asynchronous automata, where each cell can only see a fixed amount of neighbors, and creating something from that. Edit: I think this video explained the general idea quite well: link to this video
View on Hacker News

justifieron Hacker News • Mentions

On “The Movable Feast Machine”

the 'grid' changing bounds is the intended mode of existence in regard to demon horde the paper(o) states 'channel size increases performance' but this should be uncontroversial more resources give better results it will be an optimisation problem to determine necessary resource alocation for desired results the shape of the simulation was stated(i) to be a simplified representation of the functionality the paper discusses 'a movable membrane whose contents cannot diffuse out', the figure is an almost organic shape, much more adaptable than the rectangular simulation demonstration (o) comjnl.oxfordjournals.org/content/56/12/1450.full.pdf+htmlb (i) link to this video
View on Hacker News

raidicyon Hacker News • Mentions

On “Self Replicating Computer Programs”

Is this at all related to "Robust-first computing"? I first heard about it from this video0? He calls it a "movable feast machine". What interested me about cellular automation is that in my reading of Neumann, it is said he was working on using cellular automata to construct fully replicating machines. It is also said he probably would have gone on to develop said architecture in full had he not died. Is your research in anyway related? I'm interested but woefully lacking in formal cs training. 0 link to this video
View on Hacker News

u/vanderZwanin r/ProgrammingLanguages • Mentions

On “Why async execution by default like BEAM isn't the norm yet?”

Well, I suppose that's mostly true in practice, but there are a few exotic options like Chuck Moore's GA144 chip (and then there's Dave Ackeys work, which is also really intriguing). Of course you won't run into those unless you actively seek them out, and by then you also either know what you're doing or are in the process of figuring that out. some links for the uninitiated: A blog summarizing what makes the GA144's ideas interesting: https://wildirisdiscovery.blogspot.com/2015/02/the-ga144.html Dave Ackey: link to this video
1View on Reddit