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

[@PunmasterSTP]

Robust-first computing? More like "Really cool ideas that are interesting!" Thank you for sharing all of your creations and insights.

[@DaveAckley]

*Google backs robust-first computing* I'm thrilled that the Google Research Awards program (googleresearch.blogspot.com/2013/08/google-research-awards-summer-2013.html) is funding my proposal to build an open-source simulator for the Movable Feast Machine! This video from February sketches an example.

[@Unhacker]

I think I'll make a loop of the 'nuke/recovery' cycle to use as a screen saver, because it's the coolest thing I've seen a computer do in a long time. Machine, heal thyself! Btw 26:20 is just priceless. Cheers.

[@Broadsmile1987]

I find it really amazing, but it only seems to make sense if implemented in hardware, e.g. by replacing transistors with living cells and modifying their DNA, disassembling them (well… killing them), and building them (DRegs would be factories). However, given current technologies it could be possible to create a GPU-like architecture, where every cell in the grid has capabilities of all possible units, including being able to be reprogrammed by other cells - DRegs and sorters in this case. Actually it makes a lot more sense to implement this on GPU architecture instead of CPU, except for there are some caveats that others have already spotted like the concurrency. In GPU every pixel (cell) is concurrent meaning that the source is not modified until all cells evaluate - at which point the result becomes the source. But it seems only simple tweaks are needed, at least in this example: sorters instead of reading randomly, would read their right neighboring cell - it is their movement (diffusion) that would randomize the position of their input. Alternatively data could be duplicated, but it could have a unique ID, meaning that the output can actually find out the byte/word/dword number which is duplicated or which timed out and should be reinserted into the input.

[@KeithWiley]

So, I was reflecting on this in a bout of insomnia and it struck me that there may be a considerably simpler way to accomplish a very similar behavior or effect to the Demon Horde Sort. What if the "field" didn't contain the various heterogeneous "species", but rather just the numbers to be sorted, nothing else (or possibly the sources and sinks if you like, but no DRegs, Rezs or Sorters). The numbers have only two rules. One, they generally wander around in a Brownian or drunken way (or perhaps with a very weak "wind" to push them from the sources to the sinks)...and two, if they come into contact with another number, they ricochet in a biased manner, higher numbers ricocheting up and lower numbers down (or vs/va, whatever). That's it, that's the whole thing. Obviously, this could only be called Cornflake Sort for reasons too self-evident to explain. Would that essentially accomplish the same behavior (and the same overall robustness goals) of the Demon Horde Sort? I feel like I've missed the point of a lot of the complexity when all I think is going on is emulating shaking a box of cereal (which is, needless to say, a very cool and extremely parallel way to sort). Thoughts?

[@DaveAckley]

I think it would be similar. Tuning the 'wind' might be tricky, and I'd expect the quality of Cornflake Sort to decline quite precipitously at low data rates. The Sorters, in effect, generate proxy Data-Data interactions, in a relatively -- though not entirely -- rate-insensitive manner. And in the bigger picture, for me the DHS demo is largely about trying to understand basic -- and hopefully reusable -- robust computing mechanisms. Density regulation by DReg and Res, for example, seems like a good candidate for one such basic mechanism. (Actually, DHS demos, plural -- e.g., nm8.us/j has an even more complicated version employing 'DNA like' programmable molecules.)

[@KeithWiley]

Yes, I see how the other entities in the DHS are doing a lot of interesting thermostat-like feedback regulation (as you said, of the density for example). That's cool. I wonder what other entities you can create...orrrr...could you evolve a diverse ecosystem of randomized entities that perform various functions which are then culled and selected based on their utility for certain tasks? Yeesh! Meh, this could get away from you pretty quickly. Best to stay on target I suppose.

[@DaveAckley]

:) Focus is important, but truly, we need people exploring in all directions around the robust-first computing core. I'm going to be offering a 'Robust Alife' project seminar this Fall, toward that end.

[@LeExistentialRealist]

As a person with a great interest in AI, and as someone who has formulated a similar idea (independent agents interacting with eachother) I'm truly fascinated with your concept of the movable feast machine, and on a larger scale, the "robust first" approach to computer science. However, I'm interested to hear your opinion on possible software based implementations of your robust-first system in terms of applications in business information systems, and how such a concept could be efficiently integrated into modern systems, providing users with the accuracy they want, with the robust reliability they need.

