OpenRaiser/Intern-Atlas huggingface dataset:
A Dual Digraph Approach for Leaderless Atomic Broadcast (Extended Version)
Venue: arXiv cs.DC 2019
Year: 2019

Many distributed systems work on a common shared state; in such systems, distributed agreement is necessary for consistency. With an increasing number of servers, these systems become more susceptible to single-server failures, increasing the relevance of fault-tolerance. Atomic broadcast enables fault-tolerant distributed agreement, yet it is costly to solve. Most practical algorithms entail linear work per broadcast message. AllConcur -- a leaderless approach -- reduces the work, by connecting the servers via a sparse resilient overlay network; yet, this resiliency entails redundancy, limiting the reduction of work. In this paper, we propose AllConcur+, an atomic broadcast algorithm that lifts this limitation: During intervals with no failures, it achieves minimal work by using a redundancy-free overlay network. When failures do occur, it automatically recovers by switching to a resilient overlay network. In our performance evaluation of non-failure scenarios, AllConcur+ achieves comparable throughput to AllGather -- a non-fault-tolerant distributed agreement algorithm -- and outperforms AllConcur, LCR and Libpaxos both in terms of throughput and latency. Furthermore, our evaluation of failure scenarios shows that AllConcur+'s expected performance is robust with regard to occasional failures. Thus, for realistic use cases, leveraging redundancy-free distributed agreement during intervals with no failures improves performance significantly.
Cache-Aided Interference Management in Partially Connected Linear Networks
Venue: arXiv cs.IT 2019
Year: 2019

This paper studies caching in (K+L-1) x K partially connected wireless linear networks, where each of the K receivers locally communicates with L out of the K+L-1 transmitters, and caches are at all nodes. The goal is to design caching and delivery schemes to reduce the transmission latency, by using normalized delivery time (NDT) as the performance metric. For small transmitter cache size (any L transmitters can collectively store the database just once), we propose a cyclic caching strategy so that each of every L consecutive transmitters caches a distinct part of each file; the delivery strategy exploits coded multicasting and interference alignment by introducing virtual receivers. The obtained NDT is within a multiplicative gap of 2 to the optimum in the entire cache size region, and optimal in certain region. For large transmitter cache size (any L transmitters can collectively store the database for multiple copies), we propose a modified caching strategy so that every bit is repeatedly cached at consecutive transmitters; the delivery strategy exploits self-interference cancellation and interference neutralization. By combining these schemes, the NDT is optimal in a larger region. We also extend our results to linear networks with heterogeneous receiver connectivity and partially connected circular networks.
Disintegration and Bayesian Inversion via String Diagrams
Venue: arXiv cs.AI 2019
Year: 2019

The notions of disintegration and Bayesian inversion are fundamental in conditional probability theory. They produce channels, as conditional probabilities, from a joint state, or from an already given channel (in opposite direction). These notions exist in the literature, in concrete situations, but are presented here in abstract graphical formulations. The resulting abstract descriptions are used for proving basic results in conditional probability theory. The existence of disintegration and Bayesian inversion is discussed for discrete probability, and also for measure-theoretic probability --- via standard Borel spaces and via likelihoods. Finally, the usefulness of disintegration and Bayesian inversion is illustrated in several examples.
Formalized Risk Assessment for Safety and Security
Venue: arXiv cs.SY 2019
Year: 2019

The manifold interactions between safety and security aspects makes it plausible to handle safety and security risks in an unified way. The paper develops a corresponding approach based on the discrete event systems (DEVS) paradigm. The simulation-based calculation of an individual system evolution path provides the contribution of this special path of dynamics to the overall risk of running the system. Accidentally and intentionally caused failures are distinguished by the way, in which the risk contributions of the various evolution paths are aggregated to the overall risk. The consistency of the proposed risk assessment method with 'traditional' notions of risk shows its plausibility. Its non-computability, on the other hand, makes the proposed risk assessment better suitable to the IT security domain than other concepts of risk developed for both safety and security. Power grids are discussed as an application example and demonstrates some of the advantages of the proposed method.
A Survey of Indoor Localization Systems and Technologies
Venue: arXiv cs.NI 2019
Year: 2019

