Rendezvous in networks in spite of delay faults

Two mobile agents, starting from different nodes of an unknown network, have to meet at a node. Agents move in synchronous rounds using a deterministic algorithm. Each agent has a different label, which it can use in the execution of the algorithm, but it does not know the label of the other agent. Agents do not know any bound on the size of the network. In each round an agent decides if it remains idle or if it wants to move to one of the adjacent nodes. Agents are subject to delay faults: if an agent incurs a fault in a given round, it remains in the current node, regardless of its decision. If it planned to move and the fault happened, the agent is aware of it. We consider three scenarios of fault distribution: random (independently in each round and for each agent with constant probability \(0<p<1\)), unbounded adversarial (the adversary can delay an agent for an arbitrary finite number of consecutive rounds) and bounded adversarial (the adversary can delay an agent for at most c consecutive rounds, where c is unknown to the agents). The quality measure of a rendezvous algorithm is its cost, which is the total number of edge traversals. For random faults, we show an algorithm with cost polynomial in the size n of the network and polylogarithmic in the larger label L, which achieves rendezvous with very high probability in arbitrary networks. By contrast, for unbounded adversarial faults we show that rendezvous is not possible, even in the class of rings. Under this scenario we give a rendezvous algorithm with cost \(O(n\ell )\), where \(\ell \) is the smaller label, working in arbitrary trees, and we show that \(\varOmega (\ell )\) is the lower bound on rendezvous cost, even for the two-node tree. For bounded adversarial faults, we give a rendezvous algorithm working for arbitrary networks, with cost polynomial in n, and logarithmic in the bound c and in the larger label L.     

Fast arithmetic in algorithmic self-assembly

In this paper we consider the time complexity of adding two n-bit numbers together within the tile self-assembly model. The (abstract) tile assembly model is a mathematical model of self-assembly in which system components are square tiles with different glue types assigned to tile edges. Assembly is driven by the attachment of singleton tiles to a growing seed assembly when the net force of glue attraction for a tile exceeds some fixed threshold. Within this frame work, we examine the time complexity of computing the sum of two n-bit numbers, where the input numbers are encoded in an initial seed assembly, and the output sum is encoded in the final, terminal assembly of the system. We show that this problem, along with multiplication, has a worst case lower bound of \(\varOmega ( \sqrt{n} )\) in 2D assembly, and \(\varOmega (\root 3 \of {n})\) in 3D assembly. We further design algorithms for both 2D and 3D that meet this bound with worst case run times of \(O(\sqrt{n})\) and \(O(\root 3 \of {n})\) respectively, which beats the previous best known upper bound of O(n). Finally, we consider average case complexity of addition over uniformly distributed n-bit strings and show how we can achieve \(O(\log n)\) average case time with a simultaneous \(O(\sqrt{n})\) worst case run time in 2D. As additional evidence for the speed of our algorithms, we implement our algorithms, along with the simpler O(n) time algorithm, into a probabilistic run-time simulator and compare the timing results.     

A greedy approximation algorithm for minimum-gap scheduling

We consider scheduling of unit-length jobs with release times and deadlines, where the objective is to minimize the number of gaps in the schedule. Polynomial-time algorithms for this problem are known, yet they are rather inefficient, with the best algorithm running in time \(O(n^4)\) and requiring \(O(n^3)\) memory. We present a greedy algorithm that approximates the optimum solution within a factor of 2 and show that our analysis is tight. Our algorithm runs in time \(O(n^2 \log n)\) and needs only O(n) memory. In fact, the running time is \(O(n (g^*+1)\log n)\), where \(g^*\) is the minimum number of gaps.     

Tight bounds for parallel randomized load balancing

Given a distributed system of \(n\) balls and \(n\) bins, how evenly can we distribute the balls to the bins, minimizing communication? The fastest non-adaptive and symmetric algorithm achieving a constant maximum bin load requires \(\varTheta (\log \log n)\) rounds, and any such algorithm running for \(r\in {\mathcal {O}}(1)\) rounds incurs a bin load of \(\varOmega ((\log n/\log \log n)^{1/r})\). In this work, we explore the fundamental limits of the general problem. We present a simple adaptive symmetric algorithm that achieves a bin load of 2 in \(\log ^* n+{\mathcal {O}}(1)\) communication rounds using \({\mathcal {O}}(n)\) messages in total. Our main result, however, is a matching lower bound of \((1-o(1))\log ^* n\) on the time complexity of symmetric algorithms that guarantee small bin loads. The essential preconditions of the proof are (i) a limit of \({\mathcal {O}}(n)\) on the total number of messages sent by the algorithm and (ii) anonymity of bins, i.e., the port numberings of balls need not be globally consistent. In order to show that our technique yields indeed tight bounds, we provide for each assumption an algorithm violating it, in turn achieving a constant maximum bin load in constant time.     

