Broadcasting algorithms in radio networks with unknown topology

In this paper we present new randomized and deterministic algorithms for the classical problem of broadcasting in radio networks with unknown topology. We consider directed n-node radio networks with specified eccentricity D (maximum distance from the source node to any other node). Bar-Yehuda et al. presented an algorithm that for any n-node radio network with eccentricity D completes the broadcasting in time, with high probability. This result is almost optimal, since as it has been shown by Kushilevitz and Mansour and Alon et al., every randomized algorithm requires Ω(Dlog(n/D)+log²n) expected time to complete broadcasting.Our first main result closes the gap between the lower and upper bound: we describe an optimal randomized broadcasting algorithm whose running time complexity is , with high probability. In particular, we obtain a randomized algorithm that completes broadcasting in any n-node radio network in time , with high probability.The main source of our improvement is a better “selecting sequence” used by the algorithm that brings some stronger property and improves the broadcasting time. Two types of “selecting sequences” are considered: randomized and deterministic ones. The algorithm with a randomized sequence is easier (more intuitive) to analyze but both randomized and deterministic sequences give algorithms of the same asymptotic complexity.Next, we demonstrate how to apply our approach to deterministic broadcasting, and describe a deterministic oblivious algorithm that completes broadcasting in time , which improves upon best known algorithms in this case. The fastest previously known algorithm had the broadcasting time of , it was non-oblivious and significantly more complicated; our algorithm can be seen as a natural extension of our randomized algorithm. In this part of the paper we assume that each node knows the eccentricity D.Finally, we show how our randomized broadcasting algorithm can be used to improve the randomized complexity of the gossiping problem.     

Existence and Regularity of a Class of Weak Solutions to the Navier–Stokes Equations

We construct a class of weak solutions to the Navier–Stokes equations, which have second order spatial derivatives and one order time derivatives, ofppower summability for 1 < p ≤ 5/4. Meanwhile, we show thatu L^s(0, T; W^{2, r}(Ω)) with 1/s + 3/2r = 2 for 1 < r ≤ 5/4.rcan be relaxed not to exceed 3/2 if we consider only in the interior of Ω. In the end, we extend the classical regularity theorem. Our results show thatuis a regular solution if u L^s(0, T; L^r(Ω)) with 1/s + 3/2r = 1 for Ω satisfying (1.3), with 1/s + 1/r = 5/6 for arbitrary domain inR³and 1 < s ≤ 2. For Ω = Rⁿwithn ≥ 3, this result was previously obtained byH. Beirão da Veiga (Chinese Ann. Math. Ser. B16, 1995, 407–412).     

The compactness of adaptive routing tables

The compactness of a routing table is a complexity measure of the memory space needed to store the routing table on a network whose nodes have been labelled by a consecutive range of integers. It is defined as the smallest integer k such that, in every node u, every set of labels of destinations having the same output in the table of u can be represented as the union of k intervals of consecutive labels. While many works studied the compactness of deterministic routing tables, few of them tackled the adaptive case when the output of the table, for each entry, must contain a fixed number α of routing directions. We prove that every n-node network supports shortest path routing tables of compactness at most n/α for an adaptiveness parameter α, whereas we show a lower bound of n/α^O(1).     

Harmonicity of functions satisfying a weak form of the mean value property