[@DaveAckley]

For now it's basic hardware/software architecture R&D. Perhaps future robust systems will integrate more with people and the real world than with old-fashioned computers!

[@faster-than-light-memes]

Oh my God. it's so joyful

[@C4Par1]

Thanks Dave, great presentation about a very interesting idea. How would you introduce anti-fragility into this system, if at all?

[@DaveAckley]

The primary antifragility I'm aware of in the DHS is that, within limits, it sorts *better* as the data rate increases, like exercise for a sorting muscle.

[@StephenPaulKing]

Think: Botnet. One where people willing DL and install a client that runs in their devices and the messaging between the bots implements the GRID.

[@Volvith]

"In a way it's a lot more like the way society computes..." Oh boy... :P

[@DaveAckley]

..says the human on the internet :)

[@MrC0MPUT3R]

+Dave Ackley Will we have troll units? :P

[@DaveAckley]

Basically, whatever programming language you know or wish to know. This video used Java; I also frequently use C++. I'm mostly unfamiliar with alife programs or packges.

[@AlfonsoFR1978]

Hi professor: I'm curious to know if the grid is topologically cilindrical (ceiling and floor ends meet) or just rectangular (my assumption) and how inverting that would impact the sorting performance. Also if there is any version of the software that uses hexagonal or triangular grids instead. Finally, for a challenge: if are there any implementations that run on a 3D grid. Or, better, an n-dimensional grid built either on the edges of regular simplexes, or from the edges of some other tesellation of hyperspace.

[@DaveAckley]

Alfonso F R Our grids are typically flat and have edges, as here. We have explored only rectangular meshes, mostly in 2D. For implementability we admit at most three scalable dimensions, though additional finite dimensions are possible.

[@WhatsACreel]

Your videos are brilliant! The information, style and format is excellent! I've uploaded more than 100 videos and I like your format far more than my own (and more than any computing videos I've seen). I'd like to use the same format in my own videos (naturally, crediting you unless you'd prefer me not to). If you don't mind my asking, what do you use to record? I mean, it looks like Ubuntu, but how do you get an overlaid application running on the side? Surely this wasn't added in editing, you seem to be manipulating it on screen... And, what program is executing, are those custom built simulations? Sorry to bother you if you're busy, thanks for the thought provoking and entertaining videos, and have an excellent day!

[@DaveAckley]

Hi and thanks for the kind words! It is Ubuntu. I capture (pseudo) HD from an external camera via firewire with dvgrab, while also capturing the screen (and USB audio) using ffmpeg. Afterwards I composite them in Kdenlive with a 'lighten' transition to do a pixel-by-pixel max. The workflow's a little rickety and the final render is slow, but it's tolerable overall --- though I'm nowhere near 100 videos! The demos are usually custom Java code. Have a good day!

[@DaveAckley]

DB Here's an old comment sketching the workflow I use for the videos.

[@noxabellus]

I assume this is non-deterministic on the order of cell updates? The only thing I have seen similar to this was while following the development of in the game Factorio. They were looking for a method of multi threading their grid world system for their game, but several systems rely on perfectly deterministic order of execution. So, in order to do that they had designed a theoretical system that would update the grid world in these alternating 3x3 event windows. I believe they ended up not building it because it was deemed too complex. The game is still CPU bound, but years of optimizations have moved the boundary much higher.

[@DaveAckley]

Yes, site updates are random. Initial assumptions of determinism are hard to undo, but deterministic or not these systems really want massive parallelism to shine. Thanks for the comment!

[@fixfaxerify]

This is really cool. Although I don't really understand how exactly the grid relates to hardware, is an atom like a physical hardware node? If so, just curious, what kind of hardware only has a few dozen bits these days? Cheers:)

[@maersklandro]

How do you simulate the concurrent / unsynchronized, disordered simultaneous processing by all the different sorters and other entities (calling them entities cause I forgot what you called them)? Do you pick them at random each frame to get their turn to do their stuff? After each of them which has had its turn this frame, do you pick the next one randomly from those who've yet to have their go this frame, ensuring that each entity gets one operation - no less or more - each frame, or do you pick randomly from all currently remaining entities - including those which have already had their go this round, thereby conceivably allowing some to do more than one operation per frame while others do none? How does this simulate two different entities both reading, writing or deleting from the same square or writing or deleting from the same square or reading from a square being written to or deleted or writing to or deleting a square being read from by another entity, concurrently? It would seem to me that you're probably simulating the entities sequentially rather than concurrently. You'd need a separate execution thread running on a separate physical processor core, all reading and writing to the same memory pool without any semaphores, synchronization or other access restrictors or sequencers, for each entity in order to simulate them concurrently. You'd basically need to run the simulation on a GPU in order to simulate all entities concurrently, I think. I'm not sure even that would do it.