The panpositionable panconnectedness of crossed cubes

In many parallel and distributed multiprocessor systems, the processors are connected based on different types of interconnection networks. The topological structure of an interconnection network is typically modeled as a graph. Among the many kinds of network topologies, the crossed cube is one of the most popular. In this paper, we investigate the panpositionable panconnectedness problem with respect to the crossed cube. A graph G is r-panpositionably panconnected if for any three distinct vertices x, y, z of G and for any integer \(l_1\) satisfying \(r \le l_1 \le |V(G)| - r - 1\), there exists a path \(P = [x, P_1, y, P_2, z]\) in G such that (i) \(P_1\) joins x and y with \(l(P_1) = l_1\) and (ii) \(P_2\) joins y and z with \(l(P_2) = l_2\) for any integer \(l_2\) satisfying \(r \le l_2 \le |V(G)| - l_1 - 1\), where |V(G)| is the total number of vertices in G and \(l(P_1)\) (respectively, \(l(P_2)\)) is the length of path \(P_1\) (respectively, \(P_2\)). By mathematical induction, we demonstrate that the n-dimensional crossed cube \(CQ_n\) is n-panpositionably panconnected. This result indicates that the path embedding of joining x and z with a mediate vertex y in \(CQ_n\) is extremely flexible. Moreover, applying our result, crossed cube problems such as panpositionable pancyclicity, panpositionably Hamiltonian connectedness, and panpositionable Hamiltonicity can be solved.     

Throughput maximization for speed scaling with agreeable deadlines

We study the following energy-efficient scheduling problem. We are given a set of n jobs which have to be scheduled by a single processor whose speed can be varied dynamically. Each job \(J_j\) is characterized by a processing requirement (work) \(p_j\), a release date \(r_j\), and a deadline \(d_j\). We are also given a budget of energy E which must not be exceeded and our objective is to maximize the throughput (i.e., the number of jobs which are completed on time). We show that the problem can be solved optimally via dynamic programming in \(O(n^4 \log n \log P)\) time when all jobs have the same release date, where P is the sum of the processing requirements of the jobs. For the more general case with agreeable deadlines where the jobs can be ordered so that, for every \(i < j\), it holds that \(r_i \le r_j\) and \(d_i \le d_j\), we propose an optimal dynamic programming algorithm which runs in \(O(n^6 \log n \log P)\) time. In addition, we consider the weighted case where every job \(J_j\) is also associated with a weight \(w_j\) and we are interested in maximizing the weighted throughput (i.e., the total weight of the jobs which are completed on time). For this case, we show that the problem becomes \(\mathcal{NP}\)-hard in the ordinary sense even when all jobs have the same release date and we propose a pseudo-polynomial time algorithm for agreeable instances.     

Adjoint-Based,Superconvergent Galerkin Approximations of Linear Functionals

We propose a new technique for computing highly accurate approximations to linear functionals in terms of Galerkin approximations. We illustrate the technique on a simple model problem, namely, that of the approximation of J(u), where \(J(\cdot )\) is a very smooth functional and u is the solution of a Poisson problem; we assume that the solution u and the solution of the adjoint problem are both very smooth. It is known that, if \(u_h\) is the approximation given by the continuous Galerkin method with piecewise polynomials of degree \(k>0\), then, as a direct consequence of its property of Galerkin orthogonality, the functional \(J(u_h)\) converges to J(u) with a rate of order \(h^{2k}\). We show how to define approximations to J(u), with a computational effort about twice of that of computing \(J(u_h)\), which converge with a rate of order \(h^{4k}\). The new technique combines the adjoint-recovery method for providing precise approximate functionals by Pierce and Giles (SIAM Rev 42(2):247–264, 2000), which was devised specifically for numerical approximations without a Galerkin orthogonality property, and the accuracy-enhancing convolution technique of Bramble and Schatz (Math Comput 31(137):94–111, 1977), which was devised specifically for numerical methods satisfying a Galerkin orthogonality property, that is, for finite element methods like, for example, continuous Galerkin, mixed, discontinuous Galerkin and the so-called hybridizable discontinuous Galerkin methods. For the latter methods, we present numerical experiments, for \(k=1,2,3\) in one-space dimension and for \(k=1,2\) in two-space dimensions, which show that \(J(u_h)\) converges to J(u) with order \(h^{2k+1}\) and that the new approximations converges with order \(h^{4k}\). The numerical experiments also indicate, for the p-version of the method, that the rate of exponential convergence of the new approximations is about twice that of \(J(u_h)\).     

