Experiences with large-scale operational trials of ALTO-enhanced P2P filesharing in an intra-ISP scenario

Application Layer Traffic Optimization (ALTO) has recently gained attention in the research and standardisation community as a way for a network operator to guide the peer selection process of distributed applications by providing network layer topology information. In particular P2P applications are expected to gain from ALTO, due to the many connections peers form among each other, often without taking network layer topology information into account. In this paper, we present results of an extensive intra-ISP trial with an ALTO-enhanced P2P filesharing software. In summary, our results show that—depending on the concrete setting and on the distribution of upload capacity in the network—ALTO enables an ISP to save operational costs significantly while not degrading application layer performance noticeably. In addition, based on our experience we are able to give advice to operators on how to save costs with ALTO while not sacrificing application layer performance at all.     

Deciding k-Colorability of P 5-Free Graphs in Polynomial Time

The problem of computing the chromatic number of a P ₅-free graph (a graph which contains no path on 5 vertices as an induced subgraph) is known to be NP-hard. However, we show that for every fixed integer k, there exists a polynomial-time algorithm determining whether or not a P ₅-free graph admits a k-coloring, and finding one, if it does.     

Is Evolution Algorithmic?

In Darwin’s Dangerous Idea, Daniel Dennett claims that evolution is algorithmic. On Dennett’s analysis, evolutionary processes are trivially algorithmic because he assumes that all natural processes are algorithmic. I will argue that there are more robust ways to understand algorithmic processes that make the claim that evolution is algorithmic empirical and not conceptual. While laws of nature can be seen as compression algorithms of information about the world, it does not follow logically that they are implemented as algorithms by physical processes. For that to be true, the processes have to be part of computational systems. The basic difference between mere simulation and real computing is having proper causal structure. I will show what kind of requirements this poses for natural evolutionary processes if they are to be computational.     

Application of the OBD method for optimization of neural state variable estimators of the two-mass drive system

This paper presents neural estimators of the mechanical state variables of the electrical drive system with elastic joints. The non-measurable state variables, as the torsional torque and the load machine speed are estimated using multilayer feed-forward neural networks. The main stages of the design methodology of these neural estimators are presented. The optimal brain damage method is implemented for the structure optimization of each neural network. Then signals estimated by neural estimators are tested in the electrical drive control structure with additional feedbacks from the estimated shaft torque and the difference between the motor and the load speeds. The simulation results show good accuracy of both presented neural estimators for the wide range of changes of the reference speed and the load torque. The simulation results are then verified by laboratory experiments.     

Randomized mutual exclusion on a multiple access channel

In this paper we consider the mutual exclusion problem on a multiple access channel. Mutual exclusion is one of the fundamental problems in distributed computing. In the classic version of this problem, n processes execute a concurrent program that occasionally triggers some of them to use shared resources, such as memory, communication channel, device, etc. The goal is to design a distributed algorithm to control entries and exits to/from the shared resource (also called a critical section), in such a way that at any time, there is at most one process accessing it. In our considerations, the shared resource is the shared communication channel itself (multiple access channel), and the main challenge arises because the channel is also the only mean of communication between these processes. We consider both the classic and a slightly weaker version of mutual exclusion, called \(\varepsilon \)-mutual-exclusion, where for each period of a process staying in the critical section the probability that there is some other process in the critical section is at most \(\varepsilon \). We show that there are channel settings, where the classic mutual exclusion is not feasible even for randomized algorithms, while the \(\varepsilon \)-mutual-exclusion is. In more relaxed channel settings, we prove an exponential gap between the makespan complexity of the classic mutual exclusion problem and its weaker \(\varepsilon \)-exclusion version. We also show how to guarantee fairness of mutual exclusion algorithms, i.e., that each process that wants to enter the critical section will eventually succeed.     

A Chamber for Testing the Release of Volatile Substances Secreted by Animals,Especially Mammals,as Exemplified by Substances Released by Rats in Response to Stress

Abstract

The success of the testing of volatile organic compounds emitted by animals is dependent on the creation of appropriate conditions for air sampling subsequently used to assay and identify the compounds. These conditions play a particularly important role in the investigation of pheromones, which are secreted in extremely low concentrations. The authors have not come across any previous work which offers constructional solutions, which would allow avoidance of contamination of the air samples containing volatile substances secreted by animals.

A constructional solution was developed, which provides optimal conditions for their sampling and isolation. Its main advantages are as follows: the exposure chamber (the chamber in which the animal is studied) is filled with synthetic air; the exposure chamber is separated from the atmospheric air with a synthetic air “jacket”; the exposure chamber has been constructed using materials which do not release chemicals and absorb them in trace quantities.     

Finding Induced Paths of Given Parity in Claw-Free Graphs

The Parity Path problem is to decide if a given graph contains both an induced path of odd length and an induced path of even length between two specified vertices. In the related problems Odd Induced Path and Even Induced Path, the goal is to determine whether an induced path of odd, respectively even, length between two specified vertices exists. Although all three problems are NP-complete in general, we show that they can be solved in $\mathcal{O}(n^{5})$ time for the class of claw-free graphs. Two vertices s and t form an even pair in G if every induced path from s to t in G has even length. Our results imply that the problem of deciding if two specified vertices of a claw-free graph form an even pair, as well as the problem of deciding if a given claw-free graph has an even pair, can be solved in $\mathcal{O}(n^{5})$ time and $\mathcal{O}(n^{7})$ time, respectively. We also show that we can decide in $\mathcal{O}(n^{7})$ time whether a claw-free graph has an induced cycle of given parity through a specified vertex. Finally, we show that a shortest induced path of given parity between two specified vertices of a claw-free perfect graph can be found in $\mathcal {O}(n^{7})$ time.