Skip to content

Changes

Page history
example communications, further steps authored by myeisha's avatar myeisha
Show whitespace changes
Inline Side-by-side
Reliable-state-machines-(concept).md
View page @ e17ec18c
...@@ -124,3 +124,126 @@ Note that the sending state machine specifies a recovery procedure. In the simpl ...@@ -124,3 +124,126 @@ Note that the sending state machine specifies a recovery procedure. In the simpl
#### Protocol state machine on the master #### Protocol state machine on the master
On the master, the same state machines run in parallel for each device known to the state machine. Since the master will often send packets via multicast and, for a given packet, all state machine timeouts that do expire will expire at the same time, the master may send a multicast packet only once instead of once for each known destination. Additionally, when the master receives a reset command for the distributed state machine, all send/receive state machines are reset, all queues are cleared and reinitialized with the reset command packet for the distributed state machine. On the master, the same state machines run in parallel for each device known to the state machine. Since the master will often send packets via multicast and, for a given packet, all state machine timeouts that do expire will expire at the same time, the master may send a multicast packet only once instead of once for each known destination. Additionally, when the master receives a reset command for the distributed state machine, all send/receive state machines are reset, all queues are cleared and reinitialized with the reset command packet for the distributed state machine.
#### Example communications
Assume a system with a master `M`, a sensor `S` and two actors, `A` and `B`. The full specification of the distributed state machine running on the devices is not important for the discussion of the reliability mechanism, we need only know that `S` may send `INFO` packets for an endpoint `e` that may trigger changes in the actors.
In the following diagrams, packets will be denoted as `type (seq#, rest)`. Hence, `INFO` packets will be `INFO (seq#, <endpoint>)`, `ACK` packets will be `ACK(seq#, cause#)` and `PINFO` packets will be `PINFO(seq#, senderIP, <endpoint>)`.
The simplest case of course does not experience packet loss:
```
M S A B
| INFO(1, e) | | |
|<------------------------|------------------------>|------------------------>| (A, B ignore INFO)
| ACK(42, 1) | | |
|------------------------>| | |
| PINFO(43, S, e) | | |
|------------------------>|------------------------>|------------------------>| (A, B act)
| | ACK(43) | |
|<------------------------+-------------------------| |
| | | ACK(43) |
|<------------------------+-------------------------+-------------------------|
| | | |
```
If packet loss on the path from `S` to `M` occurs, `S` will retransmit the packet packet until an `ACK` is received or `S` must assume failure. If the `INFO` packet is lost, a possible communication will look much like this:
```
M S A B
| INFO(1, e) | | |
|<--//////////------------|------------------------>|------------------------>| (A, B ignore INFO)
| | | |
Z (timeout occurs) Z Z Z
| | | |
| INFO(1, e) | | |
|<------------------------|------------------------>|------------------------>| (A, B ignore INFO)
| ACK(42, 1) | | |
|------------------------>| | |
| PINFO(43, S, e) | | |
|------------------------>|------------------------>|------------------------>| (A, B act)
| | ACK(43) | |
|<------------------------+-------------------------| |
| | | ACK(43) |
|<------------------------+-------------------------+-------------------------|
| | | |
```
A lost `ACK` packet from the master to sensor `S` will behave much the same: when the master detects a retransmittd `INFO` packet, it will send another `ACK`, but no new `PINFO` packets:
```
M S A B
| INFO(1, e) | | |
|<------------------------|------------------------>|------------------------>| (A, B ignore INFO)
| ACK(42, 1) | | |
|---//////////----------->| | |
| PINFO(43, S, e) | | |
|------------------------>|------------------------>|------------------------>| (A, B act)
| | ACK(43) | |
|<------------------------+-------------------------| |
| | | ACK(43) |
|<------------------------+-------------------------+-------------------------|
| | | |
Z (timeout occurs) Z Z Z
| | | |
| INFO(1, e) | | |
|<------------------------|------------------------>|------------------------>| (A, B ignore INFO)
| ACK(42, 1) | | |
|------------------------>| | |
| | | |
```
Now let a `PINFO` packet be lost on its ways to `B`, and let the sensor `S` send another value before `B` has acknowledges reception of the first packet:
```
M S A B
| INFO(1, e1) | | |
|<------------------------|------------------------>|------------------------>| (A, B ignore INFO)
| ACK(42, 1) | | |
|------------------------>| | |
| PINFO(43, S, e1) | | |
|------------------------>|------------------------>|-----/////////---------->| (A acts, PINFO to B lost)
| | ACK(43) | |
|<------------------------+-------------------------| |
| | | |
| INFO(2, e2) | | |
|<------------------------|------------------------>|------------------------>| (A, B ignore INFO)
| | | |
Z (timeout occurs) Z Z Z
| | | |
| PINFO(43, S, e1) | | |
|------------------------>|------------------------>|------------------------>| (B acts, A detects retransmission)
| | ACK(43) | |
|<------------------------+-------------------------| |
| | | ACK(43) |
|<------------------------+-------------------------+-------------------------|
| | | |
| PINFO(44, S, e2) | | |
|------------------------>|------------------------>|------------------------>| (A, B act)
| | ACK(44) | |
|<------------------------+-------------------------| |
| | | ACK(44) |
|<------------------------+-------------------------+-------------------------|
| | | |
```
## Step n+1: but wait, there's more!
Additionally to the basic reliability mechanism, a number of advanced features that require the reliability mechanism should be implemented.
### Device groups for the state machine
Instead of repeating the IP address of the originating device in `PINFO` packets, assign to each device one or more unique group IDs. When generating `PINFO` packets from `INFO` packets, the master will generate one `PINFO` packet for each group ID assigned to the originating device. All of these `PINFO` packets must then be sent reliably to the devices in the system.
### Allow independent packets to be sent concurrently
Since the master can know the entire state machine and the current state of every device, the master can determine when it is safe to send more than one packet with strong reliability requirements. For example, two completely indepent instances of the state machine "staircase light" might be running in one installation. The master will then know that two packets can be sent concurrently if one is only valid for the first staircase light, and the second is only valid for the other. We need not introduce artificial delays by totally ordering these two packets when partially ordering them based on which state machines they affect is sufficient.
### Smart recovery mechanism
The recovery mechanism as implemented the current hexabus system (as of 18. Nov. 2013) and as sketched in Step 1 is very brutal. Instead, let the master silently execute the state machine of the entire system and, whenenver a falure is detected and subsequently fixed, recover the failed device. Since the master knows in which state the failed device should be and knows the values of each endpoint modified by the state machine, the master can then `WRITE` the values to the device and tell it to restart its state machine at the state it should be in.
### Upgrade path for the master process
Allow the master process to be updated without losing state or packets. This will require some form of saving the current state of the master process, executing the new binary and reading the state of the old instance without dropping packets. systemd can do it, we should be able to do that too.
### Failsafe master
If the master crashes, the distributed state machine should not be required to reset in its entirety. This is closely related to the previous item: if the master were to save it's state to some location that can outlive the master process itself, a new copy of the process can restart where the old left off with minimal interruption.