Close to linear space routing schemes

Let \(G=(V,E)\) be an unweighted undirected graph with n vertices and m edges, and let \(k>2\) be an integer. We present a routing scheme with a poly-logarithmic header size, that given a source s and a destination t at distance \(\varDelta \) from s, routes a message from s to t on a path whose length is \(O(k\varDelta +m^{1/k})\). The total space used by our routing scheme is \(mn^{O(1/\sqrt{\log n})}\), which is almost linear in the number of edges of the graph. We present also a routing scheme with \(n^{O(1/\sqrt{\log n})}\) header size, and the same stretch (up to constant factors). In this routing scheme, the routing table of every \(v\in V\) is at most \(kn^{O(1/\sqrt{\log n})}deg(v)\), where deg(v) is the degree of v in G. Our results are obtained by combining a general technique of Bernstein (2009), that was presented in the context of dynamic graph algorithms, with several new ideas and observations.     

Propagation of correlations in local random quantum circuits

We derive a dynamical bound on the propagation of correlations in local random quantum circuits—lattice spin systems where piecewise quantum operations—in space and time—occur with classical probabilities. Correlations are quantified by the Frobenius norm of the commutator of two positive operators acting on disjoint regions of a one-dimensional circular chain of length L. For a time \(t=O(L)\), correlations spread ballistically to spatial distances \(\mathcal {D}=t\), growing at best, diffusively with time for any distance within that radius with extensively suppressed distance- dependent corrections. For \(t=\varOmega (L^2)\), all parts of the system get almost equally correlated with exponentially suppressed distance- dependent corrections and approach the maximum amount of correlations that may be established asymptotically.     

The hierarchical Petersen network: a new interconnection network with fixed degree

Network cost and fixed-degree characteristic for the graph are important factors to evaluate interconnection networks. In this paper, we propose hierarchical Petersen network (HPN) that is constructed in recursive and hierarchical structure based on a Petersen graph as a basic module. The degree of HPN(n) is 5, and HPN(n) has \(10^n\) nodes and \(2.5 \times 10^n\) edges. And we analyze its basic topological properties, routing algorithm, diameter, spanning tree, broadcasting algorithm and embedding. From the analysis, we prove that the diameter and network cost of HPN(n) are \(3\log _{10}N-1\) and \(15 \log _{10}N-1\), respectively, and it contains a spanning tree with the degree of 4. In addition, we propose link-disjoint one-to-all broadcasting algorithm and show that HPN(n) can be embedded into FP\(_k\) with expansion 1, dilation 2k and congestion 4. For most of the fixed-degree networks proposed, network cost and diameter require \(O(\sqrt{N})\) and the degree of the graph requires O(N). However, HPN(n) requires O(1) for the degree and \(O(\log _{10}N)\) for both diameter and network cost. As a result, the suggested interconnection network in this paper is superior to current fixed-degree and hierarchical networks in terms of network cost, diameter and the degree of the graph.     

An optimal adaptive stabilizing algorithm for two edge-disjoint paths problem

The problem of two edge-disjoint paths is to identify two paths \(Q_1\) and \(Q_2\) from source \(s \in V\) to target \(t \in V\) without any common arc in a directed connected graph \(G=(V, E)\). In this paper, we present an adaptive stabilizing algorithm for finding a pair of edge-disjoint paths from s to t in G in O(D) rounds with state-space complexity of \(O(log\; n)\) bits per process, where n is the number of nodes and D is the diameter of the graph. The proposed algorithm is optimal with respect to its time complexity, and the total length of the shortest paths. In addition, it can also be used to solve the problem for undirected graphs. Since the proposed algorithm is stabilizing, it does not require initialization and is capable of withstanding transient faults. We view a fault that perturbs the state of the system but not its program as a transient fault. In addition, the proposed algorithm is adaptive since it is capable of dealing with topology changes in the form of addition/removal of arcs and/or nodes as well as changes in the directions of arcs provided that two edge-disjoint paths between s and t exist after the topology change.     

Construction of quantum caps in projective space <Emphasis Type="Italic">PG</Emphasis>(<Emphasis Type="Italic">r</Emphasis>, 4) and quantum codes of distance 4

