Maximal selection in tandem networks with symmetric hearing range

We consider an infinite tandem network in which every node is capable of hearing its neighbors up to a given distancen. At any moment of time every node may contain in the top of its queue a message destined to one of its neighbors. This network can be used as a model for a microwave or optic link with many users. For small and largen we investigate the maximal selection of nodes in the network, for which their transmissions are collision-free. For a large hearing range we show that the upper bound on the maximal selection, which is found herein, is asymptotically achievable. For small hearing ranges we show that a greedy selection is better but not asymptotically optimal. We also specify a sequence of upper bounds which converge to the maximal throughput.This research was done while J. M. Jaffe was on leave at the IBM Israel Scientific Center.     

Maximal throughput in a tandem multi-hop radio network

We consider an infinite slotted tandem multi-hop network in which every node is capable of hearing only its two neighbors. The destinations of the packets in the front of the various nodes are independent and independently resampled at each slot whether or not the given node was permitted to transmit. Under the following set of permissible access protocols, the maximal node utilization of the network is derived: At the beginning of every slot, each of the nodes may transmit the first packet in its queue; the nodes can coordinate their transmissions at no cost and make use of the destination of the first packet at each queue. The transmission scheme that attains the maximum is also specified.     

Highly reliable symmetric networks

We generalize directed loop networks to loop-symmetric networks in which there are N nodes and in which each node has in-degree and out-degree k, subject to the condition that 2^k does not exceed N. We show that by proper selection of links one can obtain generalized loop networks with optimal or close to optimal diameter and connectivity. The optimized diameter is less than k[N¹k/], where [x] indicates the ceiling of x. We also show that these networks are rather compact in that the diameter is not more than twice the average distance. Roughly 1/2(k-1)N¹k/ nodes can be removed such that the network of remaining nodes is still strongly connected, if all remaining nodes have at least one incoming and one outgoing link left     

Efficient searchable symmetric encryption supporting range queries

International Journal of Information Security - The demand for cloud storage services continuously increases putting at risk the privacy of the outsourced data. Data encryption is the obvious...     

Maximal prime subgraph decomposition of Bayesian networks

The authors present a method for decomposition of Bayesian networks into their maximal prime subgraphs. The correctness of the method is proven and results relating the maximal prime subgraph decomposition (MPD) to the maximal complete subgraphs of the moral graph of the original Bayesian network are presented. The maximal prime subgraphs of a Bayesian network can be organized as a tree which can be used as the computational structure for LAZY propagation. We also identify a number of tasks performed on Bayesian networks that can benefit from MPD. These tasks are: divide and conquer triangulation, hybrid propagation algorithms combining exact and approximative inference techniques, and incremental construction of junction trees. We compare the proposed algorithm with standard algorithms for decomposition of undirected graphs into their maximal prime subgraphs. The discussion shows that the proposed algorithm is simpler, more easy to comprehend, and it has the same complexity as the standard algorithms.     

Decomposition of general tandem queueing networks with MMPP input

For tandem queueing networks with generally distributed service times, decomposition often is the only feasible solution method besides simulation. The network is partitioned into individual nodes which are analyzed in isolation. In most existing decomposition algorithms for continuous-time networks, the output of a queue is usually approximated as a renewal process, which becomes the arrival process to the next queue. In this paper, the internal traffic processes are described as semi-Markov processes (SMPs) and Markov modulated Poisson processes (MMPPs). Thus, correlations in the traffic streams, which are known to have a considerable impact on performance, are taken into account to some extent. A two-state MMPP, which arises frequently in communications modeling, serves as input to the first queue of the tandem network. Furthermore, the single nodes may have infinite or finite buffers. Customers who arrive at a full buffer will get lost.

In principle, the analysis of an individual queue as an MMPP/G/1(/K) system delivers a wide range of performance measures. For different examples of tandem networks, stationary mean queue lengths at arbitrary time are compared to simulation data. The relative errors of the results, which are computed promptly by the decomposition component of the tool TimeNET, remain within a reasonable range.     

Permitted and forbidden sets in symmetric threshold-linear networks

The richness and complexity of recurrent cortical circuits is an inexhaustible source of inspiration for thinking about high-level biological computation. In past theoretical studies, constraints on the synaptic connection patterns of threshold-linear networks were found that guaranteed bounded network dynamics, convergence to attractive fixed points, and multistability, all fundamental aspects of cortical information processing. However, these conditions were only sufficient, and it remained unclear which were the minimal (necessary) conditions for convergence and multistability. We show that symmetric threshold-linear networks converge to a set of attractive fixed points if and only if the network matrix is copositive. Furthermore, the set of attractive fixed points is nonconnected (the network is multiattractive) if and only if the network matrix is not positive semidefinite. There are permitted sets of neurons that can be coactive at a stable steady state and forbidden sets that cannot. Permitted sets are clustered in the sense that subsets of permitted sets are permitted and supersets of forbidden sets are forbidden. By viewing permitted sets as memories stored in the synaptic connections, we provide a formulation of long-term memory that is more general than the traditional perspective of fixed-point attractor networks. There is a close correspondence between threshold-linear networks and networks defined by the generalized Lotka-Volterra equations.     

