id: 05783804
dt: a
an: 05783804
au: Fernández Anta, Antonio; Milani, Alessia; Mosteiro, Miguel A.; Zaks,
    Shmuel
ti: Opportunistic information dissemination in mobile ad-hoc networks: the
    profit of global synchrony.
so: Lynch, Nancy A. (ed.) et al., Distributed computing. 24th international
    symposium, DISC 2010, Cambridge, MA, USA, September 13‒15, 2010.
    Proceedings. Berlin: Springer (ISBN 978-3-642-15762-2/pbk). Lecture
    Notes in Computer Science 6343, 374-388 (2010).
py: 2010
pu: Berlin: Springer
la: EN
cc: 
ut: 
ci: 
li: doi:10.1007/978-3-642-15763-9_34
ab: Summary: The topic of this paper is the study of Information Dissemination
    in Mobile Ad-hoc Networks by means of deterministic protocols. We
    characterize the connectivity resulting from the movement, from
    failures and from the fact that nodes may join the computation at
    different times with two values, $α$ and $β$, so that, within $α$
    time slots, some node that has the information must be connected to
    some node without it for at least $β$ time slots. The protocols
    studied are classified into three classes: oblivious (the transmission
    schedule of a node is only a function of its ID), quasi-oblivious (the
    transmission schedule may also depend on a global time), and adaptive.
    The main contribution of this work concerns negative results.
    Contrasting the lower and upper bounds derived, interesting complexity
    gaps among protocol-classes are observed. More precisely, in order to
    guarantee any progress towards solving the problem, it is shown that
    $β$ must be at least $n - 1$ in general, but that $β\in Ω(n^{2} /
    \log n)$ if an oblivious protocol is used. Since quasi-oblivious
    protocols can guarantee progress with $β\in O(n)$, this represents a
    significant gap, almost linear in $β$, between oblivious and
    quasi-oblivious protocols. Regarding the time to complete the
    dissemination, a lower bound of $Ω(n α+ n^{3} / \log n)$ is proved
    for oblivious protocols. These results show that the gap in time
    complexity between oblivious and quasi-oblivious, and hence adaptive,
    protocols is almost linear. This gap is what we call the profit of
    global synchrony, since it represents the gain the network obtains from
    global synchrony with respect to not having it.
rv: