Emergent Cascading Distributed Termination - Graceful shutdown for libfbp

Lets stop monkeying around with termination in FBP 

TL;DR Herein proposed Emergent Cascading Distributed Termination (ECDT) whereby the libfbp component, viewed as an isolated push down automaton(PDA)[1], either:

• Reaches its own internal accept/final state and, as part of removing itself from the execution model's purview,  closes all its connection(s).

or

• Reacts to the closed exception(s) thrown by its connections(s) and reaches its own alternative, or only in some cases, final state and, as part of removing itself from the execution model's purview,  closes all its remaining connection(s).

and so on.

Thereby gracefully, and yet unknowingly, cascading the closed connections through the program graph ensemble of components allowing each to reach their final state and spread the cascade.

In order to retain the fungibility and black-box isolation requirements of FBP a component's terminating behaviour must be both dependency inverted, from an OOP perspective, and non-cooperative from a CSP theory perspective. With these immutable axioms in hand how then might libfbp not only terminate but do so gracefully?





Such a graceful exit—one where the components handle any remaining resources properly and then remove themselves from the execution model—arises freely as an emergent behaviour courtesy of the 3 states (as opposed to the tradition 2 states) of all libfbp connection type(s).

Emergent Behaviour Model of Termination

Emergent behaviour[3] is a process whereby at the level of larger entities (such as the FBP execution graph in toto) patterns, and regularities arise (such as a wave of self terminating libfbp components) through interactions among smaller or simpler entities that themselves do not exhibit such properties—in this case the ability to shutdown the whole FBP program.

Perhaps one of the best known examples of emergence is the flocking behaviour of birds which is modelled by the Boids program using small components that are unaware of the overall flocking behaviour being only aware of their immediate neighbours:

As previously explored the libfbp connection regards the connection as a resource for accessing information packets. A connection can connect in one of 2 modes, functions with one of 2 behaviours, has 3 states and throws 3 exceptions—of which one (and only one) must be thrown by all libfbp connections in all modes and all behaviours, namely the queue_closed_exception.

Connection Modes:

• multiple-producers-multiple-consumer (MPMC) 
• single-producer-single-consumer (SPSC)

Connection Behaviours:

• wait-free send(...) and receive() member functions - throws queue_closed_exception and queue_full_exception and queue_empty_exception
• wait on full send(...) and wait on empty receive() only throws queue_closed_exception

Connection States:

• CLOSED - when the connection resource is no longer required by either all producer(s) or all consumer(s).
• EMPTY - when the connection is unable to provide an IP to receive.
• FULL - when there connection is unable to accept an IP to send. 

Connection Exceptions for All Behaviours:

• if connection.send(...) and connection closed throw queue_closed_exception 
• if connection.receive() and connection empty and connection closed throw queue_closed_exception

Connection Exceptions for Wait-Free Behaviours:

• if connection.send(...) and connection full throw queue_full_exception
• if connection.receive() and connection empty queue_empty_exception

In other words, if a process is upstream of a connection that has been closed by its downstream receiving component then when attempting a, pointless, information packet send call on the closed connection said connection will immediately throw a closed exception. 

However, if a full—or rather a non-empty—connection is closed it does not immediately fail closed when a receive request is processed but rather waits until it also empty. This gives the downstream component chance to process the remaining information packets so that it can gracefully exit once the connection is empty of IPs.

Pushdown Automaton Model of Termination

Morrison[1] proposes the PDA as a model for the FBP component and hence state machine semantics can be used in examining the behaviour of libfbp components...

The sending component must now handle this closed connect exception and in doing so is able decide if the connection closed state will result in a deadlocked, and hence final, state for the component resulting in its own graceful shutdown. 

This behaviour is defined in the dependancy inverting abstract template class for connections:

This graceful exit on connection closure is embodied in the operator()() behaviour of the libfbp base component class:

It is true that, somewhat exceptionally I suspect, a component faced with closed upstream and/or closed downstream connections may be able to enter another live processing state but at least libfbp permits such alternative reaction by overriding the pure virtual finally() component member function.

Process Algebra Model of Termination

I have previously, hopefully successfully,  proposed the process algebra CSP [2]  provides mathematical semantics for thinking about Flow-Based Programming, and hence libfbp.

So, alternatively, looking at ECDT through the lens of CSP at the internal level of the libfbp component process then, termination is reached either through:

• internally evaluated success (✓ -> SKIP) 
• internally synchronised on the queue_closed_exception of any of its behaviour dependent connections after which it is deadlocked and, therefore, broken (deadlock -> STOP)

Which is a rather elegant description.

Conclusion

By viewing the connection as a resource that provides access to information packets and enabling this resource not only to be full or empty but also closed, and mandating this behaviour, then a component can recognise when it would otherwise enter a deadlocked state and initiate its own graceful exit. As part of this graceful exit process the component will close any remaining open connections and hence propagate this knowable deadlocked state. This propagation is done without component interdependency and results in an emergent cascading distributed graceful shutdown of the program execution graph.

Next time I will take a look at how libfbp implements one of the key elements of Morrison's description of FBP: Composite Components.

References:

[1] J. Paul Morrison, Flow-Based Programming, 2nd Edition: A New Approach to Application Development, CreateSpace, 2010,ISBN 1-4515-4232-1
[2] Communicating Sequential Processes
[3] Emergence

Credits

photo credit: pasukaru76 via photopin cc