Optimal Initialization and Gossiping Algorithms for Random Radio Networks

The initialization problem, also known as naming, consists to give a unique identifier ranging from 1 to n to a set of n indistinguishable nodes in a given network. We consider a network where n nodes (processors) are randomly deployed in a square (respectively, cube) X. We assume that the time is slotted and the network is synchronous, two nodes are able to communicate if they are within distance at most of r of each other (r is the transmitting/receiving range). Moreover, if two or more neighbors of a processor u transmit concurrently at the same time slot, then u would not receive either messages. We suppose also that the anonymous nodes know neither the topology of the network nor the number of nodes in the network. Under this extremal scenario, we first show how the transmitting range of the deployed processors affects the typical characteristics of the network. Then, by allowing the nodes to transmit at various ranges we design sublinear randomized initialization protocols: In the two, respectively, three, dimensional case, our randomized initialization algorithms run in O(n^1/2 log n^1/2), respectively, O(n^1/3 log n^2/3), time slots. These latter protocols are based upon an optimal gossiping algorithm which is of independent interest     

Deterministic Broadcast and Gossiping Algorithms for Ad hoc Networks

We present in this paper three deterministic broadcast and a gossiping algorithm suitable for ad hoc networks where topology changes range from infrequent to very frequent. The proposed algorithms are designed to work in networks where the mobile nodes possessing collision detection capabilities. Our first broadcast algorithm accomplishes broadcast in O(nlog n) for networks where topology changes are infrequent. We also present an O(nlog n) worst case time broadcast algorithms that is resilient to mobility. For networks where topology changes are frequent, we present a third algorithm that accomplishes broadcast in O(Δ·nlog n + n·|M|) in the worst case scenario, where |M| is the length of the message to be broadcasted and Δ the maximum node degree. We then extend one of our broadcast algorithms to develop an O(Dn log n + D²) algorithm for gossiping in the same network model.     

An O(n 1.5 ) Deterministic Gossiping Algorithm for Radio Networks

We consider the problem of distributed gossiping in radio networks of unknown topology. For radio networks of size n and diameter D , we present an adaptive deterministic gossiping algorithm of time O ($\sqrt{D}$ n+n log 2 n ) or O(n 1.5) . This algorithm is a tuned version of the fastest previously known gossiping algorithm due to Gasieniec and Lingas [1], and improves the time complexity by a poly-logarithmic factor.     

Periodic Merging Networks

We consider the problem of merging two sorted sequences on constant degree networks performing compare—exchange operations only. The classical solution to this problem is given by the networks based on Batcher's Odd—Even Merge and Bitonic Merge running in log(2n ) time. Due to the obvious log n lower bound for the runtime, this is time-optimal. We present a new family of merging networks working in a completely different way than the previously known algorithms. They have a novel property of being periodic: this means that for some (small) constant k , each processing unit of the network performs the same operations at steps t and t+k (as long as t+k does not exceed the runtime). The only operations executed are compare—exchange operations, just like in the case of Batcher's networks. The architecture of the networks is very simple and easy to lay out. We show that even for period 3 there is a network in our family merging two n -element sorted sequences in time O(log n ). Since each network of period 2 requires steps to merge such sequences, 3 is the smallest period for which we may achieve a fast runtime. In order to improve constants standing in front of log n we increment the period and tune the construction using additional techniques. We achieve the runtime 9 . . . log_3 n 5.7 . . . log n for a network of period 4, and 2.25 . . . ((k+3)/(k-1+log 3))log n 2.25 . . . log n for a network of period k+3 , for . Due to the periodic design, our networks have small area complexity. For instance, if each processing unit requires O(1) area and a comparator uses a single wire of width O(1) connecting the processing elements, then our networks require area. This compares well with Batcher's networks that require area . Received February 1997, and in revised form September 1997, and in final form February 1998.     

Gossiping on meshes and tori

