The Price of Anarchy in Network Creation Games Is (Mostly) Constant

We study the price of anarchy and the structure of equilibria in network creation games. A network creation game is played by n players {1,2,…,n}, each identified with a vertex of a graph (network), where the strategy of player i, i=1,…,n, is to build some edges adjacent to i. The cost of building an edge is α>0, a fixed parameter of the game. The goal of every player is to minimize its creation cost plus its usage cost. The creation cost of player i is α times the number of built edges. In the SumGame variant, the usage cost of player i is the sum of distances from i to every node of the resulting graph. In the MaxGame variant, the usage cost is the eccentricity of i in the resulting graph of the game. In this paper we improve previously known bounds on the price of anarchy of the game (of both variants) for various ranges of α, and give new insights into the structure of equilibria for various values of α. The two main results of the paper show that for α>273?n all equilibria in SumGame are trees and thus the price of anarchy is constant, and that for α>129 all equilibria in MaxGame are trees and the price of anarchy is constant. For SumGame this answers (almost completely) one of the fundamental open problems in the field—is price of anarchy of the network creation game constant for all values of α?—in an affirmative way, up to a tiny range of α.     

Variable Structure Control with chattering elimination and guaranteed stability for a generalized T-S model

In this paper, a fuzzy based Variable Structure Control (VSC) with guaranteed stability is presented. The main objective is to obtain an improved performance of highly non-linear unstable systems. The main contribution of this work is that, firstly, new functions for chattering reduction and error convergence without sacrificing invariant properties are proposed, which is considered the main drawback of the VSC control. Secondly, the global stability of the controlled system is guaranteed.The well known weighting parameters approach, is used in this paper to optimize local and global approximation and modeling capability of T-S fuzzy model.A one link robot is chosen as a nonlinear unstable system to evaluate the robustness, effectiveness and remarkable performance of optimization approach and the high accuracy obtained in approximating nonlinear systems in comparison with the original T-S model. Simulation results indicate the potential and generality of the algorithm. The application of the proposed FLC-VSC shows that both alleviation of chattering and robust performance are achieved with the proposed FLC-VSC controller. The effectiveness of the proposed controller is proven infront of disturbances and noise effects.     

Integrating job parallelism in real-time scheduling theory

We investigate the global scheduling of sporadic, implicit deadline, real-time task systems on multiprocessor platforms. We provide a task model which integrates job parallelism. We prove that the time-complexity of the feasibility problem of these systems is linear relatively to the number of (sporadic) tasks for a fixed number of processors. We propose a scheduling algorithm theoretically optimal (i.e., preemptions and migrations neglected). Moreover, we provide an exact feasibility utilization bound. Lastly, we propose a technique to limit the number of migrations and preemptions.     

LEGClust—A Clustering Algorithm Based on Layered Entropic Subgraphs

Hierarchical clustering is a stepwise clustering method usually based on proximity measures between objects or sets of objects from a given data set. The most common proximity measures are distance measures. The derived proximity matrices can be used to build graphs, which provide the basic structure for some clustering methods. We present here a new proximity matrix based on an entropic measure and also a clustering algorithm (LEGCIust) that builds layers of subgraphs based on this matrix and uses them and a hierarchical agglomerative clustering technique to form the clusters. Our approach capitalizes on both a graph structure and a hierarchical construction. Moreover, by using entropy as a proximity measure, we are able, with no assumption about the cluster shapes, to capture the local structure of the data, forcing the clustering method to reflect this structure. We present several experiments on artificial and real data sets that provide evidence on the superior performance of this new algorithm when compared with competing ones.     

LEGClust- a clustering algorithm based on layered entropic subgraphs.

Hierarchical clustering is a stepwise clustering method usually based on proximity measures between objects or sets of objects from a given data set. The most common proximity measures are distance measures. The derived proximity matrices can be used to build graphs, which provide the basic structure for some clustering methods. We present here a new proximity matrix based on an entropic measure and also a clustering algorithm (LEGClust) that builds layers of subgraphs based on this matrix, and uses them and a hierarchical agglomerative clustering technique to form the clusters. Our approach capitalizes on both a graph structure and a hierarchical construction. Moreover, by using entropy as a proximity measure we are able, with no assumption about the cluster shapes, to capture the local structure of the data, forcing the clustering method to reflect this structure. We present several experiments on artificial and real data sets that provide evidence on the superior performance of this new algorithm when compared with competing ones.     

