Exactly what is a state?
The future behavior of a system, given its state, is independent of the past behavior of the system. A system may enter the same state by executing different behaviors, but the future behavior of a system, given its state, doesn't depend on what happened before the state was entered.See the definition of state in our model. See a comprehensive description of states in computer systems.
When do state transitions occur?
In our model, the state of a system changes when, and only when, a message is delivered to an agent.What is an event?
Don't agents change states continuously?
Yes, agent states may change continuously. The complete state of an agent includes its program counter which points to the next statement to be executed by the agent. Our model ignores continuous changes in state of an agent while it is executing areceive and restricts
attention to the state of an agent when it is waiting.
In our model, an agent is waiting for a message or processing a
message that it received.
We only deal with the state of the agent after it has finished
processing the message and is back in the waiting state.
The changes that occur while a receive is being
executed are ignored by the model.
What happens if an agent goes to sleep
during a receive?
def receive(message, sender):
send ("hello", receiver_1)
time.sleep(1000)
send ("world", receiver_2)
The agent sends a message "hello" to receiver_1 then sleeps for
1000 seconds and then sends a message to receiver_2.
We may expect enough time to elapse between the messages to allow
receiver_1 to send a message to receiver_2
before the "world" message gets to receiver_2.
Our model does not deal with time.
It treats the execution of the receive as an atomic
operation.
The effect of the following receive with the
sleep removed is the same as the previous
receive.
def receive(message, sender):
send ("hello", receiver_1)
send ("world", receiver_2)
Time is important in the behavior of distributed systems.
We don't use time in reasoning about the correctness of distributed
systems because it's safer not to depend on clock accuracy.
Can two agents receive messages at exactly the same time? Won't that result in a state transition in which two agents change state?
If two agents receive messages at exactly the same time then the events at which the messages are received are independent and so they can be executed in arbitrary order.Suppose agent \(v\) receives a message \(m\) from agent \(u\) at exactly the same time that \(u\) receives a message \(m'\) from \(v\). Then before the steps, the channel from \(v\) to \(u\) contained message \(m\) and the channel from \(u\) to \(v\) contained message \(m'\).
If \(u\) receives \(m'\) first it makes no difference to \(m\) being at the head of the channel from \(v\) to \(u\). So, the order in which the steps occur is irrelevant.
Many agents are changing state and sending and receiving messages concurrently. We ignore these concurrent changes and restrict attention state changes in which one agent receives one message. We can analyze systems with concurrent changes using our simple model.
Can an agent receive multiple messages in a single state transition? Can an agent send multiple messages to another agent in a single state transition?
Our model only allows one message to be received in a state transition and one message to be sent to an agent in the transition.Extending the model to allow a sequence of messages to be sent to an agent in a single transition isn't necessary for the algorithms that we discuss; however, extending the model to do so is straightforward and you should try to do so.
The model does not fully capture reality. A model is an engineering choice. It is an abstraction of reality that helps us develop algorithms.
K. Mani Chandy, Emeritus Simon Ramo Professor, California Institute of Technology