What is State?

[PatternStorm]

Hi all,

recently there has been some dicussion on the relationship between states and events. You can find a short discussion showing that states are (sets) of sequences of events here => http://tech.groups.yahoo.com/group/CEP-Interest/files/ : just open the file "What Is State.pdf"

What follows are answers to objections and comments to my comment to the following blog entry http://www.thecepblog.com/2008/07/15/co ... omment-637 where I stated that states are just composite events.

Tim -> I do think the event-model should not require designers to force all state-transitions to be modelled as events
Answer -> Neither I, the event model must allow modelling state as sequences of events but surely not force it.

Tim -> For example, the level of fuel in a fuel tank can be modelled as event-state changes (as you mentioned), or it can simply be a property that presents the state at a point in time, a tuple.
Answer -> Of course, you can and should do that if you are not interested in tracing how that state changes according to input, however, either you make it explicit or nor in your model, in the end each value of the tuple is representing an equivalence class of sequences of inputs.

Tim-> So, I guess it depends if you are modelling the nodes (the state) or the arrows (the state transition), so to speak.
Answer -> If you look at state from the sequence-of-events point of view transitions and states are not ditinguished anymore: you just have states, each one corresponding to a set of sequences of events, in this case transitions are encoded in the states themselves: let's say you history of events is e1...en and that this sequence belongs to state S1, then you receive event en+1, what is the next state? Just the state that contains the sequence e1...en.en+1. So, there is no such thing as modelling the state or the transitions, everything goes together, but by looking at states as sequences of events you model both using the same basic constructs: composite events.

Paul -> “states are sequences of events”
I’m not sure I agree with that.
Answer -> Please see "What Is State.pdf" at http://tech.groups.yahoo.com/group/CEP-Interest/files/

Paul -> My current state is that I’m sitting here in a hotel room. How is this state = to a sequence of events? It is a *consequence* of a sequence of events, for sure (airplane landed, caught a taxi, slept through alarm call, …).
Answer -> This is not your current state but the state of the universe around you (which includes you) Now that state might turn out to be just the sequence of events that you mention (and lot's more that you don't mention). Of course you can just represent or communicate that state with a sentence "Im sitting here in a hotel room" but the state is "physically" the sequence of events in the universe that took you to that point in space-time so to speak...

Peter -> Not sure I understand the statement “states are sequences of events” as a general purpose definition
Answer -> Not sure I understand what's a "general purpose definition"

Peter -> When I think of states, I think of transactions or finite state machines. A system could receive a variety of messages, which produces different states. All I care about from a development perspective is “which states are important?”
Answer -> One of the main points behind looking at states as sets of sequences of events is precisely to help in undesrtanding which states are important for a particular system. This is explained in the document I link to in this comment.

Peter-> I don’t care what events occurred to transition from state B to state C
Answer -> How can you don't care? Then how do you encode that transition?

Peter-> I may only care about a fraction of the possible states, so modeling a state problem as events feel like a “square peg round hole” problem to me.
Answer -> As mentioned, looking at states as sequences of inputs is a powerful way to decide which states to care for for a given problem at design time (modeling) and which ones does your code care for a given already implemented system in order to compare those which the one which you should be caring (verification). It's defintely not a “square peg round hole” problem but a powerful approach.

Paul -> As I learn more about CEP, I end up with more questions and find scenarios where CEP just isn’t appropriate.
Answer -> Curiously, I happen to experiment the contrary: As I learn more about (C)EP, I end up with more scenarios where CEP just is appropriate.

Paul -> What I would like to see is a more practical approach, which gives the user the option to model a problem as states or events.
Answer -> States and events are the same thing only that they live at different levels of abstraction. AN STATE IS A COMPOSITE EVENT, a set of sequences of events, whether you explicitly model it as composition of input events or you just choose to ignore that cause-effect relationship and just model it with a tuple is up to you and to your problem, but there's no such thing as a design choice between States and Events.

