6 ms·

State machines are a good solution when you have a typical transactional business process (order fulfillment, inventory management, etc). But I rarely see menti

State machines are a good solution when you have a typical transactional business process (order fulfillment, inventory management, etc). But I rarely see mention of messier problems which consist of overlapping and perhaps hierarchical states. For instance, let's say that are trying to execute a complex spread in the market. You might be partially filled on one leg (the timing of which is completely out of your control, if it happens at all). Then this needs to spawn an offsetting trade (or two), both of which may or may not be completely filled over multiple tickets. Super messy. A naive state machine simply doesn't work for this, as the overall unit of work (a "trade") can have multiple sub-states all operating more or less independently of one another. Are there well-known patterns to handle such situations?

Bjartr 3y ago
In terms of specific implementation I'm not sure, but it may be possible to use a formal modeling tool like TLA+ to prove a particular approach only results in outcomes you consider correct. So you could try to model the trade and all the sub states you mention in a naive state machine way, then check if that super messy tangle works as intended or if it has incorrect behavior.
rubyfan 3y ago
Can you share what your current solution looks like for something like that? > But I rarely see mention of messier problems which consist of overlapping and perhaps hierarchical states. Your comment resonated with me relative to regulated financial services where a relationship with a customer has many states can can be independent or intertwined depending on regulatory environment and subject matter i.e. status and renewal of terms of a contract/agreement, billing/payment, different pricing revisions, etc.
- winstonprivacy 3y ago
  Basically, lots of if...else statements combined with coroutines. Refactoring out as many big blocks of code helps a bit, but there's always yet another exception lurking in the shadows, waiting to show up at the least opportune time (such as when the system is under stress).