Algorithms for performing gossiping on one- and higher-dimensional meshes are presented. As a routing model, the practically important wormhole routing is assumed. We especially focus on the trade-off between the start-up time and the transmission time. For one-dimensional arrays and rings, we give a novel lower bound and an asymptotically optimal gossiping algorithm for all choices of the parameters involved. For two-dimensional meshes and tori, a simple algorithm composed of one-dimensional phases is presented. For an important range of packet and mesh sizes, it gives clear improvements upon previously developed algorithms. The algorithm is analyzed theoretically and the achieved improvements are also convincingly demonstrated by simulations, as well as an implementation on the Paragon. On the Paragon, our algorithm even outperforms the gossiping routine provided in the NX message-passing library. For higher-dimensional meshes, we give algorithms which are based on an interesting generalization of the notion of a diagonal. These algorithms are analyzed theoretically, as well as by simulation     

Analysis of Closed Queuing Networks with Periodic Servers

A periodic network is a queuing network whose steady-state behavior is not constant in time, but repeats itself in a cycle. This behavior may be caused by the introduction of periodic servers, e.g., paging drums. The model presented is a generalization of some other models of queuing networks, and provides a more general definition of steady-state behavior. A theoretical solution is presented. Examples of theoretical and approximate solutions are presented for a well-known queuing network model of a computer system.     

Stability and Existence of Periodic Solutions of Periodic Cellular Neural Networks with Time-Vary Delays

By using the continuation theorem of Mawhins coincidence degree theory and constructing a suitable Lyapunov function, some new sufficient conditions are obtained ensuring existence and global asymptotical stability of periodic solution of cellular neural networks with periodic coefficients and delays, which do not require the activation functions to be differentiable and monotone nondecreasing. A numerical example is given to illustrate that the criteria are feasible. These results are helpful to design globally asymptotically stable and periodic oscillatory cellular neural networks.     

基于周期性无线网络数据传输的缓存管理技术研究

网络缓存管理是一种降低Internet流量和提高终端用户响应时间的网络技术。它来自于计算机和网络的其他领域,如目前流行的Intel架构的CPU中就存在缓存,用于提高内存存取的速度;各种操作系统在进行磁盘存取时也会利用缓存来提高速度;分布式文件系统通常也通过缓存来提高客户机和服务器之间的速度。无线网络数据的缓存可以在客户端,也可以在网络上,该文基于此,对周期性网络数据传输过程中的缓存管理技术进行了初步研究。     

Gossiping by processors prone to omission failures

We consider the gossip problem in a synchronous message-passing system. Participating processors are prone to omission failures, that is, a faulty processor may fail to send or receive a message. The gossip problem in the fault-tolerant setting is defined as follows: every correct processor must learn the initial value of any other processor, unless the other one is faulty; in the latter case either the initial value or the information about the fault must be learned. We develop two efficient algorithms that solve the gossip problem in time O(logn), where n is the number of processors in the system. The first one is an explicit algorithm (i.e., constructed in polynomial time) sending O(nlogn+f²) messages, and the second one reduces the message complexity to O(n+f²), where f is the upper bound on the number of faulty processors.     

Gossiping protocols for hybrid grid resource scheduling

Grid resource providers can use gossiping to disseminate their available resource state to remote regions of the grid to attract application load. Pairwise gossiping protocols exchange information about limited subsets of other resources between pairs of potentially remote participants. In epidemic gossiping protocols, the provider disseminates information to multiple neighbors, who in turn forward it to their neighbors, and so on. One important metric for these protocols is their coverage, which characterizes how many and which resources receive the information. Coverage characteristics of epidemic protocols are non-uniform, concentrated within the vicinity of a disseminating node; they can exhibit bi-modal behavior where information either reaches distant nodes or dies out quickly. Pairwise gossiping protocols, on the other hand, provide a more uniform coverage, but it can take longer for the dissemination to reach desired uniformity. In this paper, we study performance characteristics of three gossiping protocols: (1) epidemic gossiping, (2) pairwise gossiping, and (3) adaptive information dissemination (which is based on a form of epidemic gossiping). We report experimental results based on our simulation framework that compare the three protocols in terms of packet overhead and query satisfaction rates. We show that pairwise gossiping protocols work best when resource distribution on the grid is uniform, and that they can be configured to perform well in support of grid scheduling. We also verify this behavior under typical node failures of real-world production grids.     

Random Walks,Bisections and Gossiping in Circulant Graphs

