Analysis of temporal consistency management protocols for resource-constrained multi-agent systems
Article Sidebar
Main Article Content
Abstract
Multi-Agent Systems (MAS) are distributed system composed of a set of connected nodes, that communicate and share data. Since nodes do not have access to a central clock, the consistency of shared data is one of the important issues raised by this type of system. Approaches to establish temporal consistency of these shared data have been designed and implemented in the past. This paper presents and analyses existing protocols for managing temporal consistency in order to identify those that are in line with the specificities of weakly adjoining MAS with limited resources and connectivity. We propose a classification and a comparative analysis of these protocols for use within this category of MAS.
Article Details
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
References
Chaib-Draa B. Industrial applications of distributed AI. Commun ACM. 1995;38(1):49-53.
van Steen M, Tanenbaum AS. Distributed systems. 3rd ed. London: Pearson Education; 2017.
Martin B, Kjell H, Ann‐Marie L, Marianne C. Sense of coherence: definition and explanation. Int J Soc Welfare. 2006;15(3): 219-29.
Strumpfer D, Gouws J, Viviers M. Antonovsky's Sense of coherence scale related to negative and positive affectivity. Eur J Pers.1998;12(6):457-80.
Grosz B, Sidner C. Attention, intentions, and the structure of discourse. Comput Ling. 1986;12(3):175-204.
Carbaugh D, Craig RT, Tracy K. Conversational coherence: form, structure, and strategy. Lang Soc. 1989;18(1):103-9.
Thagard P. Coherence in thought and action. Cambridge: MIT press; 2000.
Thagard P. Hot thought: mechanisms and applications of emotional cognition. Cambridge: MIT press; 2008.
Grottke S, Sablatnig J, Chen J, Seiler R, Wolisz A. Consistency in distributed systems. Berlin: Technische Universitat Berlin; 2007.
Vu QN, Gaudou B, Canal R, Hassas S. Coherence and robustness in a disturbed MAS. IEEE-RIVF International Conference on Computing and Communication Technologies; 2009 Jul 13-17; Danang, Vietnam. New York: IEEE; 2009. p. 1-4.
Thomesse JP. The fieldbuses. IFAC Proc Volume. 1997;30(7):13-23.
Cauffriez L, Defrenne J. An experimental platform for the reliability-availability evaluation of intelligent distributed systems. IFAC Proc Volume. 1997;30(7):545-50.
Ferber J. Multi-agent systems: an introduction to distributed artificial intelligence. Boston: Addison-Wesley; 1999.
Lang J. Logical preference representation and combinatorial vote. Ann Math Artif Intell. 2004;42:37-71.
Bussmann S, Muller J. A negotiation framework for co-operating agents. Proceeding of CKBS-SIG; 1992 Sep 23-25; Dake Center, University of Keele. Newcastle: University of Keele; 1992. p. 1-17.
Minar N. A survey of the NTP network [Internet]. 1999 [cited 2021 Mar 10]. Available from: http://www.media.mit.edu/~nelson/research/ntp-survey99/.
Cristian F. Probabilistic clock synchronization. Distr Comput. 1989;3:146-58.
Gusella R, Zatti S. The accuracy of the clock synchronization achieved by TEMPO in Berkeley UNIX 4.3 BSD. IEEE Trans Software Eng. 1989;15(7):847-53.
Lamport L. Time, clocks, and the ordering of events in a distributed system. In: Malkhi D, editor. Concurrency: the works of Leslie Lamport. New York: Association for Computing Machinery; 2019. p. 179-96.
Mattern F. Virtual time and global states of distributed systems. Proceedings of the International Workshop on Parallel and Distributed Algorithms; 1988 Oct 3-6; Chateau de Bonas, France. Amsterdam: North-Holland; 1989. p. 215-66.
Fidge CJ. Timestamps in message-passing systems that preserve the partial ordering. Aust Comput Sci Commun. 1988;10(1):55-6.
Schwarz R, Mattern F. Detecting causal relationships in distributed computations: in search of the Holy Grail. Distr Comput. 1994;7:149-74.
Raynal M, Singhal M. Logical time: capturing causality in distributed systems. Comput. 1996;29(2):49-56.
Elson J, Girod L, Estrin D. Fine-grained network time synchronization using reference broadcasts. ACM SIGOPS Oper Syst Rev. 2002;36:147-63.
Ganeriwal S, Kumar R, Srivastava MS. Timing-sync protocol for sensor networks. Proceedings of the 1st International Conference on Embedded Networked Sensor Systems; 2003 Nov 5-7; Los Angeles, USA. New York: Association for Computing Machinery; 2003. p. 138-49.
Maroti M, Kusy B, Simon G, Ledeczi A. The flooding time synchronization protocol. Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems; 2004 Nov 3-5; Baltimore, USA. New York: Association for Computing Machinery; 2004. p. 39-49.
Ping S. Delay measurement time synchronization for wireless sensor networks. IRB-TR-03-013: Intel Research Berkeley Lab. Berkley, USA; 2003.
Maggs MK, O'Keefe SG, Thiel DV. Consensus clock synchronization for wireless sensor networks. IEEE Sensor J. 2012;12(6):2269-77.
Schenato L, Fiorentin F. Average TimeSynch: a consensus-based protocol for clock synchronization in wireless sensor networks. Automatica. 2011;47(9):1878-86.
Sommer P, Wattenhofer R. Gradient clock synchronization in wireless sensor networks. International Conference on Information Processing in Sensor Networks; 2009 Apr 13-16; San Francisco, USA. New York: IEEE; 2009. p. 37-48.
Ramirez-Avila GM, Kurths J, Depickere S, Deneubourg JL. Modeling fireflies synchronization. In: Macau EEN, editor. A mathematical modeling approach from nonlinear dynamics to complex systems. Berlin: Springer; 2019. p. 131-56.
Limame M, Henriet J, Lang C. Synchronisation d’horloge dans un systeme multi-agents. France: APIA; 2019. (In France)
Garcia E, Guyennet H, Henriet J. Towards an optimistic management of concurrency: a probabilistic study of the pilgrim protocol. International Conference on Computer Supported Cooperative Work in Design; 2005 May 24; Coventry, UK. Berlin: Springer; 2005. p. 51-60.
Brzezinski J, Sobaniec C, Wawrzyniak D. From session causality to causal consistency. 12th Euromicro Conference on Parallel, Distributed and Network-Based Processing; 2004 Feb 11-13; Coruna, Spain. New York: IEEE; 2004. p. 152-8.
Raynal M, Schiper A. A suite of formal definitions for consistency criteria in distributed shared memories. Proceedings International Conference on Parallel and Distributed Computing (PDCS'96); 1996 Sep 25-27; Dijon, France. Lausanne: Infoscience; 1996. p. 125-30.