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:

	/**
	@class connection connection.h
	@author Jeremy Thornton http://libfbp.blogspot.co.uk/
	@copyright Copyright (c) 2013 Jeremy Thornton - MIT License http://opensource.org/licenses/MIT
	@version 0.5
	@since 0.1
	*/
	#ifndef fbp_connection_h
	#define fbp_connection_h
	#include "connectable.h"
	#include <memory>
	namespace fbp {
	class output;
	class input;
	/**
	Template class connection is the abstract template constructed <i>type specific</i> communication API interface complement to the untyped connectable class from which it inherits. @see @ref connectable
	It is a libfbp design decision that all connections should be type specific on the basis that one simple principle should apply:</p>
	<b>That libfbp should strive to be run-time robust but compile-time brittle.</b></p>
	Clearly it is considerably better to discover an error at compile-time, reducing the time to discover the error and minimising its impact, rather than at run-time when in the hands of customers the impact of the error can be catastrophic!</p>
	This is where the strongly typed approach of libfbp to Flow-Based Programming excels, because the compile-time brittle gate-keeping is a powerful tool for preventing errors leaking out into the run-time user experience.
	<h4>
	Implementor Contract:</h4>
	However, the connection class template libfbp connection is not simply about the compile time it embodies the immutable contract that <b>all</b> concrete connections <b>must</b> comply with in order to work correctly with libfbp:
	<h4>
	Emergent Cascading Distributed Termination (ECDT)</h4>
	Whereby the libfbp component, viewed as an isolated push down automaton(PDA), either:
	<ul>
	<li>Reaches its own internal accept/final state and, as part of removing itself from the execution model's purview, &nbsp;closes all its connection(s).</li>
	</ul>
	or
	<ul>
	<li>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, &nbsp;closes all its remaining connection(s).</li>
	</ul>
	and so on.
	</p>
	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.
	</p>
	In order to acheive this the connection template has 3 <i>logical</i> states that throw 3 exceptions depending on wait-free or wait-on-full-wait-on-empty behaviour:
	<h4>
	Connection States:</h4>
	<ul>
	<li>full</li>
	<li>empty</li>
	<li>closed</li>
	</ul>
	<h4>
	Connection Exceptions:</h4>
	<ul>
	<li>if connection.send(...) <b>and</b> connection full throw queue_full_exception - this exception is <b>only</b> thrown by wait-free connections</li>
	<li>if connection.receive() <b>and</b> connection empty queue_empty_exception - this exception is <b>only</b> thrown by wait-free connections</li>
	<li>if connection.send(...) <b>and</b> connection closed throw queue_closed_exception - this exception is <b>only</b> thrown by wait-free connections</li>
	<li>if connection.receive() <b>and</b> connection empty <b>and</b> connection closed throw queue_closed_exception - this exception is <b>only</b> thrown by wait-free connections</li>
	</ul>
	</p>
	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. 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 resulting in its own graceful shutdown.
	</p>
	However, if a full—or rather a non-empty—connection is closed it does not immediately fail closed when a dequeue request is received 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.
	</p>
	This behaviour is defined in this dependancy inverting abstract template class for all libfbp connections.
	*/
	template<typename T>
	class connection: public connectable {
	public:
	/**
	A (logically) instantaneous type-safe Information Packet (IP).
	Morrison (J. Paul Morrison, Flow-Based Programming, 2nd Edition: A New Approach to Application Development, CreateSpace, 2010, ISBN 1-4515-4232-1) approaches describes Flow-Based programming (FBP) with the concept of an FBP Component ‘owning’ an IP or rather owning a ‘handle’ to its physical storage and that, importantly; an IP can only be accessed by its owner for the duration of that ownership.</p>
	In Morrison’s model it is the ownership of IPs that is transferred between Components and when the number of interested owners reaches zero the finite lifetime of an IP is up. At this stage the usual strategy of “garbage collection” by the system does not automatically destroy the IP but rather it must either be explicitly destroyed by a final owning process or serialized to storage.</p>
	With libfbp IPs the story is different. As described above Morrison is a proponent of what can be seen as a durability model for the IP, one where a program must deliberately destroy its IPs.</p>
	However, because libfbp has mathematical semantics derived from Sir Tony Hoare's Theory of Communicating Sequential Processes (CSP) (A model for communicating sequential process C. A. R. Hoare, 1980)
	wherein an event is "something" in which a process can participate and as such represents the communications or interactions that an FBP component can engage with, or in other words its behaviour.</p>
	In this way an event triggers a transition in the behaviour of a FBP Component as a conceptual CSP process and the IP element of the FBP narrative description maps, in an intellectually satisfying fashion, to the event of CSP Theory.</p>
	As per CSP Theory, axiomatically then, events are indivisible and instantaneous and can be communicated - which in popular variant(s) of the original CSP can be via named channels. The class of events that process can engage in is described symbolically in lower case.</p>
	Intuitively then the FBP Information Packet presents as the equivalent concept that maps to the CSP event. Being the communicated constituent that triggers behaviour or actions. But whilst an IP is communicated by named channels (FBP Connections) is it instantaneous and is it able to enforce a class or type of event?</p>
	As an alternative approach libfbp adopts the antithesis of Morrison's IP durability in order to meet the CSP requirement of an instantaneous event/IP. This is a deliberately more fragile model designed to meet the desired CSP compliance, whereby the information packet's existence must be deliberately maintained at each step in its life cycle otherwise its physical manifestation in memory is automatically deleted once the IP 'handle' leaves the local scope of the transition that it has triggered within the component.</p>
	To borrow Morrison’s memo metaphor, that was used an argument for IP durability in his book, libfbp CSP compliance requires that the memo only exists at the point at which it is sent, its creation, and the point at which it is received, its destruction. Whilst it may be copied on receipt the data is then an internal and invisible state of the component and only becomes externally visible to environment as an IP if it is sent again to another component.</p>
	This behaviour can be effected by using the C++11 std::unique_ptr. The first benefit from using a unique pointer is automatic destruction of the contained object when the pointer goes out of scope. This extreme form of garbage collection stands out in code hygiene freeing the programmer from having to track every possible exit point from a routine to make sure the object is freed properly — it is done automatically. More importantly, it will be destroyed if the component exits via an exception.</p>
	With the definition of type comes the concept of type-safety that ensures that only operations appropriate to that data-type are permitted to take place. C++ is a strongly typed language and offers data representation by type not restricted to in-built types but also user defined types and offers, despite some annoying inconsistencies, system level type safety.</p>
	An IP, which enforces the same type as the data to which it refers, is not only CSP compliant but prevents erroneous or undesirable program behaviour caused by discrepancy between differing data-types. Such discrepancies can be detected at compile time as well as runtime and help the libfbp programmer to avoid constructing an incorrect FBP program—a highly desirable correctness feature.</p>
	The aim being to twofold:
	<ol>
	<li>To maximize the static type checking that takes place when the program is being compiled from its C++ source code into a binary executable—such that a type unsafe libfbp program is brittle and will not compile but rather halt with an error.</li>
	<li>To provide dynamic type checking when the libfbp program is executing that invokes an exception handling response during execution, which by virtue of RAII permits the robust handling of such runtime errors.</li>
	</ol>
	It is proposed that this compile-time brittle, run-time robust approach to ensuring the correct handling of the correct data-types offers improved correctness and safety over any alternative approach to FBP implementation that is type ambiguous or type ambivalent.</p>
	In C++ implementation terms then, the desired instantaneous, RIAA, one-to-one relationship between IP & resource and type safety requirements can be achieved by using the std::unique_ptr language feature from the C++11 standard library.
	*/
	using ip_type = std::unique_ptr<T>;
	/**
	@param string <i>sender</i> The unique identifier <i>name</i> of the component using this connectable to send Information Packets
	@param string <i>receiver</i> The unique identifier <i>name</i> of the component using this connectable to receive Information Packets
	@param string <i>name</i> The unique identifier <i>name</i> of this connectable and hence connection.
	*/
	connection(std::string sender, std::string receiver, std::string name);
	/**
	This is the final API interface for receiving Information Packets (IPs)
	Because in C++11 the classic "throw' declaration excpetion lists is now deprecated @see http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2010/n3051.html then libfbp must rely on the implementor adhering to the contract expressed above.
	@return ip_type - The requested IP.
	@throws queue_empty_exception if the connection is empty.
	@throws queue_closed_exception if the connection is closed <b>and</b> empty - enables the reciever to empty the connection before receiving the closed exception.
	*/
	ip_type receive();
	/**
	Developed using C++11 the libfbp connection requires 2 send member functions.
	The first uses the familiar reference value semantics to an IP.
	@param ip_type& ip - An lvalue IP reference;
	@throws queue_full_exception if the connection is full.
	@throws queue_closed_exception if the connection is closed.
	*/
	void send(ip_type& ip);
	/**
	In order to permit move semantics for the IP expressed as a std::unique_ptr then an overloeaded send member function that accepts an rvalue must also exist.
	@param ip_type& ip - An rvalue IP reference;
	@throws queue_full_exception if the connection is full.
	@throws queue_closed_exception if the connection is closed.
	*/
	void send(ip_type&& ip);
	virtual ~connection();
	private:
	virtual ip_type do_receive() = 0;
	virtual void do_send(ip_type& ip) = 0;
	virtual void do_send(ip_type&& ip) = 0;
	virtual const std::type_info& do_packet_type() const;
	};
	template<typename T>
	connection<T>::connection(std::string sender, std::string receiver, std::string name): connectable(sender, receiver, name) {}
	template<typename T>
	typename connection<T>::ip_type connection<T>::receive() {
	return do_receive();
	}
	template<typename T>
	void connection<T>::send(connection<T>::ip_type& ip) {
	do_send(ip);
	}
	template<typename T>
	void connection<T>::send(connection<T>::ip_type&& ip) {
	do_send(ip);
	}
	template<typename T>
	const std::type_info& connection<T>::do_packet_type() const {
	return(typeid(T));
	}
	template<typename T>
	connection<T>::~connection() {}
	}
	#endif

view raw connection.h hosted with ❤ by GitHub

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

	#include "component.h"
	namespace fbp {
	component* component::operator()() {
	try {
	return run();
	}
	catch (que::queue_closed_exception) {
	return finally();
	}
	catch (que::queue_full_exception) {
	return on_full();
	}
	catch (que::queue_empty_exception) {
	return on_empty();
	}
	}
	component* component::on_empty() {
	return this;
	}
	component* component::on_full() {
	return this;
	}
	component::~component() {}
	component* component::skip = nullptr;
	}

view raw connection.cpp hosted with ❤ by GitHub

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