The main state machine for the GHS algorithm More...

#include <ghs.h>

Public Member Functions
	GhsState (agent_t my_id, Edge *edges, size_t num_edges)

le::Errno	start_round (StaticQueue< Msg, MSG_Q_SIZE > &outgoing_msgs, size_t &)

le::Errno	process (const Msg &msg, StaticQueue< Msg, MSG_Q_SIZE > &outgoing_buffer, size_t &sz)

bool	is_converged () const

size_t	get_n_peers () const

le::Errno	get_edge (const agent_t &to, Edge &out) const

bool	has_edge (const agent_t to) const

le::Errno	get_edge_status (const agent_t &to, status_t &out) const

le::Errno	get_edge_metric (const agent_t &to, metric_t &m) const

le::Errno	is_waiting_for (const agent_t &who, bool &out_waiting_for)

le::Errno	is_response_required (const agent_t &who, bool &response_required)

le::Errno	get_response_prompt (const agent_t &who, msg::InPartPayload &m)

agent_t	get_id () const

agent_t	get_parent_id () const

agent_t	get_leader_id () const

level_t	get_level () const

size_t	waiting_count () const

size_t	delayed_count () const

Edge	mwoe () const

le::Errno	checked_index_of (const agent_t &, size_t &) const

le::Errno	mst_broadcast (const msg::Type, const msg::Data &, StaticQueue< Msg, MSG_Q_SIZE > &buf, size_t &) const

le::Errno	mst_convergecast (const msg::Type, const msg::Data &, StaticQueue< Msg, MSG_Q_SIZE > &buf, size_t &) const

le::Errno	typecast (const status_t status, const msg::Type, const msg::Data &, StaticQueue< Msg, MSG_Q_SIZE > &buf, size_t &) const

Detailed Description

template<std::size_t NUM_AGENTS, std::size_t MSG_Q_SIZE>
class le::ghs::GhsState< NUM_AGENTS, MSG_Q_SIZE >

The main state machine for the GHS algorithm

GhsState is the message-driven state machine that executes the GHS algorithm. It receives incoming messages from a communication layer, and returns the next batch of messages to send. When completed, is_converged() will return true.

You are responsible for describing the communication graph by calling, probably, set_edge() and then starting the algorithm by calling start_round() on at least one node (the root), but most likely just call it on all nodes, which will generate the first set of messages to send.

Then, as response messages come in from other nodes, just feed them into process() until is_converged() is true.

Constructor & Destructor Documentation

◆ GhsState()

template<std::size_t NUM_AGENTS, std::size_t MSG_Q_SIZE>

GhsState::GhsState	(	agent_t	my_id,
		Edge *	edges,
		size_t	num_edges
	)

Initializes the state of the GHS algorithm for this particular node.

Requires a agent_t to represent the node id, which will be used in all incoming and outgoing mesasages (unique among all agents).

Requires a list of le::ghs::Edge structures that represent the communication links to other agents that will not be modified during execution.

The edge list may contain any number of edges (up to NUM_AGENTS). This class will ignore (not copy in) any edge that:

Is not rooted on this node (Edge.root != my_id)
Is directed to this node (Edge.peer == my_id)
Has either peer or root set to le::ghs::NO_AGENT
Has metric_val set to that of worst_edge()
otherwise does not pass is_valid()

The following conditions will produce undefined behavior:

Passing in two or more edges with the same peer and root

After the construction, you can verify the number of copied edges with get_n_peers().

Parameters

my_id	of type agent_t that tells the class which edges to consider
edges	a set of le::ghs::Edge structures, which are filtered and stored internally to determine message destinations.
num_edges	the length of the edge set

Member Function Documentation

◆ checked_index_of()

template<std::size_t NUM_AGENTS, std::size_t MSG_Q_SIZE>

le::Errno GhsState::checked_index_of	(	const agent_t &	who,
		size_t &	idx
	)		const

A much-called function that returns the index of the given agent. The index corresponds to a number 0 to N-1 for N agents, such that all data about that agent can be stored in consecutive memory. This is not a hash function! It simply searches as an O(n) operation, the memory for the matching ID.

Returns: le::Errno OK if the index was found; le::Errno NO_SUCH_PEER if not; le::Errno IMPL_REQ_PEER_MY_ID if you requsted index to this agent