Constructions of quantum caps in projective space PG(r, 4) by recursive methods and computer search are discussed. For each even n satisfying \(n\ge 282\) and each odd z satisfying \(z\ge 275\), a quantum n-cap and a quantum z-cap in \(PG(k-1, 4)\) with suitable k are constructed, and \([[n,n-2k,4]]\) and \([[z,z-2k,4]]\) quantum codes are derived from the constructed quantum n-cap and z-cap, respectively. For \(n\ge 282\) and \(n\ne 286\), 756 and 5040, or \(z\ge 275\), the results on the sizes of quantum caps and quantum codes are new, and all the obtained quantum codes are optimal codes according to the quantum Hamming bound. While constructing quantum caps, we also obtain many large caps in PG(r, 4) for \(r\ge 11\). These results concerning large caps provide improved lower bounds on the maximal sizes of caps in PG(r, 4) for \(r\ge 11\).     

Data assimilation and sampling in Banach spaces

This paper studies the problem of approximating a function f in a Banach space \(\mathcal{X}\) from measurements \(l_j(f)\), \(j=1,\ldots ,m\), where the \(l_j\) are linear functionals from \(\mathcal{X}^*\). Quantitative results for such recovery problems require additional information about the sought after function f. These additional assumptions take the form of assuming that f is in a certain model class \(K\subset \mathcal{X}\). Since there are generally infinitely many functions in K which share these same measurements, the best approximation is the center of the smallest ball B, called the Chebyshev ball, which contains the set \(\bar{K}\) of all f in K with these measurements. Therefore, the problem is reduced to analytically or numerically approximating this Chebyshev ball. Most results study this problem for classical Banach spaces \(\mathcal{X}\) such as the \(L_p\) spaces, \(1\le p\le \infty \), and for K the unit ball of a smoothness space in \(\mathcal{X}\). Our interest in this paper is in the model classes \(K=\mathcal{K}(\varepsilon ,V)\), with \(\varepsilon >0\) and V a finite dimensional subspace of \(\mathcal{X}\), which consists of all \(f\in \mathcal{X}\) such that \(\mathrm{dist}(f,V)_\mathcal{X}\le \varepsilon \). These model classes, called approximation sets, arise naturally in application domains such as parametric partial differential equations, uncertainty quantification, and signal processing. A general theory for the recovery of approximation sets in a Banach space is given. This theory includes tight a priori bounds on optimal performance and algorithms for finding near optimal approximations. It builds on the initial analysis given in Maday et al. (Int J Numer Method Eng 102:933–965, 2015) for the case when \(\mathcal{X}\) is a Hilbert space, and further studied in Binev et al. (SIAM UQ, 2015). It is shown how the recovery problem for approximation sets is connected with well-studied concepts in Banach space theory such as liftings and the angle between spaces. Examples are given that show how this theory can be used to recover several recent results on sampling and data assimilation.     

Numerical Methods and Comparison for the Dirac Equation in the Nonrelativistic Limit Regime

We analyze rigorously error estimates and compare numerically spatial/temporal resolution of various numerical methods for the discretization of the Dirac equation in the nonrelativistic limit regime, involving a small dimensionless parameter \(0<\varepsilon \ll 1\) which is inversely proportional to the speed of light. In this limit regime, the solution is highly oscillatory in time, i.e. there are propagating waves with wavelength \(O(\varepsilon ^2)\) and O(1) in time and space, respectively. We begin with several frequently used finite difference time domain (FDTD) methods and obtain rigorously their error estimates in the nonrelativistic limit regime by paying particular attention to how error bounds depend explicitly on mesh size h and time step \(\tau \) as well as the small parameter \(\varepsilon \). Based on the error bounds, in order to obtain ‘correct’ numerical solutions in the nonrelativistic limit regime, i.e. \(0<\varepsilon \ll 1\), the FDTD methods share the same \(\varepsilon \)-scalability on time step and mesh size as: \(\tau =O(\varepsilon ^3)\) and \(h=O(\sqrt{\varepsilon })\). Then we propose and analyze two numerical methods for the discretization of the Dirac equation by using the Fourier spectral discretization for spatial derivatives combined with the symmetric exponential wave integrator and time-splitting technique for temporal derivatives, respectively. Rigorous error bounds for the two numerical methods show that their \(\varepsilon \)-scalability is improved to \(\tau =O(\varepsilon ^2)\) and \(h=O(1)\) when \(0<\varepsilon \ll 1\). Extensive numerical results are reported to support our error estimates.     

Parallel construction of wavelet trees on multicore architectures

