Negotiation algorithm

The workflow in 4 steps

1. Each tool in the sgsh graph registers its identity and constraints on its I and O channels. In this way, each node's edges, that is the topology of the graph, for both input and output channels are recorded.
2. The algorithm tries to satisfy the constraints per tool per I/O channel in the most basic way.
3. The algorithm tries to optimise the solution by leveraging any flexible constraints of tools in the graph.
4. Tools receive the appropriate communication endpoints and begin execution.

SGSH negotiation specifics

Sgsh-aware programs in sgsh pipelines =|=

• are connected with a socketpair and negotiate through it by passing packets from one end of the sgsh-aware pipleline to the other.
• have an environment variable SGSH_IN SGSH_OUT set to know on which end they can negotiate.
• Each program with SGSH_OUT && !SGSH_IN starts the negotiation and continues by reading, writing on its output fd.
• Programs with SGSH_IN && !SGSH_OUT read and write on their input fd.
• All other programs start by reading from the input side and writing to the output side, and then alternate I/O directions.
• The message block contains
  • the process id of the program that created it,
  • the graph of connected programs,
  • the number of I/O channels each one provides and requires,
  • the run flag,
  • the error flag,
  • (The number of I/O channels can be -1 to denote flexibility.)
• Each change in the message block increases the block's serial #.
• Programs that fail their argument processing set the message block error flag.
• Programs that see a message block with a creator process id higher than the creator process id of another message block they have already, silently drop it. This takes care of multiple programs starting the negotiation.
• Programs that have seen the same serial # twice, when they see it again:
  • Run the algorithm to allocate I/O ports along the graph
  • Set the run flag if a solution is found
  • Set the error flag and print an error message if the negotiation requests cannot be satisfied
  • Set the ID of the process that passed them the message block
• Non-terminal processes that get the message block with the run flag set a second time and terminal processes that get the message block with the run flag set:
  • Pass the block (except for the process whose ID is set)
  • Create required output pipes
  • Read input fds from their input side
  • Write output fds to their output side
  • Start running
• Non-terminal processes that get the message block with the error flag set a second time and terminal processes that get the message block with the error flag set:
  • Pass the block (except for the process whose ID is set)
  • Exit with a non-zero exit code

Within the {{ }} block executable commands and {{ }} blocks can offer multiple inputs or outputs. All other structures offer a single I/O.

At the beginning and the end of the {{ } block an input and output concentrator receives the negotiation ports and plain I/O ports of the commands within the block and negotiates with the block's communicating parties. Negotiation from multiple input programs is received on ports 0, 3, 4, ... while negotiation to multiple output programs is sent on ports 1, 3, 4 , ...

When sgsh is run it passes SGSH_IN (if set) to the first process of the script, and SGSH_OUT (if set) to the last one.

An sgsh {{ }} block with more than one input and SGSH_IN not set, or more than one output and SGSH_OUT not set terminates with an error.