1. Analyzing the exhaustiveness of the synapse protocol
- Author
-
Vincenzo Ciancaglini, Zoran Ognjanović, Bojan Marinković, Paola Glavan, Luigi Liquori, Petar Maksimovic, Mathematical Institute of the Serbian Academy of Sciences and Arts, Serbian Academy of Sciences and Arts (SASA), Logical Networks: Self-organizing Overlay Networks and Programmable Overlay Computing Systems (LOGNET), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), University of Zagreb, and The work presented in this paper was supported by the Serbian Ministry of Education, Science and Technological Development, projects ON174026 and III44006, through Matematicki Institut SANU and by Ministarstvo znanosti, obrazovanja i sporta republike Hrvatske.
- Subjects
Theoretical computer science ,Computer Networks and Communications ,Computer science ,Distributed computing ,Overlay network ,0102 computer and information sciences ,02 engineering and technology ,Peer-to-peer ,computer.software_genre ,01 natural sciences ,[INFO.INFO-SI]Computer Science [cs]/Social and Information Networks [cs.SI] ,Synapse ,ACM: F.: Theory of Computation/F.3: LOGICS AND MEANINGS OF PROGRAMS ,[INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI] ,0202 electrical engineering, electronic engineering, information engineering ,Abstract State Machines ,Protocol (object-oriented programming) ,Computer communication networks ,Retrieval probability ,Formal description ,Quantitative Biology::Neurons and Cognition ,DASM, Peer-to-Peer Protocols ,ACM: F.: Theory of Computation/F.3: LOGICS AND MEANINGS OF PROGRAMS/F.3.1: Specifying and Verifying and Reasoning about Programs ,ACM: C.: Computer Systems Organization/C.2: COMPUTER-COMMUNICATION NETWORKS ,[MATH.MATH-LO]Mathematics [math]/Logic [math.LO] ,DHT-based overlay networks ,010201 computation theory & mathematics ,ACM: C.: Computer Systems Organization/C.2: COMPUTER-COMMUNICATION NETWORKS/C.2.2: Network Protocols ,Scalability ,Abstract state machines ,020201 artificial intelligence & image processing ,computer ,Software - Abstract
International audience; The Synapse protocol is a scalable protocol designed for information retrieval over inter-connected heterogeneous overlay networks. In this paper, we give a formal description of Synapse using the Abstract State Machines framework. The formal description pertains to Synapse actions that manipulate distributed keys. Based on this formal description, we present results concerning the expected exhaustiveness for a number of scenarios and systems maintained by the Synapse protocol, and provide comparisons to the results of the corresponding simulations and experiments. We show that the predicted theoretical results match the obtained experimental results, and give recommendations on the design of systems using Synapse.
- Published
- 2015