Design and Analysis of an Acknowledgment-Aware Asynchronous MPR MAC Protocol for Distributed WLANs

Multi-packet reception (MPR) promises significant throughput gains in wireless local area networks (WLANs) by allowing nodes to transmit even in the presence of ongoing transmissions in the medium. However, the medium access control (MAC) layer must now be redesigned to facilitate rather than discourage - these overlapping transmissions. We investigate asynchronous MPR MAC protocols, which successfully accomplish this by controlling the node behavior based on the number of ongoing transmissions in the channel. The protocols use the backoff timer mechanism of the distributed coordination function, which makes them practically appealing. We first highlight a unique problem of acknowledgment delays, which arises in asynchronous MPR, and investigate a solution that modifies the medium access rules to reduce these delays and increase system throughput in the single receiver scenario. We develop a general renewal-theoretic fixed-point analysis that leads to expressions for the saturation throughput, packet dropping probability, and average head-of-line packet delay. We also model and analyze the practical scenario in which nodes may incorrectly estimate the number of ongoing transmissions.

Network flow-control using asynchronous stochastic approximation

We propose several stochastic approximation implementations for related algorithms in flow-control of communication networks. First, a discrete-time implementation of Kelly's primal flow-control algorithm is proposed. Convergence with probability 1 is shown, even in the presence of communication delays and stochastic effects seen in link congestion indications. This ensues from an analysis of the flow-control algorithm using the asynchronous stochastic approximation (ASA) framework. Two relevant enhancements are then pursued: a) an implementation of the primal algorithm using second-order information, and b) an implementation where edge-routers rectify misbehaving flows. Next, discretetime implementations of Kelly's dual algorithm and primaldual algorithm are proposed. Simulation results a) verifying the proposed algorithms and, b) comparing the stability properties are presented.

Asynchronous behaviour in some three-atom linear concerted radical-exchange reactions

A few simple three-atom thermoneutral radical exchange reactions (i.e. A + BC --> AB + C) are examined by ab initio SCF methods. Emphasis is laid on the detailed analysis of density matrices rather than on energetics. Results reveal that the sum of the bond orders of the breaking and forming bonds is not conserved to unity, due to development of free valence on the migrating atom 'B' in the transition state. Bond orders, free valence and spin densities on the atoms are calculated. The present analysis shows that the bond-cleavage process is always more advanced than the bond-formation process in the transition state. Further analysis shows a development of the negative spin density on the migrating atom 'B' in the transition state. The depletion of the alpha-spin density on the radical site "A" in the reactant during the reaction lags behind the growth of the alpha-spin density on the terminal atom "C" of the reactant bond, 'B-C' in the transition state. But all these processes are completed simultaneously at the end of the reaction. Hence, the reactions are asynchronous but kinetically concerted in most cases.

Study of voltage collapse at converter bus in asynchronous MTDC-AC systems

This paper presents the analysis and study of voltage collapse at any converter bus in an AC system interconnected by multiterminal DC (MTDC) links. The analysis is based on the use of the voltage sensitivity factor (VSF) as a voltage collapse proximity indicator (VCPI). In this paper the VSF is defined as a matrix which is applicable to MTDC systems. The VSF matrix is derived from the basic steady state equations of the converter, control, DC and AC networks. The structure of the matrix enables the derivation of some of the basic properties which are generally applicable. A detailed case study of a four-terminal MTDC system is presented to illustrate the effects of control strategies at the voltage setting terminal (VST) and other terminals. The controls considered are either constant angle, DC voltage, AC voltage, reactive current and reactive power at the VST and constant power or current at the other terminals. The effect of the strength of the AC system (measured by short circuit ratio) on the VSF is investigated. Several interesting and new results are presented. An analytical expression for the self VSF at VST is also derived for some specific cases which help to explain the number of transitions in VSF around the critical values of SCR.

Two-Dimensional Correlation Analysis of Temperature-Dependent FT-IR Spectra of Oleic Acid