[@DaveAckley]

Much more detailed information at nm8.us/2 . This video's simulator was single-threaded; the tile-based simulator in, say, kzbin.info/www/bejne/hKK2n6KAYrt6fpY , uses a thread per tile. A single atom has exclusive access to its window during a single event, even if the window spans multiple tiles. The goal is indefinite scalability while balancing concurrency and programmability. Thanks for the thoughts!

[@maersklandro]

Thank you for the reply and the link. I have a few more questions about the actual implementation (chief among which being how the neighbouring tile locking mechanism works and what is the likelihood of two neighbouring entities' locked tile areas overlapping because they simply happen to check whether the same tiles are free and lock them at the same time) to which I'm sure I will find the answers in the paper you linked to. I think it will be a very interesting read. Your ideas are fascinating and possibly revolutionary. If somewhat hard to accept for someone who can not countenance a technical approach to computation wherein there is a definite, not negligible, probability of a non-heuristic algorithm not returning a 100% correct result.

[@lionelta]

Awesome.

[@stimpyfeelinit]

should use the geometry of the empty space that is created by dreg to stuff in more information

[@mariocosta6376]

Hi Dave, So the intent of this programing model is for a new hardware/software concept !? Or for large scale, cloud computing ? Or scalless !? Nice videos, thanks!

[@DaveAckley]

Mário Costa Yes! Thanks for checking out the videos.

[@sahinhabesoglu510]

This reminds me of Conway's Game of Life somehow.

[@jamesmathai1138]

Sahin Habesoglu To me it just seems like the same idea with more complex rules.

[@morgandavies2534]

There's one thing I don't understand. When each window area is selected we have to lock the cells involved. Doesn't this necessitate something to fulfil the responsibility of coordinating them? Once you've got a coordinator does it not introduce a single point of failure?

[@T2TileProject]

Indeed, if the main thread in that 2013-era simulator blew up, all event processing would stop. With indefinitely scalable hardware like the T2 tiles, though, such a failure would only extend to the tile where it occurred.

[@morgandavies2534]

@@T2TileProject Thanks for your response! I'll look into that, do you have a specific video / article you'd like to recommend to help me understand how it's achieved?

[@wayneworkman2012]

How can Demon-horde sort be implemented for real-life problems? What would the hardware look like? What sort of stuff could it sort? Also, a more important question would be... What sort of data comes endlessly that ALSO needs sorted? I'm thrilled by what you've accomplished, but I'm trying to wrap my head around how it could be useful.

[@DaveAckley]

Wayne Workman This is pretty basic research right now. But in principle, consider packets arriving at a router.

[@wayneworkman2012]

***** This is your research, clearly (and bravo, well done!). But, I'd like to make a suggestion. How about... instead of linear from right to left... How about making the inputs scattered throughout, and the outputs scattered throughout. And make it so inputs can also be outputs. This, IMO, instead of being a robust-first sorting engine, could instead be a robust-first path finding engine. The dreg, instead of just moving stuff up or down based on the data's value, it could move it up, down, left or right... and eventually... the data would "Find it's way" to the destination. I think it's possible that if you could accomplish this, you might be able to take that model and apply it directly to packet routing... But, you might think... the physical lines of the internet can not be moved... but YOU are ALL about ROBUST FIRST, and you know that if a line gets chopped somewhere, it's done... Look at the cellular devices we have today... They have 4G-lte, it's crazy fast, and cell phones have a very long range. Cell phones also move around. What if... dreg could be represented by cell phones, and cellphones could communicate to other cell phones without the need for a tower, and that data could slowly but surely flow from one cell phone to the next, eventually (robust first) reaching it's destination.... Think about a swarm of robots... Each one having a limited range for wireless communications... but one robot needs to send a message to another robot that's far away. Without any one robot knowing where the other is, but just being able to give a good guess at it... you could probably send data to the (most probable) next closest robot. If you apply this to cell phones or swarm robots, either way, they would all have to sometimes "Broadcast" where they are, so that others around them would know where they were. Maybe we could communicate more about this via email? [e-mail]

[@Em3rgency2]

Wayne Workman That would defeat the whole purpose. The data needs to go through as many sorters as possible. The more sorters a blue node meets, the more accurately it gets sorted. Additionally, how would a sorter know which direction to sort in? If you scatter inputs and outputs throughout, you would input random data and output random data...

[@DaveAckley]

Tadas Juscius , Wayne Workman I agree with both of you! Note in the paper ( nm8.us/y ) associated with the new video , there is an example (but not a lot of details) of a simple router implemented in the 'Feast.

[@imode256]

Big question: what's the backing language for the logic of the elements? Is it imperative or pattern-based?

[@T2TileProject]

That DHS version was written in Java! More recent versions have been ulam (imperative) and SPLAT (pattern-based).

[@youngbloodbear9662]

I’m a big fan of dynamic system regulation like this, but how exactly is this architecture going to work to do something more complicated like play a game? I’m not seeing the bridge from the first steps to running a program

[@DaveAckley]

It's a long road, but the T2 Tile Project has been fleshing out more complicated things since 2018 kzbin.info/door/1M91QuLZfCzHjBMEKvIc-A

[@SonOfSofaman]

Would the demon horde be more robust in higher dimensions?

[@Bunnokazooie]

How does this relate to the Actor model?

[@AlfonsoFR1978]

On a second though, at the beginning of the video you said that the demons can not access the global state of the machine as they only compute on their own. But, woulnd't that be a false assumption, given that the are instantiated to be spawned as a specific "kind"? The table that contains these categories must be global, right? A truly autonomous agent would not have a preset type, but rather evolve to be of a member of a kind by studying its environment (in a ways like childrens grow up to choose a career, for instance)

[@DaveAckley]

Alfonso F R Yes, we presume the 'table of elements' is copied to all tiles, so changing 'the laws of physics' is at best slow and disruptive, and may even become impossible as the technology matures. It's the earliest days, but we envision complex agents as large structured collections of atoms.

[@lionelta]

Where can I download the open-source simulator?

[@DaveAckley]

The current simulator is at github.com/DaveAckley/MFM. The easiest way to get started is installing the ulam compiler via the Ubuntu PPA at launchpad.net/~ackley/+archive/ubuntu/mfm

[@bibliusz777]

relay migration

[@toyonohoshi]

thanks for ur reply ^ ^ I'm thinking to invest some time on Maya MEL! again...I hope u upload more vids...you'r explanations are smooth and pleasant :) a true mentor quality