Indoor localization has recently witnessed an increase in interest, due to the potential wide range of services it can provide by leveraging Internet of Things (IoT), and ubiquitous connectivity. Different techniques, wireless technologies and mechanisms have been proposed in the literature to provide indoor localization services in order to improve the services provided to the users. However, there is a lack of an up-to-date survey paper that incorporates some of the recently proposed accurate and reliable localization systems. In this paper, we aim to provide a detailed survey of different indoor localization techniques such as Angle of Arrival (AoA), Time of Flight (ToF), Return Time of Flight (RTOF), Received Signal Strength (RSS); based on technologies such as WiFi, Radio Frequency Identification Device (RFID), Ultra Wideband (UWB), Bluetooth and systems that have been proposed in the literature. The paper primarily discusses localization and positioning of human users and their devices. We highlight the strengths of the existing systems proposed in the literature. In contrast with the existing surveys, we also evaluate different systems from the perspective of energy efficiency, availability, cost, reception range, latency, scalability and tracking accuracy. Rather than comparing the technologies or techniques, we compare the localization systems and summarize their working principle. We also discuss remaining challenges to accurate indoor localization.
Achieving Starvation-Freedom in Multi-Version Transactional Memory Systems
Venue: arXiv cs.DC 2019
Year: 2019

Software Transactional Memory systems (STMs) have garnered significant interest as an elegant alternative for addressing synchronization and concurrency issues with multi-threaded programming in multi-core systems. Client programs use STMs by issuing transactions. STM ensures that transaction either commits or aborts. A transaction aborted due to conflicts is typically re-issued with the expectation that it will complete successfully in a subsequent incarnation. However, many existing STMs fail to provide starvation freedom, i.e., in these systems, it is possible that concurrency conflicts may prevent an incarnated transaction from committing. To overcome this limitation, we systematically derive a novel starvation free algorithm for multi-version STM. Our algorithm can be used either with the case where the number of versions is unbounded and garbage collection is used or where only the latest K versions are maintained, KSFTM. We have demonstrated that our proposed algorithm performs better than existing state-of-the-art STMs.
A hierarchical loss and its problems when classifying non-hierarchically
Venue: arXiv cs.LG 2019
Year: 2019

Failing to distinguish between a sheepdog and a skyscraper should be worse and penalized more than failing to distinguish between a sheepdog and a poodle; after all, sheepdogs and poodles are both breeds of dogs. However, existing metrics of failure (so-called "loss" or "win") used in textual or visual classification/recognition via neural networks seldom leverage a-priori information, such as a sheepdog being more similar to a poodle than to a skyscraper. We define a metric that, inter alia, can penalize failure to distinguish between a sheepdog and a skyscraper more than failure to distinguish between a sheepdog and a poodle. Unlike previously employed possibilities, this metric is based on an ultrametric tree associated with any given tree organization into a semantically meaningful hierarchy of a classifier's classes. An ultrametric tree is a tree with a so-called ultrametric distance metric such that all leaves are at the same distance from the root. Unfortunately, extensive numerical experiments indicate that the standard practice of training neural networks via stochastic gradient descent with random starting points often drives down the hierarchical loss nearly as much when minimizing the standard cross-entropy loss as when trying to minimize the hierarchical loss directly. Thus, this hierarchical loss is unreliable as an objective for plain, randomly started stochastic gradient descent to minimize; the main value of the hierarchical loss may be merely as a meaningful metric of success of a classifier.
On the Structure and Computation of Random Walk Times in Finite Graphs
Venue: arXiv cs.SY 2019
Year: 2019

We consider random walks in which the walk originates in one set of nodes and then continues until it reaches one or more nodes in a target set. The time required for the walk to reach the target set is of interest in understanding the convergence of Markov processes, as well as applications in control, machine learning, and social sciences. In this paper, we investigate the computational structure of the random walk times as a function of the set of target nodes, and find that the commute, hitting, and cover times all exhibit submodular structure, even in non-stationary random walks. We provide a unifying proof of this structure by considering each of these times as special cases of stopping times. We generalize our framework to walks in which the transition probabilities and target sets are jointly chosen to minimize the travel times, leading to polynomial-time approximation algorithms for choosing target sets. Our results are validated through numerical study.
Answering Visual-Relational Queries in Web-Extracted Knowledge Graphs
Venue: arXiv cs.LG 2019
Year: 2019

A visual-relational knowledge graph (KG) is a multi-relational graph whose entities are associated with images. We explore novel machine learning approaches for answering visual-relational queries in web-extracted knowledge graphs. To this end, we have created ImageGraph, a KG with 1,330 relation types, 14,870 entities, and 829,931 images crawled from the web. With visual-relational KGs such as ImageGraph one can introduce novel probabilistic query types in which images are treated as first-class citizens. Both the prediction of relations between unseen images as well as multi-relational image retrieval can be expressed with specific families of visual-relational queries. We introduce novel combinations of convolutional networks and knowledge graph embedding methods to answer such queries. We also explore a zero-shot learning scenario where an image of an entirely new entity is linked with multiple relations to entities of an existing KG. The resulting multi-relational grounding of unseen entity images into a knowledge graph serves as a semantic entity representation. We conduct experiments to demonstrate that the proposed methods can answer these visual-relational queries efficiently and accurately.
The Diverse Cohort Selection Problem
Venue: arXiv cs.LG 2019
Year: 2019

