Non-centralized data synchronization for IoT and other distributed applications
Disclosed is a method, apparatus, and system for processing a data update message in a multi-agent system comprising a plurality of agents, the operations comprising: receiving, at a second agent, the data update message comprising data for a node in a shared data tree and a first node context map from a first agent, the first node context map comprising last known contexts of all the agents for the node according to knowledge of the first agent; determining, at the second agent, whether any of three conditions relating to the first node context map and a second node context map is true, the second node context map comprising last known contexts of all the agents for the node according to knowledge of the second agent; and in response to determining that none of the three conditions relating to the first node context map and the second node context map is true, updating, at the second agent, the node based on the data update message from the first agent.
1. A computer-implemented method for processing a data update message in a decentralized multi-agent system comprising a plurality of agents, the method comprising:
receiving, at a second agent of the plurality of agents, the data update message comprising data for a node in a shared data tree comprising a plurality of nodes and a first node context map from a first agent of the plurality of agents, the first node context map comprising last known contexts of all the agents for the node according to knowledge of the first agent, each of the plurality of agents maintaining a separate copy of the shared data tree, and the data update message being sent in response to a change in a copy of the node in the shared data tree maintained by the first agent that desynchronizes the first agent from the second agent;
determining, at the second agent, whether any of three conditions relating to the first node context map and a second node context map is true, the second node context map comprising last known contexts of all the agents for the node according to knowledge of the second agent; and
in response to determining that none of the three conditions relating to the first node context map and the second node context map is true, updating, at the second agent, the node based on the data update message from the first agent, wherein each agent of the plurality of agents maintains its respective copy of the shared data tree and a respective full context map comprising last known contexts of all of the plurality of agents including itself for each of the plurality of nodes of the shared data tree according to knowledge of the agent, wherein each agent's own context is a maximal context in the respective full context map, and wherein each agent's own context is larger than or equal to other agent's last known context of the agent.
2. The method of claim 1 , wherein the three conditions comprise: 1) the last known node context of the second agent according to knowledge of the first agent is equal to the last known node context of the first agent according to knowledge of the first agent; 2) the last known node context of the first agent according to knowledge of the first agent is equal to the last known node context of the first agent according to knowledge of the second agent; and 3) there exists a third agent such that the last known node context of the first agent according to knowledge of the first agent is equal to the last known node context of the third agent according to knowledge of the first agent, and the last known node context of the third agent according to knowledge of the second agent is higher than or equal to the last known node context of the first agent according to knowledge of the first agent.
3. The method of claim 1 , further comprising in response to determining that at least one of the three conditions relating to the first node context map and the second node context map is true, not updating, at the second agent, the node based on the data update message from the first agent.
4. The method of claim 1 , wherein each respective copy of the shared data tree maintained be each respective agent is the same except immediately after one of the respective agents changes its respective copy of the shared data tree immediately triggering a synchronization across each respective agent.
5. The method of claim 1 , further comprising:
changing, by the second agent, data for a second node in a copy of the shared data tree maintained by the second agent at the same time that the change in the copy of the node in the shared data tree maintained by the first agent occurs; and
in response to changing the data, sending a second data update message that conflicts with the data update message.
6. The method of claim 1 , wherein the multi-agent system comprises at least three agents.
7. The method of claim 6 , wherein the agents of the multi-agent system play equal roles.
8. A non-transitory machine-readable medium having instructions stored therein, which when executed by a processor, cause the processor to perform synchronization operations in a decentralized multi-agent system comprising a plurality of agents, the operations comprising:
receiving, at a second agent of the plurality of agents, a data update message comprising data for a node in a shared data tree comprising a plurality of nodes and a first node context map from a first agent of the plurality of agents, the first node context map comprising last known contexts of all the agents for the node according to knowledge of the first agent, each of the plurality of agents maintaining a separate copy of the shared data tree, and the data update message being sent in response to a change in a copy of the node in the shared data tree maintained by the first agent that desynchronizes the first agent from the second agent;
determining, at the second agent, whether any of three conditions relating to the first node context map and a second node context map is true, the second node context map comprising last known contexts of all the agents for the node according to knowledge of the second agent; and
in response to determining that none of the three conditions relating to the first node context map and the second node context map is true, updating, at the second agent, the node based on the data update message from the first agent,
wherein each agent of the plurality of agents maintains its respective copy of the shared data tree and a respective full context map comprising last known contexts of all of the plurality of agents including itself for each of the plurality of nodes of the shared data tree according to knowledge of the agent, wherein each agent's own context is a maximal context in the respective full context map, and wherein each agent's own context is larger than or equal to other agent's last known context of the agent.
9. The non-transitory machine-readable medium of claim 8 , wherein the three conditions comprise: 1) the last known node context of the second agent according to knowledge of the first agent is equal to the last known node context of the first agent according to knowledge of the first agent; 2) the last known node context of the first agent according to knowledge of the first agent is equal to the last known node context of the first agent according to knowledge of the second agent; and 3) there exists a third agent such that the last known node context of the first agent according to knowledge of the first agent is equal to the last known node context of the third agent according to knowledge of the first agent, and the last known node context of the third agent according to knowledge of the second agent is higher than or equal to the last known node context of the first agent according to knowledge of the first agent.
10. The non-transitory machine-readable medium of claim 8 , the operations further comprising in response to determining that at least one of the three conditions relating to the first node context map and the second node context map is true, not updating, at the second agent, the node based on the data update message from the first agent.
11. The non-transitory machine-readable medium of claim 8 , wherein each respective copy of the shared data tree maintained be each respective agent is the same except immediately after one of the respective agents changes its respective copy of the shared data tree immediately triggering a synchronization across each respective agent.
12. The non-transitory machine-readable medium of claim 8 , further comprising:
changing, by the second agent, data for a second node in a copy of the shared data tree maintained by the second agent at the same time that the change in the copy of the node in the shared data tree maintained by the first agent occurs; and
in response to changing the data, sending a second data update message that conflicts with the data update message.
13. The non-transitory machine-readable medium of claim 8 , wherein the multi-agent system comprises at least three agents.
14. The non-transitory machine-readable medium of claim 13 , wherein the agents of the multi-agent system play equal roles.
15. A data processing system for processing a data update message in a decentralized multi-agent system comprising a plurality of agents, comprising:
a processor; and
a memory coupled to the processor to store instructions, which when executed by the processor, cause the processor to perform synchronization operations in a multi-agent system comprising a plurality of agents, the operations including:
receiving, at a second agent of the plurality of agents, a data update message comprising data for a node in a shared data tree comprising a plurality of nodes and a first node context map from a first agent of the plurality of agents, the first node context map comprising last known contexts of all the agents for the node according to knowledge of the first agent, each of the plurality of agents maintaining a separate copy of the shared data tree, and the data update message being sent in response to a change in a copy of the node in the shared data tree maintained by the first agent that desynchronizes the first agent from the second agent;
determining, at the second agent, whether any of three conditions relating to the first node context map and a second node context map is true, the second node context map comprising last known contexts of all the agents for the node according to knowledge of the second agent; and
in response to determining that none of the three conditions relating to the first node context map and the second node context map is true, updating, at the second agent, the node based on the data update message from the first agent,
wherein each agent of the plurality of agents maintains its respective copy of the shared data tree and a respective full context map comprising last known contexts of all of the plurality of agents including itself for each of the plurality of nodes of the shared data tree according to knowledge of the agent, wherein each agent's own context is a maximal context in the respective full context map, and wherein each agent's own context is larger than or equal to other agent's last known context of the agent.
16. The data processing system of claim 15 , wherein the three conditions comprise: 1) the last known node context of the second agent according to knowledge of the first agent is equal to the last known node context of the first agent according to knowledge of the first agent; 2) the last known node context of the first agent according to knowledge of the first agent is equal to the last known node context of the first agent according to knowledge of the second agent; and 3) there exists a third agent such that the last known node context of the first agent according to knowledge of the first agent is equal to the last known node context of the third agent according to knowledge of the first agent, and the last known node context of the third agent according to knowledge of the second agent is higher than or equal to the last known node context of the first agent according to knowledge of the first agent.
17. The data processing system of claim 15 , further comprising in response to determining that at least one of the three conditions relating to the first node context map and the second node context map is true, not updating, at the second agent, the node based on the data update message from the first agent.
18. The data processing system of claim 15 , wherein each respective copy of the shared data tree maintained be each respective agent is the same except immediately after one of the respective agents changes its respective copy of the shared data tree immediately triggering a synchronization across each respective agent.
19. The data processing system of claim 15 , further comprising:
changing, by the second agent, data for a second node in a copy of the shared data tree maintained by the second agent at the same time that the change in the copy of the node in the shared data tree maintained by the first agent occurs; and
in response to changing the data, sending a second data update message that conflicts with the data update message.
20. The data processing system of claim 15 , wherein the multi-agent system comprises at least three agents.
21. The data processing system of claim 20 , wherein the agents of the multi-agent system play equal roles.