Pamar 3y ago
Not that I know of (so I'd like to see if someone can suggest anything). In practice, what I have always done is to decompose the "object" into a set of components. Each of these components can be in a number of states, and there are rules to set the header state depending on what the substates are. Practical example: ------------ Business order #2849 State: PSH (Partially shipped) Item 2849.01 State ONO (Ordered, not confirmed) Item 2849.02 State STR (Received, stored) Item 2849.03 State SSH (Shipped by supplier) Item 2849.04 State STR (Received, stored) ------------- Where the "business rules" are something like: * "If all items are SSH or better, status=SSH" * "If at leat one item is ONO, status=POR" (on order, not fully confirmed) ... Etc.
- winstonprivacy 3y ago
  That is precisely what I'm doing now and it's the best solution I've found so far. However it is brittle and it takes quite a long time to iron out the edge cases where things can happen that you didn't anticipate. I have one system that has been more or less stable for two months and once a week, it fails inexplicably (dumping no logs either). Whenever this happens, I find myself writing a ton of debug code hoping to catch it.
  - bdunks 3y ago
    I worked on a highly complex, high-volume automated procurement sourcing system many years ago. Each Purchase Requisition (PR) -> RFQ -> Bid Response -> Purchase Order could have many-to-many relationships, splitting & bundling at each line item (even the arrows above don't give the right idea, as things could go to re-bid, long-term contract with task orders, etc.). We tried for nearly two years to get the status/state of each PR line item to update in real-time as events occurred during follow-on steps, but it was extremely brittle. We finally added an intermediary queue and centralized all the logic in batch. Anytime something happened that might trigger a state (not verified), we tossed it in the queue. Then, we processed the queue every five minutes through a rules engine that was a classic factory pattern (a favorite anti-pattern). Every time the PR # ran through the rules engine, it would have a deterministic result. Sometimes it would pass through 10-20 times with no state change, but at least it was predictable. We thought it would be too inefficient, potentially processing the same PRs 100s of times without any actual change to the state. However, the servers handled it fine, and it was real-time "enough" the users didn't notice a lag. We went from fixing issues several times a week to no changes for the remaining two years I was on the project.
mcphage 3y ago
> But I rarely see mention of messier problems which consist of overlapping and perhaps hierarchical states. That's what State Charts were designed for: https://www.inf.ed.ac.uk/teaching/courses/seoc/2005_2006/resources/statecharts.pdf https://www.inf.ed.ac.uk/teaching/courses/seoc/2005_2006/res... It's used as the basis for a number of state machine / state chart libraries, for instance XState: https://xstate.js.org/docs/ https://xstate.js.org/docs/
friendzis 3y ago
> Are there well-known patterns to handle such situations? I'm not familiar with algorithmic trading so may be way off, but if I understand your problem correctly, it sounds like you need what is called parallel states: state machine where a "state" is in itself a state machine. The trick here is that transition of one "leg" can be transition trigger for another leg. In your example you would have 4 states: "Executing trade leg A/B" and "Executing balancing trade". Suppose trade A fills first (a complex machine in itself), it triggers leg B to terminate and transition to balancing trade state while leg A would transition to completion state.
- bheadmaster 3y ago
  I think the problem with parallel states is the combinatorial explosion of the number of transitions - instead of having O(n) transitions, now you have O(n_1*n_2*...*n_k) transitions between all possible k-tuples of parallel states.
  - friendzis 3y ago
    Um... No? Parallel (though hierarchical/recursive would be more fitting term) states are literally designed to fight combinatorial explosion of transitions. Qt docs provide nice, concise summary: https://doc.qt.io/qt-5/statemachine-api.html#using-parallel-states-to-avoid-a-combinatorial-explosion-of-states https://doc.qt.io/qt-5/statemachine-api.html#using-parallel-... Instead of transitioning on multiple parameters you decompose states into respective nested state machines to avoid this explosion
sesteel 3y ago
Look up HSMs.
- winstonprivacy 3y ago
  I've looked into HSMs and I don't think they are intended to handle this scenario due to the needed to be in multiple states at once. For instance, you partially fill one trade. This spawns a process which must then enter an offsetting trade for that partial amount. While this is going on, you may partially fill more of your initial trade, which then must spawn an offsetting trade for that amount (and so on). This quickly escalates out of control when you consider all of the possibilities which can happen at each state along the way (partial fills, cancels, connection issues, circuit breakers).
senkora 3y ago
I know I’m missing the point, but many exchanges have support for defining and executing spread strategies atomically.
sly010 3y ago
Just take the product of the two independent states. If you had 5 + 5 states, now you have 25 superstates each representing a potentially unique situation. As long as the sub-states are enumerable, the superstates will be enumerable too. One could argue this is exactly where state machines shine, because they allow you to methodically consider every condition.

Bjartr 3y ago

In terms of specific implementation I'm not sure, but it may be possible to use a formal modeling tool like TLA+ to prove a particular approach only results in outcomes you consider correct. So you could try to model the trade and all the sub states you mention in a naive state machine way, then check if that super messy tangle works as intended or if it has incorrect behavior.

rubyfan 3y ago

Can you share what your current solution looks like for something like that? > But I rarely see mention of messier problems which consist of overlapping and perhaps hierarchical states. Your comment resonated with me relative to regulated financial services where a relationship with a customer has many states can can be independent or intertwined depending on regulatory environment and subject matter i.e. status and renewal of terms of a contract/agreement, billing/payment, different pricing revisions, etc.

winstonprivacy 3y ago
Basically, lots of if...else statements combined with coroutines. Refactoring out as many big blocks of code helps a bit, but there's always yet another exception lurking in the shadows, waiting to show up at the least opportune time (such as when the system is under stress).

Pamar 3y ago

Not that I know of (so I'd like to see if someone can suggest anything). In practice, what I have always done is to decompose the "object" into a set of components. Each of these components can be in a number of states, and there are rules to set the header state depending on what the substates are. Practical example: ------------ Business order #2849 State: PSH (Partially shipped) Item 2849.01 State ONO (Ordered, not confirmed) Item 2849.02 State STR (Received, stored) Item 2849.03 State SSH (Shipped by supplier) Item 2849.04 State STR (Received, stored) ------------- Where the "business rules" are something like: * "If all items are SSH or better, status=SSH" * "If at leat one item is ONO, status=POR" (on order, not fully confirmed) ... Etc.

winstonprivacy 3y ago
That is precisely what I'm doing now and it's the best solution I've found so far. However it is brittle and it takes quite a long time to iron out the edge cases where things can happen that you didn't anticipate. I have one system that has been more or less stable for two months and once a week, it fails inexplicably (dumping no logs either). Whenever this happens, I find myself writing a ton of debug code hoping to catch it.
- bdunks 3y ago
  I worked on a highly complex, high-volume automated procurement sourcing system many years ago. Each Purchase Requisition (PR) -> RFQ -> Bid Response -> Purchase Order could have many-to-many relationships, splitting & bundling at each line item (even the arrows above don't give the right idea, as things could go to re-bid, long-term contract with task orders, etc.). We tried for nearly two years to get the status/state of each PR line item to update in real-time as events occurred during follow-on steps, but it was extremely brittle. We finally added an intermediary queue and centralized all the logic in batch. Anytime something happened that might trigger a state (not verified), we tossed it in the queue. Then, we processed the queue every five minutes through a rules engine that was a classic factory pattern (a favorite anti-pattern). Every time the PR # ran through the rules engine, it would have a deterministic result. Sometimes it would pass through 10-20 times with no state change, but at least it was predictable. We thought it would be too inefficient, potentially processing the same PRs 100s of times without any actual change to the state. However, the servers handled it fine, and it was real-time "enough" the users didn't notice a lag. We went from fixing issues several times a week to no changes for the remaining two years I was on the project.

mcphage 3y ago

> But I rarely see mention of messier problems which consist of overlapping and perhaps hierarchical states. That's what State Charts were designed for: https://www.inf.ed.ac.uk/teaching/courses/seoc/2005_2006/resources/statecharts.pdf https://www.inf.ed.ac.uk/teaching/courses/seoc/2005_2006/res... It's used as the basis for a number of state machine / state chart libraries, for instance XState: https://xstate.js.org/docs/ https://xstate.js.org/docs/

friendzis 3y ago

> Are there well-known patterns to handle such situations? I'm not familiar with algorithmic trading so may be way off, but if I understand your problem correctly, it sounds like you need what is called parallel states: state machine where a "state" is in itself a state machine. The trick here is that transition of one "leg" can be transition trigger for another leg. In your example you would have 4 states: "Executing trade leg A/B" and "Executing balancing trade". Suppose trade A fills first (a complex machine in itself), it triggers leg B to terminate and transition to balancing trade state while leg A would transition to completion state.

bheadmaster 3y ago
I think the problem with parallel states is the combinatorial explosion of the number of transitions - instead of having O(n) transitions, now you have O(n_1*n_2*...*n_k) transitions between all possible k-tuples of parallel states.
- friendzis 3y ago
  Um... No? Parallel (though hierarchical/recursive would be more fitting term) states are literally designed to fight combinatorial explosion of transitions. Qt docs provide nice, concise summary: https://doc.qt.io/qt-5/statemachine-api.html#using-parallel-states-to-avoid-a-combinatorial-explosion-of-states https://doc.qt.io/qt-5/statemachine-api.html#using-parallel-... Instead of transitioning on multiple parameters you decompose states into respective nested state machines to avoid this explosion

sesteel 3y ago

Look up HSMs.

winstonprivacy 3y ago
I've looked into HSMs and I don't think they are intended to handle this scenario due to the needed to be in multiple states at once. For instance, you partially fill one trade. This spawns a process which must then enter an offsetting trade for that partial amount. While this is going on, you may partially fill more of your initial trade, which then must spawn an offsetting trade for that amount (and so on). This quickly escalates out of control when you consider all of the possibilities which can happen at each state along the way (partial fills, cancels, connection issues, circuit breakers).

senkora 3y ago

I know I’m missing the point, but many exchanges have support for defining and executing spread strategies atomically.

sly010 3y ago

Just take the product of the two independent states. If you had 5 + 5 states, now you have 25 superstates each representing a potentially unique situation. As long as the sub-states are enumerable, the superstates will be enumerable too. One could argue this is exactly where state machines shine, because they allow you to methodically consider every condition.