state machines & non-blocking algs

Chris Purcell writes:

Re. your talk: State machines permeate my algorithms, too. I suspect it’s because they are easy to do atomically, make the “progress” through an algorithm obvious (simplifying concurrent assistance), and make enumerating all cases (the bane of lock-free algorithms) both explicit and fundamental.

This is absolutely the Right Thing To Do here.  The hardware guys have been using State Machines for years to do concurrent algorithms – in hardware.  That is, they have tool support such that they can write large State Machines, have the description maintained by many people (CVS for State Machines?), automatically tested, executable code generated (Verilog), etc.  I think the concurrent algorithms crowd definitely needs to head down this road as well.


Published by


This is the "wpengine" admin user that our staff uses to gain access to your admin area to provide support and troubleshooting. It can only be accessed by a button in our secure log that auto generates a password and dumps that password after the staff member has logged in. We have taken extreme measures to ensure that our own user is not going to be misused to harm any of our clients sites.