2011/05/30 by Martı́n Farach-Colton, Farach-Colton, Martin, Antonio Fernández Anta +7
Computer Science · #68Q25 #C.2.2 #C.2.4 #Cooperative Communication and Network Coding #Data Structures and Algorithms (cs.DS) #Distributed #Distributed systems and fault tolerance #F.2.0 #FOS: Computer and information sciences #Mobile Ad Hoc Networks #Networking and Internet Architecture (cs.NI) #Opportunistic and Delay-Tolerant Networks #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1105.6151
openalex publication_date 2011/05/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper the problem of information dissemination in Mobile Ad-hoc\nNetworks (MANET) is studied. The problem is to disseminate a piece of\ninformation, initially held by a distinguished source node, to all nodes in a\nset defined by some predicate. We use a model of MANETs that is well suited for\ndynamic networks and opportunistic communication. In this model nodes are\nplaced in a plane, in which they can move with bounded speed, and communication\nbetween nodes occurs over a collision-prone single channel. In this setup\ninformed and uninformed nodes can be disconnected for some time (bounded by a\nparameter alpha), but eventually some uninformed node must become neighbor of\nan informed node and remain so for some time (bounded by a parameter beta). In\naddition, nodes can start at different times, and they can crash and recover.\nUnder the above framework, we show negative and positive results for different\ntypes of randomized protocols, and we put those results in perspective with\nrespect to previous deterministic results.\n