Synthesis of symmetric and asymmetric singly terminated elliptic ladder filters for multiplexing applications

An extension of the Cauer ladder development for synthesizing singly terminated filters with symmetric and asymmetric responses is presented. Basically, a driving‐point immittance including reactive constant elements is carried out in such a way that provides the transmission zeros. The reactive constant elements are introduced into the synthesis for two reasons. The first is to consider the possibility of the asymmetric position of transmission zeros in the real frequency axis. The second one is to obtain canonical forms, i.e. networks with the minimum number of elements in the case of symmetrical responses. To validate the proposed method, a filter with asymmetrical response has been synthesized, comparing different topologies for its use in multiplexers. This fact is illustrated with a Ku‐band elliptic response diplexer designed in H‐plane rectangular waveguide. © 2009 Wiley Periodicals, Inc. Int J RF and Microwave CAE, 2009.     

Improving SCTP retransmission delays for time-dependent thin streams

A large number of network services rely on IP and reliable transport protocols. For applications that provide abundant data for transmission, loss is usually handled satisfactorily, even if the application is latency-sensitive (Wang et al. 2004). For data streams where small packets are sent intermittently, however, applications can occasionally experience extreme latencies (Griwodz and Halvorsen 2006). As it is not uncommon that such thin-stream applications are time-dependent, any unnecessarily induced delay can have severe consequences for the service provided. Massively Multiplayer Online Games (MMOGs) are a defining example of thin streams. Many MMOGs (like World of Warcraft and Age of Conan) use TCP for the benefits of reliability, in-order delivery and NAT/firewall traversal. It has been shown that TCP has several shortcomings with respect to the latency requirements of thin streams because of the way it handles retransmissions (Griwodz and Halvorsen 2006). As such, an alternative to TCP may be SCTP (Stewart et al. 2000), which was originally developed to meet the requirements of signaling transport. In this paper, we evaluate the Linux-kernel SCTP implementation in the context of thin streams. To address the identified latency challenges, we propose sender-side only enhancements that reduce the application-layer latency in a manner that is compatible with unmodified receivers. These enhancements can be switched on by applications and are used only when the system identifies the stream as thin. To evaluate the latency performance, we have performed several tests over various real networks and over an emulated network, varying parameters like RTT, packet loss and amount of competing cross traffic. When comparing our modifications with SCTP on Linux and FreeBSD and TCP New Reno, our results show great latency improvements and indicate the need for a separate handling of thin and thick streams.     

Testing from a stochastic timed system with a fault model

In this paper we present a method for testing a system against a non-deterministic stochastic finite state machine. As usual, we assume that the functional behaviour of the system under test (SUT) is deterministic but we allow the timing to be non-deterministic. We extend the state counting method of deriving tests, adapting it to the presence of temporal requirements represented by means of random variables. The notion of conformance is introduced using an implementation relation considering temporal aspects and the limitations imposed by a black-box framework. We propose a new group of implementation relations and an algorithm for generating a test suite that determines the conformance of a deterministic SUT with respect to a non-deterministic specification. We show how previous work on testing from stochastic systems can be encoded into the framework presented in this paper as an instantiation of our parameterized implementation relation. In this setting, we use a notion of conformance up to a given confidence level.     

The δ-Al2O3 (Saffil) fibre degradation during infiltration with MgLi alloy

The chemical and phase transformations of -Al₂O₃ (Saffil) fibres during their infiltration with Mg-8 wt% Li were studied by scanning and transmission electron microscopy, Auger electron spectroscopy, secondary ion mass spectrometry and X-ray diffraction methods. The infiltration experiments were carried out in autoclave under argon pressure at temperatures of 883–908 K and contact times of 4–30 s as well as at 918 K/420 s. During the course of infiltration, lithium penetrates the Saffil fibres and this process is accompanied by the gradual transformation of the tetragonal -Al₂O₃ lattice towards the cubic spinel LiAl₅O₈ compound, where part of the Li⁺ ions is probably substituted by Mg²⁺ No remarkable interfacial zone at the fibre/matrix interface was observed; however, the Saffil fibres became brittle which had been manifested by the occurrence of fragmentation on the metallographically treated fibre cross-sections. The tensile strength (maximum 220 MPa) of the corresponding metal matrix composite clearly decreased with increased infiltration time.