After I posted my code, a thought popped into my head regarding attempt-run-step and future-for-step - I think these can be broken down into a nice separation of concerns, which you've partially done already.

The separate concerns would be:
- Make sure the promise gets delivered
- Wait for all dependencies to complete
- Make sure the semaphore is acquired and released
- Run the actual step

It may be design overkill, but I think this separation makes sense and the code would be more bulletproof as a result.  

It is just as suggestion, I think the structure is fine as-is as well.