1,720,976 research outputs found
Lower bounds on systolic gossip
No full textAbstractGossiping is an extensively investigated information dissemination process in which each processor has a distinct item of information and has to collect all the items possessed by the other processors. In this paper we provide an innovative and general lower bound technique relying on the novel notion of delay digraph of a gossiping protocol and on the use of matrix norm methods. Such a technique is very powerful and allows the determination of new and significantly improved lower bounds in many cases. In fact, we derive the first general lower bound on the gossiping time of systolic protocols, i.e., constituted by a periodic repetition of simple communication steps. In particular, given any network of n processors and any systolic period s, in the directed and the undirected half-duplex cases every s-systolic gossip protocol takes at least log(n)/log(1/λ)−O(loglog(n)) time steps, where λ is the unique solution between 0 and 1 of λ·p⌊s/2⌋(λ)·p⌈s/2⌉(λ)=1, with pi(λ)=1+λ2+⋯+λ2i−2 for any integer i>0. We then provide improved lower bounds in the directed and half-duplex cases for many well-known network topologies, such as Butterfly, de Bruijn, and Kautz graphs. All the results are extended also to the full-duplex case. Our technique is very general, as for s→∞ it allows the determination of improved results even for non-systolic protocols. In fact, for general networks, as a simple corollary it yields a lower bound only an O(loglog(n)) additive factor far from the general one independently proved in [Proc. 1st ACM Symposium on Parallel Algorithms and Architectures (SPAA), 1989, p. 318; Topics in Combinatorics and Graph Theory (1990) 451; SIAM Journal on Computing 21(1) (1992) 111; Discrete Applied Mathematics 42 (1993) 75] for all graphs and any (non-systolic) gossip protocol. Moreover, for specific networks, it significantly improves with respect to the previously known results, even in the full-duplex case. Correspondingly, better lower bounds on the gossiping time of non-systolic protocols are determined in the directed, half-duplex and full-duplex cases for Butterfly, de Bruijn, and Kautz graphs. Even if in this paper we give only a limited number of examples, our technique has wide applicability and gives a general framework that often allows to get improved lower bounds on the gossiping time of systolic and non-systolic protocols in the directed, half-duplex and full-duplex cases
Colouring All Directed Paths in a Symmetric Tree with an Application to Optical Networks
No full textThe "Real" approximation factor of the MST heuristic for the Minimum Energy Broadcasting
No full textThe ``Real" Approximation Factor of the MST heuristic for the Minimum Energy Broadcasting
No full textThis paper deals with one of the most studied problems in the last few years in the field of wireless
communication in ad-hoc networks. The problem consists of reducing the total energy consumption
of wireless radio stations distributed over a given area of interest in order to perform the basic
pattern of communication by a broadcast. Recently, a tight 6-approximation of the minimum spanning
tree heuristic has been proven. While such a bound is theoretically optimal if compared to the
known lower bound of 6, there is an obvious gap with practical experimental results. By extensive
experiments, proposing a new technique to generate input instances and supported by theoretical
results, we show how the approximation ratio can be actually considered close to 4 for a “real-world”
set of instances. We consider, in fact, instances more representative of common practices. Those
are usually composed by considerable number of nodes uniformly and randomly distributed inside
the area of interest
Improved Approximation Results for the Minimum Energy Broadcasting Problem
No full textIn this paper we present new results on the performance of the Minimum
Spanning Tree heuristic for the Minimum Energy Broadcast Routing (MEBR) problem.
We first prove that, for any number of dimensions d ≥ 2, the approximation ratio
of the heuristic does not increase when the power attenuation coefficient α, that is the
exponent to which the coverage distance must be raised to give the emission power,
grows. Moreover, we show that, for any fixed instance, as a limit for α going to infinity,
the ratio tends to the lower bound of Clementi et al. (Proceedings of the 18th
annual symposium on theoretical aspects of computer science (STACS), pp. 121–131,
2001),Wan et al. (Wirel. Netw. 8(6):607–617, 2002) given by the d-dimensional kissing
number, thus closing the existing gap between the upper and the lower bound. We
then introduce a new analysis allowing to establish a 7.45-approximation ratio for the 2-dimensional case, thus significantly decreasing the previously known 12 upper
bound (Wan et al. in Wirel. Netw. 8(6):607–617, 2002) (actually corrected to
12.15 in Klasing et al. (Proceedings of the 3rd IFIP-TC6 international networking
conference, pp. 866–877, 2004)). Finally, we extend our analysis to any number of
dimensions d ≥ 2 and any α ≥ d, obtaining a general approximation ratio of 3d − 1,
again independent of α. The improvements of the approximation ratios are specifically
significant in comparison with the lower bounds given by the kissing numbers,
as these grow at least exponentially with respect to d
- …