How should a firm allocate its limited interviewing resources to select the optimal cohort of new employees from a large set of job applicants? How should that firm allocate cheap but noisy resume screenings and expensive but in-depth in-person interviews? We view this problem through the lens of combinatorial pure exploration (CPE) in the multi-armed bandit setting, where a central learning agent performs costly exploration of a set of arms before selecting a final subset with some combinatorial structure. We generalize a recent CPE algorithm to the setting where arm pulls can have different costs and return different levels of information. We then prove theoretical upper bounds for a general class of arm-pulling strategies in this new setting. We apply our general algorithm to a real-world problem with combinatorial structure: incorporating diversity into university admissions. We take real data from admissions at one of the largest US-based computer science graduate programs and show that a simulation of our algorithm produces a cohort with hiring overall utility while spending comparable budget to the current admissions process at that university.
Robust Transmission for Massive MIMO Downlink with Imperfect CSI
Venue: arXiv cs.IT 2019
Year: 2019

In this paper, the design of robust linear precoders for the massive multi-input multi-output (MIMO) downlink with imperfect channel state information (CSI) is investigated. The imperfect CSI for each UE obtained at the BS is modeled as statistical CSI under a jointly correlated channel model with both channel mean and channel variance information, which includes the effects of channel estimation error, channel aging and spatial correlation. The design objective is to maximize the expected weighted sum-rate. By combining the minorize-maximize (MM) algorithm with the deterministic equivalent method, an algorithm for robust linear precoder design is derived. The proposed algorithm achieves a stationary point of the expected weighted sum-rate maximization problem. To reduce the computational complexity, two low-complexity algorithms are then derived. One for the general case, and the other for the case when all the channel means are zeros. For the later case, it is proved that the beam domain transmission is optimal, and thus the precoder design reduces to the power allocation optimization in the beam domain. Simulation results show that the proposed robust linear precoder designs apply to various mobile scenarios and achieve high spectral efficiency.
Synthesizing Optimally Resilient Controllers
Venue: arXiv cs.GT 2019
Year: 2019

Recently, Dallal, Neider, and Tabuada studied a generalization of the classical game-theoretic model used in program synthesis, which additionally accounts for unmodeled intermittent disturbances. In this extended framework, one is interested in computing optimally resilient strategies, i.e., strategies that are resilient against as many disturbances as possible. Dallal, Neider, and Tabuada showed how to compute such strategies for safety specifications. In this work, we compute optimally resilient strategies for a much wider range of winning conditions and show that they do not require more memory than winning strategies in the classical model. Our algorithms only have a polynomial overhead in comparison to the ones computing winning strategies. In particular, for parity conditions, optimally resilient strategies are positional and can be computed in quasipolynomial time.
Robust Attitude Tracking for Aerobatic Helicopters: A Geometric Approach
Venue: arXiv cs.SY 2019
Year: 2019

This paper highlights the significance of the rotor dynamics in control design for small-scale aerobatic helicopters, and proposes two singularity free robust attitude tracking controllers based on the available states for feedback. 1. The first, employs the angular velocity and the flap angle states (a variable that is not easy to measure) and uses a backstepping technique to design a robust compensator (BRC) to \textbf{\textit{actively}} suppress the disturbance induced tracking error. 2. The second exploits the inherent damping present in the helicopter dynamics leading to a structure preserving, \textbf{\textit{passively}} robust controller (SPR), which is free of angular velocity and flap angle feedback. The BRC controller is designed to be robust in the presence of two types of uncertainties: structured and unstructured. The structured disturbance is due to uncertainty in the rotor parameters, and the unstructured perturbation is modeled as an exogenous torque acting on the fuselage. The performance of the controller is demonstrated in the presence of both types of disturbances through numerical simulations. In contrast, the SPR tracking controller is derived such that the tracking error dynamics inherits the natural damping characteristic of the helicopter. The SPR controller is shown to be almost globally asymptotically stable and its performance is evaluated experimentally by performing aggressive flip maneuvers. Throughout the study, a nonlinear coupled rotor-fuselage helicopter model with first order flap dynamics is used.
Stochastic Stability of Perturbed Learning Automata in Positive-Utility Games
Venue: arXiv cs.GT 2019
Year: 2019