In the present study, variable temperature FT-IR spectroscopic investigations were used to characterize the spectral changes in oleic acid during heating oleic acid in the temperature range from -30 degrees;C to 22 degrees C. In order to extract more information about the spectral variations taking place during the phase transition process, 2D correlation spectroscopy (2DCOS) was employed for the stretching (C?O) and rocking (CH2) band of oleic acid. However, the interpretation of these spectral variations in the FT-IR spectra is not straightforward, because the absorption bands are heavily overlapped and change due to two processes: recrystallization of the ?-phase and melting of the oleic acid. Furthermore, the solid phase transition from the ?- to the a-phase was also observed between -4 degrees C and -2 degrees C. Thus, for a more detailed 2DCOS analysis, we have split up the spectral data set in the subsets recorded between -30 degrees C to -16 degrees C, -16 degrees C to 10 degrees C, and 10 degrees C to 22 degrees C. In the corresponding synchronous and asynchronous 2D correlation plots, absorption bands that are characteristic of the crystalline and amorphous regions of oleic acid were separated.

Asynchronous Gossip for Averaging and Spectral Ranking

We consider two variants of the classical gossip algorithm. The first variant is a version of asynchronous stochastic approximation. We highlight a fundamental difficulty associated with the classical asynchronous gossip scheme, viz., that it may not converge to a desired average, and suggest an alternative scheme based on reinforcement learning that has guaranteed convergence to the desired average. We then discuss a potential application to a wireless network setting with simultaneous link activation constraints. The second variant is a gossip algorithm for distributed computation of the Perron-Frobenius eigenvector of a nonnegative matrix. While the first variant draws upon a reinforcement learning algorithm for an average cost controlled Markov decision problem, the second variant draws upon a reinforcement learning algorithm for risk-sensitive control. We then discuss potential applications of the second variant to ranking schemes, reputation networks, and principal component analysis.

Multithreaded Test Synthesis for Deadlock Detection

Designing and implementing thread-safe multithreaded libraries can be a daunting task as developers of these libraries need to ensure that their implementations are free from concurrency bugs, including deadlocks. The usual practice involves employing software testing and/or dynamic analysis to detect. deadlocks. Their effectiveness is dependent on well-designed multithreaded test cases. Unsurprisingly, developing multithreaded tests is significantly harder than developing sequential tests for obvious reasons. In this paper, we address the problem of automatically synthesizing multithreaded tests that can induce deadlocks. The key insight to our approach is that a subset of the properties observed when a deadlock manifests in a concurrent execution can also be observed in a single threaded execution. We design a novel, automatic, scalable and directed approach that identifies these properties and synthesizes a deadlock revealing multithreaded test. The input to our approach is the library implementation under consideration and the output is a set of deadlock revealing multithreaded tests. We have implemented our approach as part of a tool, named OMEN1. OMEN is able to synthesize multithreaded tests on many multithreaded Java libraries. Applying a dynamic deadlock detector on the execution of the synthesized tests results in the detection of a number of deadlocks, including 35 real deadlocks in classes documented as thread-safe. Moreover, our experimental results show that dynamic analysis on multithreaded tests that are either synthesized randomly or developed by third-party programmers are ineffective in detecting the deadlocks.

Trace Driven Dynamic Deadlock Detection and Reproduction

Dynamic analysis techniques have been proposed to detect potential deadlocks. Analyzing and comprehending each potential deadlock to determine whether the deadlock is feasible in a real execution requires significant programmer effort. Moreover, empirical evidence shows that existing analyses are quite imprecise. This imprecision of the analyses further void the manual effort invested in reasoning about non-existent defects. In this paper, we address the problems of imprecision of existing analyses and the subsequent manual effort necessary to reason about deadlocks. We propose a novel approach for deadlock detection by designing a dynamic analysis that intelligently leverages execution traces. To reduce the manual effort, we replay the program by making the execution follow a schedule derived based on the observed trace. For a real deadlock, its feasibility is automatically verified if the replay causes the execution to deadlock. We have implemented our approach as part of WOLF and have analyzed many large (upto 160KLoC) Java programs. Our experimental results show that we are able to identify 74% of the reported defects as true (or false) positives automatically leaving very few defects for manual analysis. The overhead of our approach is negligible making it a compelling tool for practical adoption.