Path selection in multi-layer networks

Multi-layer networks are computer networks where the configuration of the network can be changed dynamically at multiple layers. However, in practice, technologies at different layers may be incompatible to each other, which necessitates a careful choice of a multi-layer network model. Not much work has been done on path selection in multi-layer networks. In this paper, we describe how to represent a multi-layer network and we provide algorithms for selecting paths in them. Throughout the paper we will use examples drawn from practical experience with routing in hybrid optical networks.     

Parameterized synthesis of self-stabilizing protocols in symmetric networks

Self-stabilization in distributed systems is a technique to guarantee convergence to a set of legitimate states without external intervention when a transient fault or bad initialization occurs. Recently, there has been a surge of efforts in designing techniques for automated synthesis of self-stabilizing algorithms that are correct by construction. Most of these techniques, however, are not parameterized, meaning that they can only synthesize a solution for a fixed and predetermined number of processes. In this paper, we report a breakthrough in parameterized synthesis of self-stabilizing algorithms in symmetric networks, including ring, line, mesh, and torus. First, we develop cutoffs that guarantee (1) closure in legitimate states, and (2) deadlock-freedom outside the legitimate states. We also develop a sufficient condition for convergence in self-stabilizing systems. Since some of our cutoffs grow with the size of the local state space of processes, scalability of the synthesis procedure is still a problem. We address this problem by introducing a novel SMT-based technique for counterexample-guided synthesis of self-stabilizing algorithms in symmetric networks. We have fully implemented our technique and successfully synthesized solutions to maximal matching, three coloring, and maximal independent set problems for ring and line topologies.     

一种基于对称加密的范围数据查询算法

为了弥补保序加密算法的隐私泄漏问题,结合对称可搜索加密技术基本思想,提出一种新型的具有隐私保护功能的范围数据加密查询算法.在该算法中,将数字范围转换为特殊关键字并放入布隆过滤器进行存储与命中判定,其中密文信息仅与值域相关,与具体数据无关,从而保证了语义安全性.实验结果表明,该算法计算负载仅为线性增长.综合而言,该算法具有更高的安全性与良好的运行效率.     

Delay optimal coteries on regular symmetric networks

Coteries, introduced by Garcia-Molina and Barbara [Journal for the Association for Computing Machinery, 32 (4) (1985) 841], are an important and effective tool for enforcing mutual exclusion in distributed systems. Communication delay is an important performance measure for a coterie. Fu et al. [IEEE Transactions on Parallel and Distributed Systems, 8 (1) (1997) 59] emphasize that while calculating communication delay, the actual distances between different sites in a network must be taken into account and using this idea, obtain delay optimal coteries for trees, rings and hypercubes. Also, topology of an interconnection network plays an important role in the performance of a distributed system. For certain applications, it is desirable that the degree of each node in the interconnection network is the same. Constant Degree Four Cayley Graphs introduced by Vadapalli and Srimani [IEEE Transactions on Parallel and Distributed Systems 7(2) (1996) 26] provide an ideal topology for such applications. They are regular, have a logarithmic diameter and a node connectivity of four. In this paper, we prove that no coterie on an arbitrary network can have a delay of less than half the diameter of the network and use this result to obtain delay optimal coteries on regular symmetric networks with special reference to constant degree four Cayley interconnection-network.     

Advances in evolutionary feature selection neural networks with co-evolution learning

Training neural networks is a complex task provided that many algorithms are combined to find best solutions to the classification problem. In this work, we point out the evolutionary computing to minimize a neural configuration. For this purpose, a distribution estimation framework is performed to select relevant features, which lead to classification accuracy with a lower complexity in computational time. Primarily, a pruning strategy-based score function is applied to decide the network relevance in the genetic population. Since the complexity of the network (connections, weights, and biases) is most important, the cooling state of the system will strongly relate to the entropy as a minimization function to reach the desired solution. Also, the framework proposes coevolution learning (with discrete and continuous representations) to improve the behavior of the evolutionary neural learning. The results obtained after simulations show that the proposed work is a promising way to extend its usability to other classes of neural networks.     

限定记忆的前向神经网络在线学习算法研究