Let W ì \Bbb Rⁿ\Omega \subset {\Bbb R}^n be a smooth domain and let u ? C⁰(W).u \in C^0(\Omega ). A classical result of potential theory states that¶¶-ò_{Sr([`(x)])</sub> u(x)ds(x)=u([`(x)])-\kern-5mm\int\limits _{S_{r}(\bar x)} u(x)d\sigma (x)=u(\bar x)¶¶for every [`(x)] ? W\bar x\in \Omega and r > 0r>0 if and only if¶¶Du=0 in W.\Delta u=0 \hbox { in } \Omega.¶¶Here -ò<sub>Sr([`(x)])} u(x)ds(x)-\kern-5mm\int\limits _{S_{r}(\bar x)} u(x)d\sigma (x) denotes the average of u on the sphere S_r([`(x)])S_r(\bar x) of center [`(x)]\bar x and radius r. Our main result, which is a "localized" version of the above result, states:¶¶Theorem. Let u ? W^2,1(W)u\in W^{2,1}(\Omega ) and let x ? Wx\in \Omega be a Lebesgue point of Du\Delta u such that¶¶-ò_Sr([`(x)]) u d s- a = o(r²)-\kern-5mm\int\limits _{S_{r}(\bar x)} u d \sigma - \alpha =o(r^2)¶¶for some a ? \Bbb R\alpha \in \Bbb R and all sufficiently small r > 0.r>0. Then¶¶Du(x)=0.\Delta u(x)=0.     

The Serendipity Family of Finite Elements

We give a new, simple, dimension-independent definition of the serendipity finite element family. The shape functions are the span of all monomials which are linear in at least s−r of the variables where s is the degree of the monomial or, equivalently, whose superlinear degree (total degree with respect to variables entering at least quadratically) is at most r. The degrees of freedom are given by moments of degree at most r−2d on each face of dimension d. We establish unisolvence and a geometric decomposition of the space.     

Reconstructing edge-disjoint paths

For an undirected graph G=(V,E), the edge connectivity values between every pair of nodes of G can be succinctly recorded in a flow-equivalent tree that contains the edge connectivity value for a linear number of pairs of nodes. We generalize this result to show how we can efficiently recover a maximum set of disjoint paths between any pair of nodes of G by storing such sets for a linear number of pairs of nodes. At the heart of our result is an observation that combining two flow solutions of the same value, one between nodes s and r and the second between nodes r and t, into a feasible flow solution of value f between nodes s and t, is equivalent to solving a stable matching problem on a bipartite multigraph.Our observation, combined with an observation of Chazelle, leads to a data structure, which takes O(n^3.5) time to generate, that can construct the maximum number λ(u,v) of edge-disjoint paths between any pair (u,v) of nodes in time O(α(n,n)λ(u,v)n) time.     

No TVD Fields for 1-D Isentropic Gas Flow

We prove that isentropic gas flow does not admit non-degenerate TVD fields on any invariant set ?(r ₀, s ₀) = {r ₀ < r < s < s ₀}, where r, s are Riemann coordinates. A TVD field refers to a scalar field whose spatial variation Var _X (?(τ(t, X), u(t, X))) is non-increasing in time along entropic solutions. The result is established under the assumption that the Riemann problem defined by an overtaking shock-rarefaction interaction gives the asymptotic states in the exact solution.

Little is known about global existence of large-variation solutions to hyperbolic systems of conservation laws u _t  + f(u) _x  = 0. In particular it is not known if isentropic gas flow admits a priori BV bounds which apply to all BV data.

In the few cases where such results are available (scalar case, Temple class, systems satisfying Bakhvalov's condition, isothermal gas dynamics) there are TVD fields which play a key role for existence. Our results show that the same approach cannot work for isentropic flow.     

Positive solutions for systems of nonlinear eigenvalue problems for functional differential equations

Values of?λ?are determined for which there exist positive solutions of the system of functional differential equations, u″?+?λa(t)f(v _t )?=?0,v″?+?λb(t)g(u _t )?=?0, for 0?t?u(s)?=?v(s)?=?φ(s), ?r?≤?s?≤?0, and the boundary conditions u(0)?=?v(0)?=?φ(0)?=?u(1)?=?v(1)?=?0. A Guo–Krasnosel'skii fixed point theorem is applied.     

Regularized inner products of distorted plane waves and near-forward inverse scattering

Regularized inner products, r(s, e₁, e₂,) of the distorted plane waves fór the plasma wave equation u_u ? Δu + qu = 0 are introduced for potentials with compact support. The regularized inner product may be represented in terms of the far-field pattern. The use of the WKB approximation shows that the behaviour of r as e₂ → ? e₁ is closely related to the Radon transform of q. This observation indicates the possibility of finding the Radon transform of q in terms of r(s, e₁, e₂) and then of recovering q by means of the inverse Radon transform.     

Intersection graphs of proper subtrees of unicyclic graphs

A graph is fraternally oriented iff for every three vertices u, ν, w the existence of the edges u → w and ν → w implies that u and ν are adjacent. A directed unicyclic graph is obtained from a unicyclic graph by orienting the unique cycle clockwise and by orienting the appended subtrees from the cycle outwardly. Two directed subtrees s, t of a directed unicyclic graph are proper if their union contains no (directed or undirected) cycle and either they are disjoint or one of them s has its root r(s) in t and contains all the successors of r(s) in t. In the present paper we prove that G is an intersection graph of a family of proper directed subtrees of a directed unicyclic graph iff it has a fraternal orientation such that for every vertex ν, G(Γⁱⁿν) is acyclic and G(Γ^outν) is the transitive closure of a tree. We describe efficient algorithms for recognizing when such graphs are perfect and for testing isomorphism of proper circular-arc graphs.     

Fast broadcasting and gossiping in radio networks

We establish an O(nlog²n) upper bound on the time for deterministic distributed broadcasting in multi-hop radio networks with unknown topology. This nearly matches the known lower bound of Ω(nlogn). The fastest previously known algorithm for this problem works in time O(n^3/2). Using our broadcasting algorithm, we develop an O(n^3/2log²n) algorithm for gossiping in the same network model.     

Reliable Broadcasting in Logarithmic Time with Byzantine Link Failures

Broadcasting is a process of transmitting a message held in one node of a communication network to all other nodes. Links of the network are subject to randomly and independently distributed faults with probability; faults are permanent and Byzantine, while all nodes are fault-free. In a unit of time, each node can communicate with at most one other node. We present a broadcasting algorithm which works fornnodes in timeO(log n) with probability of correctness exceeding 1 − 1/n, for sufficiently largen.     

A higher-order large-scale regularity theory for random elliptic operators

We develop a large-scale regularity theory of higher order for divergence-form elliptic equations with heterogeneous coefficient fields a in the context of stochastic homogenization. The large-scale regularity of a-harmonic functions is encoded by Liouville principles: The space of a-harmonic functions that grow at most like a polynomial of degree k has the same dimension as in the constant-coefficient case. This result can be seen as the qualitative side of a large-scale C^k,α-regularity theory, which in the present work is developed in the form of a corresponding C^k,α-“excess decay” estimate: For a given a-harmonic function u on a ball B_R, its energy distance on some ball B_r to the above space of a-harmonic functions that grow at most like a polynomial of degree k has the natural decay in the radius r above some minimal radius r₀.

Though motivated by stochastic homogenization, the contribution of this paper is of purely deterministic nature: We work under the assumption that for the given realization a of the coefficient field, the couple (φ, σ) of scalar and vector potentials of the harmonic coordinates, where φ is the usual corrector, grows sublinearly in a mildly quantified way. We then construct “kth-order correctors” and thereby the space of a-harmonic functions that grow at most like a polynomial of degree k, establish the above excess decay, and then the corresponding Liouville principle.     

Analysis of a Free Boundary Problem Modeling Tumor Growth

In this paper, we study a free boundary problem arising from the modeling of tumor growth. The problem comprises two unknown functions： R = R（t）, the radius of the tumor, and u = u（r, t）, the concentration of nutrient in the tumor. The function u satisfies a nonlinear reaction diffusion equation in the region 0 〈 r 〈 R（t）, t 〉 0, and the function R satisfies a nonlinear integrodifferential equation containing u. Under some general conditions, we establish global existence of transient solutions, unique existence of a stationary solution, and convergence of transient solutions toward the stationary solution as t →∞.     

Uniform decay estimates for solutions of the Yamabe equation

We study positive solutions u of the Yamabe equation c_m Du-s( x) u+k( x) u^\fracm+2m-2=0{c_{m} \Delta u-s\left( x\right) u+k\left( x\right) u^{\frac{m+2}{m-2}}=0}, when k(x) > 0, on manifolds supporting a Sobolev inequality. In particular we get uniform decay estimates at infinity for u which depend on the behaviour at infinity of k, s and the L ^Γ-norm of u, for some G 3 \tfrac2mm-2{\Gamma\geq\tfrac{2m}{m-2}}. The required integral control, in turn, is implied by further geometric conditions. Finally we give an application to conformal immersions into the sphere.     

Distributed near-optimal matching

In this paper, we consider the following distributed bipartite matching problem: LetG=(L,R;E) be a bipartite graph in which boys are partL (left nodes), and girls are partR (right nodes.) There is an edge(l _i ,r _j )E iff boyl _i is interested in girlr _j . Every boyl _i will propose to a girlr _j among all those he is interested in, i.e., his adjacent right nodes in the bipartite graphG. If several boys propose to the same girl, only one of them will be accepted by the girl. We assume that none of the boys communicate with others. This matching problem is typical of distributed computing under incomplete information: Each boy only knows his own preference but none of the others. We first study the one-round matching problem: each boy proposes to at most one girl, so that the total number of girls receiving a proposal is maximized. If the maximum matching isM, then no deterministic algorithm can produce a matching of size not bounded by a constant, but a randomized algorithm achieves — and this is shown optimal by an adversary argument. If we allow many rounds in matching, with the senders learning from their failures, then, for deterministic algorithms, the ratio (of the optimal solution to the solution of the algorithm) is unbounded when the number of rounds is smaller than (G), and becomes bounded (two) at the (G)-th round. In contrast, an extension of the one-round randomized algorithm establishes that there is no such discontinuity in the randomized case. This randomized result is also matched by an upper bound of asymptotically the same order.     

Some remarks on solutions to an overdetermined elliptic problem in divergence form in a ball

We prove the existence of a continuum of non-radial pairs (k,u) solutions to the following overposed problem div in B _r , u = 0 and on ∂B _r , where B _r is the Euclidean ball centered at zero of radius r in . Dedicato a Marco e Andrea Provera.     

Centers to centroids in graphs

For S ? V(G) the S-center and S-centroid of G are defined as the collection of vertices u ∈ V(G) that minimize e_s(u) = max {d(u, v): v ∈ S} and d_s(u) = ∑_u∈S d(u, v), respectively. This generalizes the standard definition of center and centroid from the special case of S = V(G). For 1 ? k ?|V(G)| and u ∈ V(G) let r_k(u) = max {∑_s∈S d(u, s): S ? V(G), |S| = k}. The k-centrum of G, denoted C(G; k), is defined to be the subset of vertices u in G for which r_k(u) is a minimum. This also generalizes the standard definitions of center and centroid since C(G; 1) is the center and C(G; |V(G)|) is the centroid. In this paper the structure of these sets for trees is examined. Generalizations of theorems of Jordan and Zelinka are included.     

Improved algorithm for broadcast scheduling of minimal latency in wireless ad hoc networks

A wide range of applications for wireless ad hoc networks are time-critical and impose stringent requirement on the communication latency. One of the key communication operations is to broadcast a message from a source node. This paper studies the minimum latency broadcast scheduling problem in wireless ad hoc networks under collision-free transmission model. The previously best known algorithm for this NP-hard problem produces a broadcast schedule whose latency is at least 648（rmax/rmin）^2 times that of the optimal schedule, where rmax and rmin are the maximum and minimum transmission ranges of nodes in a network, respectively. We significantly improve this result by proposing a new scheduling algorithm whose approximation performance ratio is at most （1 ＋ 2rmax/rmin）^2＋32, Moreover, under the proposed scheduling each node just needs to forward a message at most once.