◆ delayed_count()

template<std::size_t NUM_AGENTS, std::size_t MSG_Q_SIZE>

size_t GhsState::delayed_count ( ) const

Returns the number of agents from which we have received an IN_PART message that we have not responded to.

Returns: size_t

See also: set_response_required(); msg::InPartPayload; Msg

◆ get_edge()

template<std::size_t NUM_AGENTS, std::size_t MSG_Q_SIZE>

le::Errno GhsState::get_edge	(	const agent_t &	to,
		Edge &	out
	)		const

Populates the given edge with any stored edge that connects this agent to another agent. If we are unaware of that agent or do not have an edge, return error code.

Parameters

to	an agent_t to look up
out	and Edge to populate as an out parameter

Returns: le::Errno IMPL_REQ_PEER_MY_ID if edge has peer==my_id; le::Errno NO_SUCH_PEER if edge cannot be found; le::Errno OK if successful

See also: has_edge()

◆ get_edge_metric()

template<std::size_t NUM_AGENTS, std::size_t MSG_Q_SIZE>

le::Errno GhsState::get_edge_metric	(	const agent_t &	to,
		metric_t &	m
	)		const

Returns the edge metric to the given agent.

Parameters

to	agent_t identifier
m	the metric_t that is populated if the function is successful

Returns: OK if successful; le::Errno NO_SUCH_PEER if we cannot find the given agent id; le::Errno IMPL_REQ_PEER_MY_ID if edge has peer==my_id

◆ get_edge_status()

template<std::size_t NUM_AGENTS, std::size_t MSG_Q_SIZE>

le::Errno GhsState::get_edge_status	(	const agent_t &	to,
		status_t &	out
	)		const

Returns the edge status to the given agent.

Parameters

to	agent_t identifier
out	the status_t that is populated if the function is successful

Returns: OK if successful; le::Errno NO_SUCH_PEER if we cannot find the given agent id; le::Errno IMPL_REQ_PEER_MY_ID if edge has peer==my_id

◆ get_id()

template<std::size_t NUM_AGENTS, std::size_t MSG_Q_SIZE>

agent_t GhsState::get_id ( ) const

Returns whatever was set (or initialized) as the agent_t for this state machine

Never fails to return

Returns: agent_t for this class's id.

◆ get_leader_id()

template<std::size_t NUM_AGENTS, std::size_t MSG_Q_SIZE>

agent_t GhsState::get_leader_id ( ) const

Returns whatever I believe my leader is

◆ get_level()

template<std::size_t NUM_AGENTS, std::size_t MSG_Q_SIZE>

level_t GhsState::get_level ( ) const

Returns whatever I believe this partition's level is

◆ get_n_peers()

template<std::size_t NUM_AGENTS, std::size_t MSG_Q_SIZE>

size_t le::ghs::GhsState< NUM_AGENTS, MSG_Q_SIZE >::get_n_peers ( ) const

inline

Returns the number of peers, which is a counter that is incremented every time you add_edge_to(id) (or variant), with a new id.

◆ get_parent_id()

template<std::size_t NUM_AGENTS, std::size_t MSG_Q_SIZE>

agent_t GhsState::get_parent_id ( ) const

Returns whatever I believe my parent is

Returns: agent_t corresponding to the parent id. Could be self!

◆ get_response_prompt()

template<std::size_t NUM_AGENTS, std::size_t MSG_Q_SIZE>

le::Errno GhsState::get_response_prompt	(	const agent_t &	who,
		msg::InPartPayload &	m
	)

Returns the message that triggered a delay in response.

Parameters

agent_t	who sent the message
InPartPayload	the outgoing payload of the message that we cannot respond to yet

Returns: le::Errno OK if successful; le::Errno NO_SUCH_PEER if we cannot find the given agent id; le::Errno IMPL_REQ_PEER_MY_ID if edge has peer==my_id

◆ has_edge()

template<std::size_t NUM_AGENTS, std::size_t MSG_Q_SIZE>

bool GhsState::has_edge ( const agent_t to ) const

Returns true if any of the following will work:

get_edge()
set_edge_status()
get_edge_status()
set_edge_metric()
get_edge_metric()
set_response_required()
is_response_required()
set_response_prompt() 
get_response_prompt()