从理论上分析了隐含层激励函数满足Mercer条件的前向神经网络的数学本质,给出了网络学习的指导方向.提出3种网络在线学习算法,它们通过动态调整网络结构和权值来提高网络在线预测性能.算法完全符合统计学习理论提出的结构风险最小化原则,具有较快的学习收敛速度和良好的抗噪声能力.最后通过具体数值实验验证了上述算法的可行性和优越性.     

On the computational efficiency of symmetric neural networks

An open problem concerning the computational power of neural networks with symmetric weights is solved. It is shown that these networks possess the same computational power as general networks with asymmetric weights; i.e., these networks can compute any recursive function. The computations of these networks can be described as a minimmization process of a certain energy function; it is shown that for uninitialized symmetric neural networks this process presents a Σ₂-complete problem.     

Performance analysis for range expansion in heterogeneous networks

In this paper, the uplink and downlink performance of a two-tier heterogeneous network （HetNet） with range expansion （RE） is analyzed. Different from previous works, base stations （BSs） are modeled as a spatial Poisson point process. This model can not only capture the irregularity of the BS deployment but also lead to closed form expressions. With the analytical results, the impacts of several key parameters on the coverage and throughput performance are investigated. Our results justifies the effectiveness of RE and Pico deployment. Based on our analyses, certain attention should be made on the RE design to balance the uplink and downlink performance. Our analyses are corroborated by simulations and can thus serve as a flexible and quick guidance for system design without complicated and time-consuming system-level platform construction and simulation.     

Packet-switched network selection with the highest QoS in 4G networks

The evolution of telecommunications during the last decades has been enormous and as a result, nowadays, people find themselves before the challenge of 4G networks. Due to the fact that the latter constitute an environment of heterogeneous networks, their integration in terms of the Quality of Service (QoS) offered is of crucial importance. In general, the topic of this paper is to integrate the parameters that define QoS. Specifically, the main scope of this paper is the development of a process to evaluate three packet-switched networks (UMTS, WLAN and GPRS) in reference to the QoS offered and finally, the selection of the network that offers the highest standard for QoS. In order to achieve the above goal, there has been an attempt to distinguish the most important QoS indicators that characterize packet-switched networks and a few processes have been developed in order to either estimate the contribution of each parameter to the total QoS, or identify the weak points of a network. Apparently, each of these processes approaches the term of QoS in a different way and gives results of different usefulness.     

Portfolio selection using neural networks

In this paper we apply a heuristic method based on artificial neural networks (NN) in order to trace out the efficient frontier associated to the portfolio selection problem. We consider a generalization of the standard Markowitz mean-variance model which includes cardinality and bounding constraints. These constraints ensure the investment in a given number of different assets and limit the amount of capital to be invested in each asset. We present some experimental results obtained with the NN heuristic and we compare them to those obtained with three previous heuristic methods. The portfolio selection problem is an instance from the family of quadratic programming problems when the standard Markowitz mean-variance model is considered. But if this model is generalized to include cardinality and bounding constraints, then the portfolio selection problem becomes a mixed quadratic and integer programming problem. When considering the latter model, there is not any exact algorithm able to solve the portfolio selection problem in an efficient way. The use of heuristic algorithms in this case is imperative. In the past some heuristic methods based mainly on evolutionary algorithms, tabu search and simulated annealing have been developed. The purpose of this paper is to consider a particular neural network (NN) model, the Hopfield network, which has been used to solve some other optimisation problems and apply it here to the portfolio selection problem, comparing the new results to those obtained with previous heuristic algorithms.     

Best routes selection in international intermodal networks

This study focuses on one of the intermodal operational issues: how to select best routes for shipments through the international intermodal network. International intermodal routing is complicated by three important characteristics: (1) multiple objectives; (2) scheduled transportation modes and demanded delivery times; and (3) transportation economies of scale. In this paper, the international intermodal routing problem is formulated as a multiobjective multimodal multicommodity flow problem (MMMFP) with time windows and concave costs. The objectives of this paper are to develop a mathematical model encompassing all three essential characteristics, and to propose an algorithm that can effectively provide answers to the model. The problem is NP-hard. It follows that the proposed algorithm is a heuristic. Based on relaxation and decomposition techniques, the original problem is broken into a set of smaller and easier subproblems. The case studies show that it is important to incorporate the three characteristics into the international intermodal routing problem, and our proposed algorithm can effectively and efficiently solve the MMMFP with time windows and concave costs.     

Data-independent vantage point selection for range queries

The Journal of Supercomputing - Vantage point-based indexing is a popular technique for implementing range queries in main memory database. Vantage points are reference points that are used to...