Tim -> Events should be something “more significant” than just changes-of-state.
Answer -> Please, read my linked doc and you will see that i am not saying that events are changes-of-state, in my case, events are inputs. Events are already something "more significant" that just changes-of-state, they are relevant things that happen, what is relevant depends on the problem domain.

Tim -> CEP/EP will experience the same never ending debates on granularity when folks try to answer “what is an event?”
Answer -> Discussing what is an event beyond the generic "something relevant that happens" definiton is pointless. What we have to discuss is techniques for modelling, designing and implementing the processing of those events.

Regards,
PatternStorm

[Tim Bass]

Hi Claudi,

Excellent discussion. My apologies that you could not post your comments over at www.thecepblog.com as you mention here:

http://www.thecepblog.com/2008/07/15/co ... omment-638

I think there might be a restriction on the lenght of a comment, because I cut-and-pasted your comment (to check) and found the same issue.

Yours faithfully, Tim

Ref: http://www.thecepblog.com/2008/07/15/co ... by-states/

[woolfel]

Hi all,

recently there has been some dicussion on the relationship between states and events. Here you can find a short discussion showing that states are (sets) of sequences of events => http://f1.grp.yahoofs.com/v1/gKp9SO87R7 ... 0State.pdf

What follows are answers to objections and comments to my comment to the following blog entry http://www.thecepblog.com/2008/07/15/co ... omment-637 where I stated that states are just composite events.

Tim -> I do think the event-model should not require designers to force all state-transitions to be modelled as events
Answer -> Neither I, the event model must allow modelling state as sequences of events but surely not force it.

Tim -> For example, the level of fuel in a fuel tank can be modelled as event-state changes (as you mentioned), or it can simply be a property that presents the state at a point in time, a tuple.
Answer -> Of course, you can and should do that if you are not interested in tracing how that state changes according to input, however, either you make it explicit or nor in your model, in the end each value of the tuple is representing an equivalence class of sequences of inputs.

Tim-> So, I guess it depends if you are modelling the nodes (the state) or the arrows (the state transition), so to speak.
Answer -> If you look at state from the sequence-of-events point of view transitions and states are not ditinguished anymore: you just have states, each one corresponding to a set of sequences of events, in this case transitions are encoded in the states themselves: let's say you history of events is e1...en and that this sequence belongs to state S1, then you receive event en+1, what is the next state? Just the state that contains the sequence e1...en.en+1. So, there is no such thing as modelling the state or the transitions, everything goes together, but by looking at states as sequences of events you model both using the same basic constructs: composite events.

Paul -> “states are sequences of events”
I’m not sure I agree with that.
Answer -> Please see http://f1.grp.yahoofs.com/v1/gKp9SO87R7 ... 0State.pdf

Paul -> My current state is that I’m sitting here in a hotel room. How is this state = to a sequence of events? It is a *consequence* of a sequence of events, for sure (airplane landed, caught a taxi, slept through alarm call, …).
Answer -> This is not your current state but the state of the universe around you (which includes you) Now that state might turn out to be just the sequence of events that you mention (and lot's more that you don't mention). Of course you can just represent or communicate that state with a sentence "Im sitting here in a hotel room" but the state is "physically" the sequence of events in the universe that took you to that point in space-time so to speak...

Peter -> Not sure I understand the statement “states are sequences of events” as a general purpose definition
Answer -> Not sure I understand what's a "general purpose definition"

Peter -> When I think of states, I think of transactions or finite state machines. A system could receive a variety of messages, which produces different states. All I care about from a development perspective is “which states are important?”
Answer -> One of the main points behind looking at states as sets of sequences of events is precisely to help in undesrtanding which states are important for a particular system. This is explained in the document I link to in this comment.

Peter-> I don’t care what events occurred to transition from state B to state C
Answer -> How can you don't care? Then how do you encode that transition?