Circulant graphs are regular graphs based on Cayley graphs defined on the Abelian group \(\mathbb{Z}_{n}\) . They are popular network topologies that arise in distributed computing. Using number theoretical tools, we first prove two main results for random directed k-regular circulant graphs with n vertices, when n is sufficiently large and k is fixed. First, for any fixed ε>0, n=p prime and L≥p ^1/k (logp)^1+1/k+ε , walks of length at most L terminate at every vertex with asymptotically the same probability. Second, for any n, there is a polynomial time algorithm that for almost all undirected 2r-regular circulant graphs finds a vertex bisector and an edge bisector, both of size less than n ^1?1/r+o(1). We then prove that the latter result also holds for all (rather than for almost all) 2r-regular circulant graphs with n=p, prime, vertices, while, in general, it does not hold for composite n. Using the bisection results, we provide lower bounds on the number of rounds required by any gossiping algorithms for any n. We introduce generic distributed algorithms to solve the gossip problem in any circulant graphs. We illustrate the efficiency of these algorithms by giving nearly matching upper bounds of the number of rounds required by these algorithms in the vertex-disjoint and the edge-disjoint paths communication models in particular circulant graphs.     

On the Weighted Pseudo-Almost Periodic Solution for BAM Networks with Delays

In this paper, a class of Bidirectional Associative Memory neural networks with time-varying weights and continuously distributed delays is discussed. Sufficient conditions are obtained for the existence and uniqueness of weighted pseudo-almost periodic solution of the considered model and numerical examples are given to show the effectiveness of the obtained results.     

Novel Sufficient Conditions on Periodic Solutions for Discrete-Time Neutral-Type Neural Networks

Neural Processing Letters - In this paper, we consider the existence and global exponential stability of periodic solutions for a class of delayed discrete-time neutral-type neural networks. Novel...     

Weighted Pseudo Almost Periodic Shunting Inhibitory Cellular Neural Networks with Multi-proportional Delays

Neural Processing Letters - In this present paper, the dynamics of weighted pseudo almost periodic shunting inhibitory cellular neural networks with multi-proportional delays is concerned. By...     

On the Almost Periodic Solution of Cellular Neural Networks With Distributed Delays

By exponential dichotomy about differential equations, a formal almost periodic solution (APS) of a class of cellular neural networks (CNNs) with distributed delays is obtained. Then, within different normed spaces, several sufficient conditions guaranteeing the existence and uniqueness of an APS are proposed using two fixed-point theorems. Based on the continuity property and some inequality techniques, two theorems insuring the global stability of the unique APS are given. Comparing with known literatures, all conclusions are drawn with slacker restrictions, e.g., do not require the integral of the kernel function determining the distributed delays from zero to positive infinity to be one, and the activation functions to be bounded, etc.; besides, all criteria are obtained by different ways. Finally, two illustrative examples show the validity and that all criteria are easy to check and apply     

Synchronization of a Class of Improved Neural Networks Based on Periodic Intermittent Control

In this paper, the synchronization of a class of improved neural networks with variable time delay is concerned via intermittent control. Firstly, a class of modified delayed neural networks is introduced, in which communication delays between different neurons are considered and the intra-neuron delays are negligible. Secondly, using Lyapunov functional theory, inequality techniques, and multi-parameter method, the synchronization criteria are established based on p-norm via intermittent control, and a feasible synchronization control region is given. Besides, by means of the component analysis method, the reduction to absurdity, mathematical induction, the exponential synchronization of the addressed networks is discussed in terms of the infinite norm, some criteria and the feasible control region of synchronization are also derived. Finally, some numerical examples are provided to show the validity and effectiveness of the theoretical results.     

Pseudo Almost Periodic Solutions for High-Order Hopfield Neural Networks with Time-Varying Leakage Delays

In this paper, high-order Hopfield neural networks with time-varying leakage delays are investigated. By applying Lyapunov functional method and differential inequality techniques, a set of sufficient conditions are obtained for the existence and exponential stability of pseudo almost periodic solutions of the model. Some simulations are carried out to support the theoretical findings. Our results improve and generalize those of the previous studies.