[@StephenPaulKing]

How could we show that robust-first is better than CEO for random bit flips in an arbitrarily long sequence of computations?

[@DaveAckley]

Stephen Paul King Because in that case CEO will crash almost surely? In general the question isn't answerable until one postulates some error metric on the computations to determine 'how good is good' among outputs that might be wrong or missing.

[@StephenPaulKing]

AFAIK, random bit flips are corrected by error correction schemes in CEO. Robust-first computations deal with such by culling them, a Darwinian process.

[@DaveAckley]

Stephen Paul King Yes, many problems are fixed by ECC. Fault tolerance folks talk of three (CEO) responses to an uncorrected bit flip: Crash, Hang, and (my favorite) Silent Data Corruption (SDC), which is basically 'everything else'.

[@n-clue2871]

i know this is old, but can i ask, what are the exact chances of a DReg doing things?

[@DaveAckley]

For that ancient Java demo, I'm not now certain, but it wouldn't be that different than the current code at github.com/DaveAckley/ULAM/blob/develop/share/ulam/core/DReg.ulam There, per event, it's 1-in-1000 to create a new DReg if an empty site is chosen, 1-in-200 to create a new Res assuming a DReg was not created, 1-in-10 of destroying a DReg if an occupied site containing a DReg is chosen, and 1-in-100 of destroying anything if an occupied non-DReg site is chosen.

[@n-clue2871]

@@DaveAckley thanks! i kinda just chose some random numbers based on the limited info given here

[@DaveAckley]

The behavior is pretty robust!

[@toyonohoshi]

a little question if I may ^ ^ what kind of programs and programming languages you recommend for alife design?

[@carsonscott260]

reminds me of postmodernism

[@brendawilliams8062]

Makes me think artificial was a good name. WHO would thought this was a good idea. It worked. That is good