Peter-> I may only care about a fraction of the possible states, so modeling a state problem as events feel like a “square peg round hole” problem to me.
Answer -> As mentioned, looking at states as sequences of inputs is a powerful way to decide which states to care for for a given problem at design time (modeling) and which ones does your code care for a given already implemented system in order to compare those which the one which you should be caring (verification). It's defintely not a “square peg round hole” problem but a powerful approach.

Paul -> As I learn more about CEP, I end up with more questions and find scenarios where CEP just isn’t appropriate.
Answer -> Curiously, I happen to experiment the contrary: As I learn more about (C)EP, I end up with more scenarios where CEP just is appropriate.

Paul -> What I would like to see is a more practical approach, which gives the user the option to model a problem as states or events.
Answer -> States and events are the same thing only that they live at different levels of abstraction. AN STATE IS A COMPOSITE EVENT, a set of sequences of events, whether you explicitly model it as composition of input events or you just choose to ignore that cause-effect relationship and just model it with a tuple is up to you and to your problem, but there's no such thing as a design choice between States and Events.

Tim -> Events should be something “more significant” than just changes-of-state.
Answer -> Please, read my linked doc and you will see that i am not saying that events are changes-of-state, in my case, events are inputs. Events are already something "more significant" that just changes-of-state, they are relevant things that happen, what is relevant depends on the problem domain.

Tim -> CEP/EP will experience the same never ending debates on granularity when folks try to answer “what is an event?”
Answer -> Discussing what is an event beyond the generic "something relevant that happens" definiton is pointless. What we have to discuss is techniques for modelling, designing and implementing the processing of those events.

Regards,
PatternStorm

I believe some of the comments attributed to Paul were made by me, just wanted to point that out. Paul shouldn't be blamed for my comments. I couldn't get to the URL, so I can't respond to that. I'll have to read the post a couple of times to make sure I understand it, but it looks like your definition of events is different than the definition I see in product literature. In my mind, events are just messages, which may or may not be "significant". They may or may not indicate a state change depending on the scenario.

When I think of pre-trade compliance and risk management, I want the system to detect when a trade would cause a violation or increase risk. A compliance violation could occur as a result of several unrelated transactions, a transaction set or a single transaction. This is just my experience first hand, so it may not apply to other scenarios. When the user models the problem in this specific case, they're thinking of transactions or positions in a portfolio, fund or account group. When a specific pattern is detected in real-time, the user is notified of the violation or increase in risk. When the user views the violation, they want to see the transactions and/or positions that are involved.

Given the constantly changing state of an active portfolio or fund, I don't care about state transitions that do not cause a violation or increase my risk. Clearly, the scenarios for event detection varies greatly, so a tool should provide the option to model a problem as events or as states. For what I've done in the past, modeling state makes much more sense. A developer or business user can't possibly understand hundreds or thousands events that my occur within a few seconds. What they can do is model the states that result in a violation.

peter

[DLuckham]

Typically, in automata theory anyway, state is a set of values assigned to state variables. A possible representation being a set of <variable,value> pairs. An automaton is a state and a state transition diagram which defines how its state changes as inputs are received. Inputs can be regarded as events.
A sequence of events may affect different automata (or different worlds) differently.
So the view that state IS a sequence of events could be regarded as incomplete. You also need the state transition diagram.

However, "state of mind" is an entirely different matter, although some might argue that that too is an FSM.

- David

[PatternStorm]

So the view that state IS a sequence of events could be regarded as incomplete. You also need the state transition diagram.
- David

Hi David!

I did not forget about the state transition diagram otherwise it would make no sense at all!!

Let me quickly repeat here the reasoning in order for everyone to be able to check if it has any flaw or a particular step requires more clarification:

Code: Select all


Let T be an arbitray transition system.

Let S be the set of possible states of T.
Let I be the set of possible inputs of T.

Let I* denote the set of (finite) sequences of elements of I (i.e. sequences of inputs)