If it returns false, all of them will fail by returning something other than le::Errno OK.

◆ is_converged()

template<std::size_t NUM_AGENTS, std::size_t MSG_Q_SIZE>

bool GhsState::is_converged ( ) const

Returns: true if the state machine believes that a global MST has converged; false otherwise

◆ is_response_required()

template<std::size_t NUM_AGENTS, std::size_t MSG_Q_SIZE>

le::Errno GhsState::is_response_required	(	const agent_t &	who,
		bool &	response_required
	)

returns the response-delayed status for the given agent.

Parameters

agent_t	who
bool	waiting to send (true) or not waiting (false)

Returns: OK if successful and waiting_for is a valid return; le::Errno NO_SUCH_PEER if we cannot find the given agent id and waiting_for may have any value; le::Errno IMPL_REQ_PEER_MY_ID if edge has peer==my_id and waiting_for may have any value

◆ is_waiting_for()

template<std::size_t NUM_AGENTS, std::size_t MSG_Q_SIZE>

le::Errno GhsState::is_waiting_for	(	const agent_t &	who,
		bool &	out_waiting_for
	)

returns the waiting status for the given agent.

Parameters

agent_t	who
bool	waiting for response (true) or not waiting for response (false)

Returns: OK if successful and waiting_for is a valid return; le::Errno NO_SUCH_PEER if we cannot find the given agent id and waiting_for may have any value; le::Errno IMPL_REQ_PEER_MY_ID if edge has peer==my_id and waiting_for may have any value

◆ mst_broadcast()

template<std::size_t NUM_AGENTS, std::size_t MSG_Q_SIZE>

le::Errno GhsState::mst_broadcast	(	const msg::Type	,
		const msg::Data &	,
		StaticQueue< Msg, MSG_Q_SIZE > &	buf,
		size_t &
	)		const

Sends messages to MST child links only. There are very good reasons for using MST links even for non-ghs messages, so this is public.

For example, this ensures each node only receives one copy, even if it is a "bottleneck" leading towards many agents.

Functionally equivalent to:

Mst m;
StaticQueue buf;
size_t qsz;
return mst_typecast(MST, m.type, m.data, buf, qsz);

Parameters

msg::Type	denoting what type of message to send
msg::Data	denoting what message data to broadcast
StaticQueue	in which to queue the outgoing messages
size_t	denoting how many messages were enqueued only if OK is returned.

Returns: le::Errno OK if everything went well; CAST_INVALID_EDGE if we found an edge without us as root

See also: set_edge_status(); mst_typecast(); mst_convergecast()

◆ mst_convergecast()

template<std::size_t NUM_AGENTS, std::size_t MSG_Q_SIZE>

le::Errno GhsState::mst_convergecast	(	const msg::Type	,
		const msg::Data &	,
		StaticQueue< Msg, MSG_Q_SIZE > &	buf,
		size_t &
	)		const

The opposite of mst_broadcast, will send messages "UP" the MST to the root.

useful for conducting "reduce" operations on an MST, assuming it is combined with a useful data reduction strategy.

In GHS, the reduction strategy is to compare msg::SrchRetPayload from all incoming MST links, and pass the minimum weight edge up to the parent.

Is actually implemented with a search across all edges for one of type MST and with peer matching our parent id.

Parameters

msg::Type	denoting what type of message to send
msg::Data	denoting what message data to broadcast
StaticQueue	in which to queue the outgoing messages
size_t	denoting how many messages were enqueued only if OK is returned.

Returns: le::Errno OK if everything went well; CAST_INVALID_EDGE if we found an edge without us as root

See also: set_edge_status(); mst_typecast(); mst_convergecast()

◆ mwoe()

template<std::size_t NUM_AGENTS, std::size_t MSG_Q_SIZE>

Edge GhsState::mwoe ( ) const

Returns the current minimum weight outgoing edge (MWOE).

This is the edge we would add to our partition if you forced us to chose from our minimum spanning tree rooted at ourself. To find the global MWOE, these are passed UP the MST using mst_convergecast(), with a msg::SrchRetPayload. At each node, the msg::SrchRetPayload is compared to our mwoe() to determine the actual best edge all the way up to the root of the MST for this partition. After that, a msg::JoinUsPayload is sent back from the root using mst_broadcast() to trigger the process of adding that edge to the MST