The wavelet tree has become a very useful data structure to efficiently represent and query large volumes of data in many different domains, from bioinformatics to geographic information systems. One problem with wavelet trees is their construction time. In this paper, we introduce two algorithms that reduce the time complexity of a wavelet tree’s construction by taking advantage of nowadays ubiquitous multicore machines. Our first algorithm constructs all the levels of the wavelet in parallel with O(n) time and \(O(n\lg \sigma + \sigma \lg n)\) bits of working space, where n is the size of the input sequence and \(\sigma \) is the size of the alphabet. Our second algorithm constructs the wavelet tree in a domain decomposition fashion, using our first algorithm in each segment, reaching \(O(\lg n)\) time and \(O(n\lg \sigma + p\sigma \lg n/\lg \sigma )\) bits of extra space, where p is the number of available cores. Both algorithms are practical and report good speedup for large real datasets.     

Entanglement witness criteria of strong-<Emphasis Type="Italic">k</Emphasis>-separability for multipartite quantum states

Let \(H_{1}, H_{2},\ldots ,H_{n}\) be separable complex Hilbert spaces with \(\dim H_{i}\ge 2\) and \(n\ge 2\). Assume that \(\rho \) is a state in \(H=H_1\otimes H_2\otimes \cdots \otimes H_n\). \(\rho \) is called strong-k-separable \((2\le k\le n)\) if \(\rho \) is separable for any k-partite division of H. In this paper, an entanglement witnesses criterion of strong-k-separability is obtained, which says that \(\rho \) is not strong-k-separable if and only if there exist a k-division space \(H_{m_{1}}\otimes \cdots \otimes H_{m_{k}}\) of H, a finite-rank linear elementary operator positive on product states \(\Lambda :\mathcal {B}(H_{m_{2}}\otimes \cdots \otimes H_{m_{k}})\rightarrow \mathcal {B}(H_{m_{1}})\) and a state \(\rho _{0}\in \mathcal {S}(H_{m_{1}}\otimes H_{m_{1}})\), such that \(\mathrm {Tr}(W\rho )<0\), where \(W=(\mathrm{Id}\otimes \Lambda ^{\dagger })\rho _{0}\) is an entanglement witness. In addition, several different methods of constructing entanglement witnesses for multipartite states are also given.     

Nearly optimal bounds for distributed wireless scheduling in the SINR model

We study the wireless scheduling problem in the SINR model. More specifically, given a set of \(n\) links, each a sender–receiver pair, we wish to partition (or schedule) the links into the minimum number of slots, each satisfying interference constraints allowing simultaneous transmission. In the basic problem, all senders transmit with the same uniform power. We analyze a randomized distributed scheduling algorithm proposed by Kesselheim and Vöcking, and show that it achieves \(O(\log n)\)-approximation, an improvement of a logarithmic factor. This matches the best ratio known for centralized algorithms and holds in arbitrary metric space and for every length-monotone and sublinear power assignment. We also show that every distributed algorithm uses \(\varOmega (\log n)\) slots to schedule certain instances that require only two slots, which implies that the best possible absolute performance guarantee is logarithmic.     

Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systems

We consider broadcasting in random d-regular graphs by using a simple modification of the random phone call model introduced by Karp et al. (Proceedings of the FOCS ’00, 2000). In the phone call model, in every time step, each node calls a randomly chosen neighbour to establish a communication channel to this node. The communication channels can then be used bi-directionally to transmit messages. We show that, if we allow every node to choose four distinct neighbours instead of one, then the average number of message transmissions per node required to broadcast a message efficiently decreases exponentially. Formally, we present an algorithm that has time complexity \(O(\log n)\) and uses \(O(n\log \log n)\) transmissions per message. In contrast, we show for the standard model that every distributed algorithm in a restricted address-oblivious model that broadcasts a message in time \(O(\log n)\) requires \(\Omega (n \log n{/} \log d)\) message transmissions. Our algorithm efficiently handles limited communication failures, only requires rough estimates of the number of nodes, and is robust against limited changes in the size of the network. Our results have applications in peer-to-peer networks and replicated databases.     

A Two-Grid Block-Centered Finite Difference Method for the Nonlinear Time-Fractional Parabolic Equation

In this article, a two-grid block-centered finite difference scheme is introduced and analyzed to solve the nonlinear time-fractional parabolic equation. This method is considered where the nonlinear problem is solved only on a coarse grid of size H and a linear problem is solved on a fine grid of size h. Stability results are proven rigorously. Error estimates are established on non-uniform rectangular grid which show that the discrete \(L^{\infty }(L^2)\) and \(L^2(H^1)\) errors are \(O(\triangle t^{2-\alpha }+h^2+H^3)\). Finally, some numerical experiments are presented to show the efficiency of the two-grid method and verify that the convergence rates are in agreement with the theoretical analysis.