Now let's define the following relation on elements of I* : i1 is related to i2 iff when you run i1 through T, T ends up in the same state that when you run i2 through T.

The relation above is an equivalence relation: it is reflexive, transitive and symmetric, therefore it partitionates I* in equivalence classes.

Each equivalence class is just the set of all sequences of inputs that leave the transition system in the same state.

Clearly each equivalence class corresponds to one and only one state of T and viceversa, therefore, since T is an arbitrary transition system, we can conclude that states of a transition system are just sets of sequences of inputs. QED.


If the reasoning above has no flaws (i.e. it is a demonstration) then it would not be a matter of opinion whether states are sets of sequences of inputs or not. Another thing is whether this has any practical implications or not. Let's try to agree on the former first...

Thank you very much!

Regards,
PatternStorm

[PVincentTIBCO]

Paul -> As I learn more about CEP, I end up with more questions and find scenarios where CEP just isn’t appropriate.
Answer -> Curiously, I happen to experiment the contrary: As I learn more about (C)EP, I end up with more scenarios where CEP just is appropriate.

Paul -> What I would like to see is a more practical approach, which gives the user the option to model a problem as states or events.
Answer -> States and events are the same thing only that they live at different levels of abstraction. AN STATE IS A COMPOSITE EVENT, a set of sequences of events, whether you explicitly model it as composition of input events or you just choose to ignore that cause-effect relationship and just model it with a tuple is up to you and to your problem, but there's no such thing as a design choice between States and Events.

I believe some of the comments attributed to Paul were made by me, just wanted to point that out. Paul shouldn't be blamed for my comments.

Thanks Peter - I certainly don't share the first comment attributed to me, although I agree there are plenty of problems that do not require low-latency, some of these benefit from a event-pattern perspective... conversely I agree with PatternStorm here.