This paper considers a class of reinforcement-based learning (namely, perturbed learning automata) and provides a stochastic-stability analysis in repeatedly-played, positive-utility, finite strategic-form games. Prior work in this class of learning dynamics primarily analyzes asymptotic convergence through stochastic approximations, where convergence can be associated with the limit points of an ordinary-differential equation (ODE). However, analyzing global convergence through an ODE-approximation requires the existence of a Lyapunov or a potential function, which naturally restricts the analysis to a fine class of games. To overcome these limitations, this paper introduces an alternative framework for analyzing asymptotic convergence that is based upon an explicit characterization of the invariant probability measure of the induced Markov chain. We further provide a methodology for computing the invariant probability measure in positive-utility games, together with an illustration in the context of coordination games.
mts: A light framework for parallelizing tree search codes
Venue: arXiv cs.DC 2019
Year: 2019

We describe mts, a generic framework for parallelizing certain types of tree search programs including reverse search, backtracking, branch and bound and satisfiability testing. It abstracts and generalizes the ideas used in parallelizing lrs, a reverse search code for vertex enumeration. mts supports sharing information between processes which is important for applications such as satisfiability testing and branch-and-bound. No parallelization is implemented in the legacy single processor programs minimizing the changes needed and simplying debugging. mts is written in C, uses MPI for parallelization and can be used on a network of computers. We give four examples of reverse search codes parallelized by using mts: topological sorts, spanning trees, triangulations and Galton-Watson trees. We also give a parallelization of two codes for satisfiability testing. We give experimental results comparing the parallel codes with other codes for the same problems.
Tracking Human Pose During Robot-Assisted Dressing using Single-Axis Capacitive Proximity Sensing
Venue: arXiv cs.RO 2019
Year: 2019

Dressing is a fundamental task of everyday living and robots offer an opportunity to assist people with motor impairments. While several robotic systems have explored robot-assisted dressing, few have considered how a robot can manage errors in human pose estimation, or adapt to human motion in real time during dressing assistance. In addition, estimating pose changes due to human motion can be challenging with vision-based techniques since dressing is often intended to visually occlude the body with clothing. We present a method to track a person's pose in real time using capacitive proximity sensing. This sensing approach gives direct estimates of distance with low latency, has a high signal-to-noise ratio, and has low computational requirements. Using our method, a robot can adjust for errors in the estimated pose of a person and physically follow the contours and movements of the person while providing dressing assistance. As part of an evaluation of our method, the robot successfully pulled the sleeve of a hospital gown and a cardigan onto the right arms of 10 human participants, despite arm motions and large errors in the initially estimated pose of the person's arm. We also show that a capacitive sensor is unaffected by visual occlusion of the body and can sense a person's body through cotton clothing.
A Structural Characterization of Market Power in Electric Power Networks
Venue: arXiv cs.GT 2019
Year: 2019

We consider a market in which capacity-constrained generators compete in scalar-parameterized supply functions to serve an inelastic demand spread throughout a transmission constrained power network. The market clears according to a locational marginal pricing mechanism, in which the independent system operator (ISO) determines the generators' production quantities to minimize the revealed cost of meeting demand, while ensuring that network transmission and generator capacity constraints are met. Under the stylizing assumption that both the ISO and generators choose their strategies simultaneously, we establish the existence of Nash equilibria for the underlying market, and derive an upper bound on the allocative efficiency loss at Nash equilibrium relative to the socially optimal level. We also characterize an upper bound on the markup of locational marginal prices at Nash equilibrium above their perfectly competitive levels. Of particular relevance to ex ante market power monitoring, these bounds reveal the role of certain market structures---specifically, the \emph{market share} and \emph{residual supply index} of a producer---in predicting the degree to which that producer is able to exercise market power to influence the market outcome to its advantage. Finally, restricting our attention to the simpler setting of a two-node power network, we provide a characterization of market structures under which a Braess-like paradox occurs due to the exercise of market power---that is to say, we provide a necessary and sufficient condition on market structure under which the strengthening of the network's transmission line capacity results in the (counterintuitive) increase in the total cost of generation at Nash equilibrium.
Are we done with object recognition? The iCub robot's perspective
Venue: arXiv cs.RO 2019
Year: 2019

We report on an extensive study of the benefits and limitations of current deep learning approaches to object recognition in robot vision scenarios, introducing a novel dataset used for our investigation. To avoid the biases in currently available datasets, we consider a natural human-robot interaction setting to design a data-acquisition protocol for visual object recognition on the iCub humanoid robot. Analyzing the performance of off-the-shelf models trained off-line on large-scale image retrieval datasets, we show the necessity for knowledge transfer. We evaluate different ways in which this last step can be done, and identify the major bottlenecks affecting robotic scenarios. By studying both object categorization and identification problems, we highlight key differences between object recognition in robotics applications and in image retrieval tasks, for which the considered deep learning approaches have been originally designed. In a nutshell, our results confirm the remarkable improvements yield by deep learning in this setting, while pointing to specific open challenges that need be addressed for seamless deployment in robotics.