Synchronization protocols for reliable communication in fully distributed agent systems

ABSTRACT

In order to prevent misunderstandings within groups of interacting agents, it is necessary to ensure that the agents' beliefs regarding the overall state of the interaction are consistent with each other at all times. In [7], Paurobally et al. proposed that these beliefs could be synchronized by adding a specialized protocol layer that incorporates protocols specifically designed to synchronize the agents' beliefs. Here we define the problem that such protocols would need to solve in the worst case, and prove it to be insoluble. We then consider the possibility of synchronizing the beliefs of groups of agents if it is assumed that the communication layer notifies the sender of a message whenever that message is not successfully delivered. Paurobally et al. proved that this assumption allows agents' beliefs to be synchronized in bilateral interactions. However, we prove that this assumption is insufficient to achieve belief synchronization in groups of three or more agents. Finally, we discuss the possibility of achieving adequate synchronization using probabilistic protocols.

REFERENCES

• 1: E. A. Akkoyunlu , K. Ekanadham , R. V. Huber, Some constraints and tradeoffs in the design of network communications, Proceedings of the fifth ACM symposium on Operating systems principles, p.67-74, November 19-21, 1975, Austin, Texas, United States
• 2: Gildas Avoine , Serge Vaudenay, How to safely close a discussion, Information Processing Letters, v.102 n.4, p.138-142, May, 2007 [doi>10.1016/j.ipl.2006.12.001]
• 3: Ronald Fagin , Joseph Y. Halpern , Moshe Y. Vardi , Yoram Moses, Reasoning about knowledge, MIT Press, Cambridge, MA, 1995
• 4: Jim Gray, Notes on Data Base Operating Systems, Operating Systems, An Advanced Course, p.393-481, January 1978
• 5: M. Huget (Ed.): Communication in Multiagent Systems, Agent Communication Languages and Conversation Policies. LNCS 2650, 2003.
• 6: Ram Meshulam , Ariel Felner , Sarit Kraus, Utility-based multi-agent system for performing repeated navigation tasks, Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, July 25-29, 2005, The Netherlands [doi>10.1145/1082473.1082608]
• 7: Shamimabi Paurobally , Jim Cunningham , Nicholas R. Jennings, Ensuring consistency in the joint beliefs of interacting agents, Proceedings of the second international joint conference on Autonomous agents and multiagent systems, July 14-18, 2003, Melbourne, Australia [doi>10.1145/860575.860682]
• 8: S. Paurobally. Rational Agents and the Processes and States of Negotiation. PhD Thesis, Imperial College, 2002.
• 9: Onn Shehory , Katia Sycara , Gita Sukthankar , Vick Mukherjee, Agent aided aircraft maintenance, Proceedings of the third annual conference on Autonomous Agents, p.306-312, April 1999, Seattle, Washington, United States [doi>10.1145/301136.301216]
• 10: George Varghese , Nancy A. Lynch, A tradeoff between safety and liveness for randomized coordinated attack, Information and Computation, v.128 n.1, p.57-71, July 10, 1996 [doi>10.1006/inco.1996.0063]
• 11: Bin Yu , Paul Scerri , Katia Sycara , Yang Xu , Michael Lewis, Scalable and reliable data delivery in mobile ad hoc sensor networks, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan [doi>10.1145/1160633.1160825]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence

General Terms:
Languages, Reliability, Verification

Keywords:
agent, broadcasting, protocol, synchronization