On the 2nd comment: I find I disagree with both - events can be used to drive state transitions, so surely the practical approach is to model states and/or events? And although at an academic level one can claim that states are derived from events (I think this is PatternStorm's thesis: derived can be replaced with represents), this doesn't take account of temporal / time dependencies and changes in prior state transition definitions over time, and that (as the PDF states early on), the set of all states and events (and times) can often be considered infinite (or not modelable, anyway). But its an interesting direction to explore, nonetheless...

Cheers

[hgilde]

If the reasoning above has no flaws (i.e. it is a demonstration) then it would not be a matter of opinion whether states are sets of sequences of inputs or not. Another thing is whether this has any practical implications or not.

T has to be a function (i.e. maps each element in the domain to exactly one element in the range) from I* to S. As I recall from reading on this topic a while ago, depending on how T works, you may need to add the concept of time to make T a function. For example, T might map the same sequence I` in I* to two different elements of S depending on the timing of arrival of each I in I`. This might not be as simple as stating that elements of I are distinct if they occur at different instants in time, because that guarantees that I is uncountable, which may be inconvenient.

Also, your definition of I* may need to add the empty sequence, depending on how you define "all sequences". T(empty sequence) is the initial state of T.

I remember reading some proofs of various facts about a system like this. For example: take two sequences that are equivalent under T. If you can find subsequences on the left of each equivalent sequence that end such that T(subsequence)=T(empty sequence) then you can drop those subsequences from the left of each equivalent sequence and they are still equivalent.

It should be mentioned, though, that there are some practical problems with using sequences to represent state in the computer. The most basic of which is simply that it takes a relatively long time to determine the state from a sequence as opposed to from some variables.

[PatternStorm]

T has to be a function (i.e. maps each element in the domain to exactly one element in the range) from I* to S. As I recall from reading on this topic a while ago, depending on how T works, you may need to add the concept of time to make T a function. For example, T might map the same sequence I` in I* to two different elements of S depending on the timing of arrival of each I in I`. This might not be as simple as stating that elements of I are distinct if they occur at different instants in time, because that guarantees that I is uncountable, which may be inconvenient.

Good point. However I believe my demonstration covers this case also since time ticks are, at the end, a particular input. For example, imagine I am modelling a transition system that processes four different inputs in a time dependent manner, then I can choose I to be I={i1,i2,i3,i4,t} where t is a time tick that happens at the approprriate resolution for my problem. Then the following two sequences:

i1.t.t.t.t.i2.t.t.i3.t.i4
i1.t.i2.t.t.t.t.i3.i4

are different although they are time-dependent variations of the same sequence i1.i2.i3.i4

Therefore, do you Hans agree that the demonstration is also valid for transition systems that take time into account?

Also, your definition of I* may need to add the empty sequence, depending on how you define "all sequences". T(empty sequence) is the initial state of T.

I* does indeed include the empty sequence. The empty sequence belongs to the initial state of T, so yes, T(empty sequence) = initial state of T.

I remember reading some proofs of various facts about a system like this.

Please, would you be able to provide pointers to those readings? My demonstration must be a known result but couldn't find any literature...

For example: take two sequences that are equivalent under T. If you can find subsequences on the left of each equivalent sequence that end such that T(subsequence)=T(empty sequence) then you can drop those subsequences from the left of each equivalent sequence and they are still equivalent.

That's correct. All the sequences belonging to (the equivalence class of) the initial state can be dropped when they appear as left prefixes in other sequences. Moreover, every input sequence can be represented by the state it belongs to, so you can tanslate from sequences of inputs to sequences of states...Interesting corollaries...These must be well-known results...Anyone has pointers?

It should be mentioned, though, that there are some practical problems with using sequences to represent state in the computer. The most basic of which is simply that it takes a relatively long time to determine the state from a sequence as opposed to from some variables.

Let's keep the pragmatic part of the discussion for a second in order to focus on the first part: is everybody ok with my reasoning that shows that states are sets of sequences of events? If not, please shout!

[PatternStorm]

I believe some of the comments attributed to Paul were made by me

Sorry for that!

Given the constantly changing state of an active portfolio or fund, I don't care about state transitions that do not cause a violation or increase my risk

So, for your problem, these are not state transitions, that is, they belong to the same equivalence class. In fact you are using the words "state transitions" when you should be using the words "sequences of input elements"!!!!, i.e. you should be saying I don't care about sequence of input elements that do not cause a violation or increase my risk (that is, that do not cause a transition for my problem)

Every (interactive) component solving a particular problem needs to deal with a specific set of different input elements, these input elements arrive at the component one after the other, the component changes state as the input elements arrive, at any point in time the component is in a particular state and has processed a particular sequence of input elements...There surely exist several other sequences of inputs that will leave your component in the same state...Let's group all those sequences together in a set, well, then that state of your component is in fact a particular convenient (implementation-dependant) representation, for the problem you are solving, of that set of sequences of inputs...Aren't you interested in knowing how your component's implementation is partitioning the space of possible sequences of inputs into states? Are you confident enough this partitioning is correct? One way to help in that is: instead of (or in addition to) jumping into state machine modeling or implementation right ahead just try to characterize/specify your problem by grouping sequences of inputs into equivalent classes...you may want to use event expression patterns to help you in that task...

After all, what is Event Processing essentially about? I would say about expressing (as declarative as possible) situations(=states=composite events) to which we want to react. What does an interactive component essentially do? React to situations occurring in its history of received inputs. Then, why I would not be able to use Event Processing techniques to declaratively implement interactive components?

What they can do is model the states that result in a violation.

How do they do that? Can you illustrate, for instance providing a simplified/toy example that nevertheless captures the essence of the problem?

Thanks!

Regards,
PatternStorm

[woolfel]

I believe some of the comments attributed to Paul were made by me

Sorry for that!

Given the constantly changing state of an active portfolio or fund, I don't care about state transitions that do not cause a violation or increase my risk

So, for your problem, these are not state transitions, that is, they belong to the same equivalence class. In fact you are using the words "state transitions" when you should be using the words "sequences of input elements"!!!!, i.e. you should be saying I don't care about sequence of input elements that do not cause a violation or increase my risk (that is, that do not cause a transition for my problem)

Every (interactive) component solving a particular problem needs to deal with a specific set of different input elements, these input elements arrive at the component one after the other, the component changes state as the input elements arrive, at any point in time the component is in a particular state and has processed a particular sequence of input elements...There surely exist several other sequences of inputs that will leave your component in the same state...Let's group all those sequences together in a set, well, then that state of your component is in fact a particular convenient (implementation-dependant) representation, for the problem you are solving, of that set of sequences of inputs...Aren't you interested in knowing how your component's implementation is partitioning the space of possible sequences of inputs into states? Are you confident enough this partitioning is correct? One way to help in that is: instead of (or in addition to) jumping into state machine modeling or implementation right ahead just try to characterize/specify your problem by grouping sequences of inputs into equivalent classes...you may want to use event expression patterns to help you in that task...

After all, what is Event Processing essentially about? I would say about expressing (as declarative as possible) situations(=states=composite events) to which we want to react. What does an interactive component essentially do? React to situations occurring in its history of received inputs. Then, why I would not be able to use Event Processing techniques to declaratively implement interactive components?

What they can do is model the states that result in a violation.

How do they do that? Can you illustrate, for instance providing a simplified/toy example that nevertheless captures the essence of the problem?

Thanks!

Regards,
PatternStorm

Actually, the "state" of the portfolio is changing. By that I mean real transactions are executing and the value of the portfolio is changing, so it's not just a sequence of inputs. I get the feeling my definition is quite different than yours. I'll do my best to give an example. Within compliance, there's a wide variety of rules. They range from simple restriction rule, which prohibit the trade of a given security, to diversifiction and risk rules. Here's some examples.

Restrict the purchase of ticker MSFT for account 11, 300, 431, 13
The minimum cash balance for account 300 is 20,000.00
The maximum cash balance for account 13 is 5,000.00

Diversification rules
For account 13, the weight of industry oil & gas, and rating of AA cannot exceed 20% of the total portfolio value
For account 300, the weight of the top 5 securities in sector industrial cannot exceed 10%

Risk rules
If the current price for the stock is less than 3 x the maximum delta for the last month (current price < (closing price - (3 x max delta) ) ), send an alert to the fund manager

the rules can get a lot more compilcated than this, but it should give a decent idea. Given stock prices move up and down, and the number of bid/ask/buy/sell flowing through the various trading systems is huge, it's practically impossible to think of it in terms of events or inputs. A rule could get triggered by any number of events and a violation could automatically resolve itself without human intervention. Let me give you an example of this.

Say portfolio A has 50 positions (aka stocks). There's 10 pending transactions and 5 new transactions. Say we're currently at 9.5% weight for account 300. We have a pending sell and a new buy for sector industrial.

T0 is the start of the day and the portfolio has no violations and is properly balanced
T1 sell order is sent and is pending
T2 a new buy order is executed, making the weight for sector industrial 11.2% - this triggers a compliance violation and sends a message to the portfolio manager
T3 the pending sell order goes through and the weight drops down to 9.8% - the system send a message to the portfolio manager saying the sector is no longer in violation

In practice, the number of transactions that may impact compliance varies from day to day. Understanding the sequence of events that could lead to a violation isn't practical, since it's an unbounded problem. Attempting to categorize or understanding the possible combination of events that could lead to violation is a waste of time. In the example above, if the sell order executes first, the system wouldn't generate a compliance violation message.

For this particular case, I feel modeling it as state is more appropriate. If a business user or developer were to try modeling the events first, they would get overwhelmed. This is from first hand experience building a real pre-trade compliance engine for an order managemetn system. I'm sure there are plenty of cases where modeling as event makes more sense.

peter