Returns: size_t

See also: set_response_required(); msg::InPartPayload; Msg

◆ process()

template<std::size_t NUM_AGENTS, std::size_t MSG_Q_SIZE>

le::Errno GhsState::process	(	const Msg &	msg,
		StaticQueue< Msg, MSG_Q_SIZE > &	outgoing_buffer,
		size_t &	sz
	)

The main class entry point. It will puplate the outgoing_buffer with message that should be sent as a response to the passed-in message. You can execute the entire algorithm simply by calling process() with a msg::SrchPayload message properly constructed (but use start_round() for this), then feeding in all the response messages.

Parameters

Msg	to process
StaticQueue	into which to push the response messages
sz	the size_t that will be set to the number of messages added to outgoing_buffer on success, or left unset otherwise

See also: Msg; le::Errno

◆ start_round()

template<std::size_t NUM_AGENTS, std::size_t MSG_Q_SIZE>

le::Errno GhsState::start_round	(	StaticQueue< Msg, MSG_Q_SIZE > &	outgoing_msgs,
		size_t &
	)

ONLY IF this node is the root of an MST (even an MST with only itself as a member) THEN this function will enqueue the first set of messages to send to all peers, and set up the internal state of the algorithm to be ready to process the responses.

In short it:

checks to make sure we're not already in a search phase, exiting with error if we are.
resets the MWOE to a default value
creates a msg::SrchPayload and calls mst_broadcast()

Calling start_round() while in the middle of a round will essentially lose all state, such that incomign messages that are not a response to these outgoing messages will likely cause errors.

However, no edge statuses are changed, so executing start_round is safe if you already know of some MST links and have edited them in, or have somehow terminated a round and want to resume it.

Parameters

StaticQeueue	in which to enque outgoing messages
size_t	the number of messages enque'd

Returns: le::Errno OK if successful; le::Errno SRCH_STILL_WAITING if waiting_count() is not zero

Queue up the start of the round

◆ typecast()

template<std::size_t NUM_AGENTS, std::size_t MSG_Q_SIZE>

le::Errno GhsState::typecast	(	const status_t	status,
		const msg::Type	,
		const msg::Data &	,
		StaticQueue< Msg, MSG_Q_SIZE > &	buf,
		size_t &
	)		const

Filters edges by msgtype, and sends outgoing message along those that match.

Parameters

status_t	the edge status along which to send messages.
msg::Type	denoting what type of message to send
msg::Data	denoting what message data to broadcast
StaticQueue	in which to queue the outgoing messages
size_t	denoting how many messages were enqueued only if OK is returned.

Returns: le::Errno OK if everything went well; CAST_INVALID_EDGE if we found an edge without us as root

See also: set_edge_status(); mst_typecast(); mst_convergecast()

◆ waiting_count()

template<std::size_t NUM_AGENTS, std::size_t MSG_Q_SIZE>

size_t GhsState::waiting_count ( ) const

Returns the number of agents to which we have already sent IN_PART messages, but from which we have not yet received ACK_PART or NACK_PART messages.

Returns: size_t

See also: set_waiting_for(); msg::InPartPayload; Msg

The documentation for this class was generated from the following files:

include/ghs/ghs.h
include/ghs/ghs_impl.hpp

Public Member Functions

Detailed Description

template<std::size_t NUM_AGENTS, std::size_t MSG_Q_SIZE> class le::ghs::GhsState< NUM_AGENTS, MSG_Q_SIZE >

Constructor & Destructor Documentation

◆ GhsState()

Member Function Documentation

◆ checked_index_of()

◆ delayed_count()

◆ get_edge()

◆ get_edge_metric()

◆ get_edge_status()

◆ get_id()

◆ get_leader_id()

◆ get_level()

◆ get_n_peers()

◆ get_parent_id()

◆ get_response_prompt()

◆ has_edge()

◆ is_converged()

◆ is_response_required()

◆ is_waiting_for()

◆ mst_broadcast()

◆ mst_convergecast()

◆ mwoe()

◆ process()

◆ start_round()

◆ typecast()

◆ waiting_count()

template<std::size_t NUM_AGENTS, std::size_t MSG_Q_SIZE>
class le::ghs::GhsState< NUM_AGENTS, MSG_Q_SIZE >