On start of the application we create singletons of our state machine backed services, and manage the dependencies between them manually. That is, we create an instance of the UserSessionService and then pass it into a "constructor" for the NavService. That constructing function creates the NavService and then wires them together by subscribing the NavService to listen to the state transitions of the UserSessionService.
I suppose if the code base grows and you have dozens of services to keep track of, it will get pretty unwieldy, but that is no different than using a fancy IOC container in Java/.Net. We plan on keeping things simple, while still braking apart the single store you'd have with Redux.
I hacked together a simple gist to show the basics of how we wire things together (without getting into the specifics of how the internals of the state machines work). [1]
[1] https://gist.github.com/adamkl/656008691d42220eddf8bfe147753...