An Optimal Broadcast Algorithm for Content-Addressable Networks
| Autor: | Ludovic Henrio, Fabrice Huet, Justine Rochas |
|---|---|
| Přispěvatelé: | Active objects, semantics, Internet and security (OASIS), 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)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Inria, Roberto Baldoni, Maarten van Steen, Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS) |
| Jazyk: | angličtina |
| Rok vydání: | 2013 |
| Předmět: |
Spanning tree
Computer science Distributed computing [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] Broadcast domain 020206 networking & telecommunications Context (language use) 02 engineering and technology Peer-to-peer computer.software_genre Content addressable network Atomic broadcast [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI] [INFO.INFO-MA]Computer Science [cs]/Multiagent Systems [cs.MA] 020204 information systems Broadcast communication network 0202 electrical engineering electronic engineering information engineering Broadcast radiation computer |
| Zdroj: | OPODIS 2013-International Conference on Principles of DIstributed Systems OPODIS 2013-International Conference on Principles of DIstributed Systems, Inria, Dec 2013, Nice, France. pp.176-190, ⟨10.1007/978-3-319-03850-6_13⟩ Lecture Notes in Computer Science ISBN: 9783319038490 OPODIS |
| Popis: | International audience; Structured peer-to-peer networks are powerful underlying structures for communication and storage systems in large-scale setting. In the context of the Content-Addressable Network (CAN), this paper addresses the following challenge: how to perform an efficient broadcast while the local view of the network is restricted to a set of neighbours? In existing approaches, either the broadcast is inefficient (there are dupli- cated messages) or it requires to maintain a particular structure among neighbours, e.g. a spanning tree. We define a new broadcast primitive for CAN that sends a minimum number of messages while covering the whole network, without any global knowledge. Currently, no other al- gorithm achieves those two goals in the context of CAN. In this sense, the contribution we propose in this paper is threefold. First, we pro- vide an algorithm that sends exactly one message per recipient without building a global view of the network. Second, we prove the absence of duplicated messages and the coverage of the whole network when using this algorithm. Finally, we show the practical benefits of the algorithm throughout experiments. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|