OpenRaiser/Intern-Atlas huggingface dataset:
Epistemic Model Checking of Atomic Commitment Protocols with Byzantine Failures
Venue: arXiv cs.DC 2017
Year: 2017

The notion of knowledge-based program introduced by Halpern and Fagin provides a useful formalism for designing, analysing, and optimising distributed systems. This paper formulates the two phase commit protocol as a knowledge-based program and then an iterative process of model checking and counter-example guided refinement is followed to find concrete implementations of the program for the case of perfect recall semantic in the Byzantine failures context with synchronous reliable communication. We model several different kinds of Byzantine failures and verify different strategies to fight and mitigate them. We address a number of questions that have not been considered in the prior literature, viz., under what circumstances a sender can know that its transmission has been successful, and under what circumstances an agent can know that the coordinator is cheating, and find concrete answers to these questions. The paper describes also a methodology based on temporal-epistemic model checking technology that can be followed to verify the shortest and longest execution time of a distributed protocol and the scenarios that lead to them.
Item Recommendation with Evolving User Preferences and Experience
Venue: arXiv cs.AI 2017
Year: 2017

Current recommender systems exploit user and item similarities by collaborative filtering. Some advanced methods also consider the temporal evolution of item ratings as a global background process. However, all prior methods disregard the individual evolution of a user's experience level and how this is expressed in the user's writing in a review community. In this paper, we model the joint evolution of user experience, interest in specific item facets, writing style, and rating behavior. This way we can generate individual recommendations that take into account the user's maturity level (e.g., recommending art movies rather than blockbusters for a cinematography expert). As only item ratings and review texts are observables, we capture the user's experience and interests in a latent model learned from her reviews, vocabulary and writing style. We develop a generative HMM-LDA model to trace user evolution, where the Hidden Markov Model (HMM) traces her latent experience progressing over time -- with solely user reviews and ratings as observables over time. The facets of a user's interest are drawn from a Latent Dirichlet Allocation (LDA) model derived from her reviews, as a function of her (again latent) experience level. In experiments with five real-world datasets, we show that our model improves the rating prediction over state-of-the-art baselines, by a substantial margin. We also show, in a use-case study, that our model performs well in the assessment of user experience levels.
Routing in Mobile Ad-Hoc Networks using Social Tie Strengths and Mobility Plans
Venue: arXiv cs.NI 2017
Year: 2017

We consider the problem of routing in a mobile ad-hoc network (MANET) for which the planned mobilities of the nodes are partially known a priori and the nodes travel in groups. This situation arises commonly in military and emergency response scenarios. Optimal routes are computed using the most reliable path principle in which the negative logarithm of a node pair's adjacency probability is used as a link weight metric. This probability is estimated using the mobility plan as well as dynamic information captured by table exchanges, including a measure of the social tie strength between nodes. The latter information is useful when nodes deviate from their plans or when the plans are inaccurate. We compare the proposed routing algorithm with the commonly-used optimized link state routing (OLSR) protocol in ns-3 simulations. As the OLSR protocol does not exploit the mobility plans, it relies on link state determination which suffers with increasing mobility. Our simulations show considerably better throughput performance with the proposed approach as compared with OLSR at the expense of increased overhead. However, in the high-throughput regime, the proposed approach outperforms OLSR in terms of both throughput and overhead.
Classification and Representation via Separable Subspaces: Performance Limits and Algorithms
Venue: arXiv cs.IT 2017
Year: 2017

We study the classification performance of Kronecker-structured models in two asymptotic regimes and developed an algorithm for separable, fast and compact K-S dictionary learning for better classification and representation of multidimensional signals by exploiting the structure in the signal. First, we study the classification performance in terms of diversity order and pairwise geometry of the subspaces. We derive an exact expression for the diversity order as a function of the signal and subspace dimensions of a K-S model. Next, we study the classification capacity, the maximum rate at which the number of classes can grow as the signal dimension goes to infinity. Then we describe a fast algorithm for Kronecker-Structured Learning of Discriminative Dictionaries (K-SLD2). Finally, we evaluate the empirical classification performance of K-S models for the synthetic data, showing that they agree with the diversity order analysis. We also evaluate the performance of K-SLD2 on synthetic and real-world datasets showing that the K-SLD2 balances compact signal representation and good classification performance.
A Reconnaissance Attack Mechanism for Fixed-Priority Real-Time Systems
Venue: arXiv cs.CR 2017
Year: 2017

In real-time embedded systems (RTS), failures due to security breaches can cause serious damage to the system, the environment and/or injury to humans. Therefore, it is very important to understand the potential threats and attacks against these systems. In this paper we present a novel reconnaissance attack that extracts the exact schedule of real-time systems designed using fixed priority scheduling algorithms. The attack is demonstrated on both a real hardware platform and a simulator, with a high success rate. Our evaluation results show that the algorithm is robust even in the presence of execution time variation.
Horizontal Product Differentiation in Varian's Model of Sales
Venue: arXiv cs.GT 2017
Year: 2017

We consider the explicit introduction of firms' choice of location to Varian's model of sales for a two-stage spatial competition model based on a standard Hotelling's linear city model. This model is the formalization of Varian's model of sales in the context of Hotelling's spatial competition. We obtain three main results. First, we show that there exists a subgame perfect equilibrium in which each firm chooses a symmetric mixed strategy equilibrium profile. This equilibrium includes symmetric location pairs and asymmetric location pairs. Second, the equilibrium behaviors in our model are randomized at both location and price stages. Third, we show that expected profits in a subgame perfect equilibrium are equal to the maximum monopoly profit from an uninformed market. Thus, even when product differentiation is explicitly introduced into a Varian-type model, Varian's implication can be retained; the opportunity for profit in an informed market is lost with competition.
Report on the Fourth Workshop on Sustainable Software for Science: Practice and Experiences (WSSSPE4)
Venue: arXiv cs.SE 2017
Year: 2017

This report records and discusses the Fourth Workshop on Sustainable Software for Science: Practice and Experiences (WSSSPE4). The report includes a description of the keynote presentation of the workshop, the mission and vision statements that were drafted at the workshop and finalized shortly after it, a set of idea papers, position papers, experience papers, demos, and lightning talks, and a panel discussion. The main part of the report covers the set of working groups that formed during the meeting, and for each, discusses the participants, the objective and goal, and how the objective can be reached, along with contact information for readers who may want to join the group. Finally, we present results from a survey of the workshop attendees.
Emptiness Problems for Distributed Automata
Venue: arXiv cs.FL 2017
Year: 2017

We investigate the decidability of the emptiness problem for three classes of distributed automata. These devices operate on finite directed graphs, acting as networks of identical finite-state machines that communicate in an infinite sequence of synchronous rounds. The problem is shown to be decidable in LogSpace for a class of forgetful automata, where the nodes see the messages received from their neighbors but cannot remember their own state. When restricted to the appropriate families of graphs, these forgetful automata are equivalent to classical finite word automata, but strictly more expressive than finite tree automata. On the other hand, we also show that the emptiness problem is undecidable in general. This already holds for two heavily restricted classes of distributed automata: those that reject immediately if they receive more than one message per round, and those whose state diagram must be acyclic except for self-loops.
Lightweight Robust Framework for Workload Scheduling in Clouds
Venue: arXiv cs.DC 2017
Year: 2017

Reliability, security and stability of cloud services without sacrificing too much resources have become a desired feature in the area of workload management in clouds. The paper proposes and evaluates a lightweight framework for scheduling a workload which part could be unreliable. This unreliability could be caused by various types of failures or attacks. Our framework for robust workload scheduling efficiently combines classic fault-tolerant and security tools, such as packet/job scanning, with workload scheduling, and it does not use any heavy resource-consuming tools, e.g., cryptography or non-linear optimization. More specifically, the framework uses a novel objective function to allocate jobs to servers and constantly decides which job to scan based on a formula associated with the objective function. We show how to set up the objective function and the corresponding scanning procedure to make the system provably stable, provided it satisfies a specific stability condition. As a result, we show that our framework assures cloud stability even if naive scanning-all and scanning-none strategies are not stable. We extend the framework to decentralized scheduling and evaluate it under several popular routing procedures.
AirDraw: Leveraging Smart Watch Motion Sensors for Mobile Human Computer Interactions
Venue: arXiv cs.CV 2017
Year: 2017

Wearable computing is one of the fastest growing technologies today. Smart watches are poised to take over at least of half the wearable devices market in the near future. Smart watch screen size, however, is a limiting factor for growth, as it restricts practical text input. On the other hand, wearable devices have some features, such as consistent user interaction and hands-free, heads-up operations, which pave the way for gesture recognition methods of text entry. This paper proposes a new text input method for smart watches, which utilizes motion sensor data and machine learning approaches to detect letters written in the air by a user. This method is less computationally intensive and less expensive when compared to computer vision approaches. It is also not affected by lighting factors, which limit computer vision solutions. The AirDraw system prototype developed to test this approach is presented. Additionally, experimental results close to 71% accuracy are presented.
Out-of-Order Dataflow Scheduling for FPGA Overlays
Venue: arXiv cs.AR 2017
Year: 2017

We exploit floating-point DSPs in the Arria10 FPGA and multi-pumping feature of the M20K RAMs to build a dataflow-driven soft processor fabric for large graph workloads. In this paper, we introduce the idea of out-of-order node scheduling across a large number of local nodes (thousands) per processor by combining an efficient node tagging scheme along with leading-one detector circuits. We use a static one-time node labeling algorithm to sort nodes based on criticality to organize local memory inside each soft processor. This translates to a small ~6% memory overhead. When compared to a memory-expensive FIFO-based first-come-first-serve approach used in previous studies, we deliver up to 50% performance improvement while eliminating the cost of the FIFOs. On the Arria10 10AX115S board, we can create an overlay design of up to 300 processors connected by high bandwidth Hoplite NoC at frequencies up to 250MHz.
Combating Human Trafficking with Deep Multimodal Models
Venue: arXiv cs.CL 2017
Year: 2017

Human trafficking is a global epidemic affecting millions of people across the planet. Sex trafficking, the dominant form of human trafficking, has seen a significant rise mostly due to the abundance of escort websites, where human traffickers can openly advertise among at-will escort advertisements. In this paper, we take a major step in the automatic detection of advertisements suspected to pertain to human trafficking. We present a novel dataset called Trafficking-10k, with more than 10,000 advertisements annotated for this task. The dataset contains two sources of information per advertisement: text and images. For the accurate detection of trafficking advertisements, we designed and trained a deep multimodal model called the Human Trafficking Deep Network (HTDN).
Polarization Shift Keying (PolarSK): System Scheme and Performance Analysis
Venue: arXiv cs.IT 2017
Year: 2017

Single-Radio-Frequency (RF) Multiple-Input-Multiple-Output (MIMO) systems such as the spatial modulation (SM) system and the space shift keying (SSK) system have been proposed to pursue a high spectral efficiency while keeping a low cost and complexity transceiver design. Currently, polarization domain resource has been introduced to the single-RF MIMO system to reduce the size of the transmit antenna array and provide 1 bit per channel use (bpcu) multiplexing gain. Nevertheless, the polarization domain resource still has the potential to provide a higher multiplexing gain in the polarized single-RF MIMO system. In this paper, we propose a generalized polarization shift keying (PolarSK) modulation scheme for a SIMO system that uses the polarization states in the dual-polarized transmit antenna as an information-bearing unit to increase the overall spectral efficiency. At the receive end, the maximum likelihood (ML) detector is employed to demodulate the received signal. A closed form union upper bound on the average bit error probability (ABEP) of PolarSK system with the optimum maximum likelihood (ML) receiver is deduced under fading channels. To reduce the computational complexity of the receiver, a linear successive interference cancellation (SIC) detection algorithm and a sphere-decoding (SD) detection algorithm are proposed. On the basis of analytic results and simulations, performances of the proposed PolarSK systems in terms of computational complexity and ABEP are analyzed. Numerical results show that the proposed PolarSK scheme performs better than state of the art dual-polarized/uni-polarized SM schemes.
Density Estimation for Geolocation via Convolutional Mixture Density Network
Venue: arXiv cs.CL 2017
Year: 2017

Nowadays, geographic information related to Twitter is crucially important for fine-grained applications. However, the amount of geographic information avail- able on Twitter is low, which makes the pursuit of many applications challenging. Under such circumstances, estimating the location of a tweet is an important goal of the study. Unlike most previous studies that estimate the pre-defined district as the classification task, this study employs a probability distribution to represent richer information of the tweet, not only the location but also its ambiguity. To realize this modeling, we propose the convolutional mixture density network (CMDN), which uses text data to estimate the mixture model parameters. Experimentally obtained results reveal that CMDN achieved the highest prediction performance among the method for predicting the exact coordinates. It also provides a quantitative representation of the location ambiguity for each tweet that properly works for extracting the reliable location estimations.
Scene Text Eraser
Venue: arXiv cs.CV 2017
Year: 2017

The character information in natural scene images contains various personal information, such as telephone numbers, home addresses, etc. It is a high risk of leakage the information if they are published. In this paper, we proposed a scene text erasing method to properly hide the information via an inpainting convolutional neural network (CNN) model. The input is a scene text image, and the output is expected to be text erased image with all the character regions filled up the colors of the surrounding background pixels. This work is accomplished by a CNN model through convolution to deconvolution with interconnection process. The training samples and the corresponding inpainting images are considered as teaching signals for training. To evaluate the text erasing performance, the output images are detected by a novel scene text detection method. Subsequently, the same measurement on text detection is utilized for testing the images in benchmark dataset ICDAR2013. Compared with direct text detection way, the scene text erasing process demonstrates a drastically decrease on the precision, recall and f-score. That proves the effectiveness of proposed method for erasing the text in natural scene images.
On the Height of Towers of Subsequences and Prefixes
Venue: arXiv cs.FL 2017
Year: 2017

A tower is a sequence of words alternating between two languages in such a way that every word is a subsequence of the following word. The height of the tower is the number of words in the sequence. If there is no infinite tower (a tower of infinite height), then the height of all towers between the languages is bounded. We study upper and lower bounds on the height of maximal finite towers with respect to the size of the NFA (the DFA) representation of the languages. We show that the upper bound is polynomial in the number of states and exponential in the size of the alphabet, and that it is asymptotically tight if the size of the alphabet is fixed. If the alphabet may grow, then, using an alphabet of size approximately the number of states of the automata, the lower bound on the height of towers is exponential with respect to that number. In this case, there is a gap between the lower and upper bound, and the asymptotically optimal bound remains an open problem. Since, in many cases, the constructed towers are sequences of prefixes, we also study towers of prefixes.
Flat Parallelization
Venue: arXiv cs.DC 2017
Year: 2017

There are two intertwined factors that affect performance of concurrent data structures: the ability of processes to access the data in parallel and the cost of synchronization. It has been observed that for a large class of "concurrency-unfriendly" data structures, fine-grained parallelization does not pay off: an implementation based on a single global lock outperforms fine-grained solutions. The flat combining paradigm exploits this by ensuring that a thread holding the global lock sequentially combines requests and then executes the combined requests on behalf of concurrent threads. In this paper, we propose a synchronization technique that unites flat combining and parallel bulk updates borrowed from parallel algorithms designed for the PRAM model. The idea is that the combiner thread assigns waiting threads to perform concurrent requests in parallel. We foresee the technique to help in implementing efficient "concurrency-ambivalent" data structures, which can benefit from both parallelism and serialization, depending on the operational context. To validate the idea, we considered heap-based implementations of a priority queue. These data structures exhibit two important features: concurrent remove operations are likely to conflict and thus may benefit from combining, while concurrent insert operations can often be at least partly applied in parallel thus may benefit from parallel batching. We show that the resulting flat parallelization algorithm performs well compared to state-of-the-art priority queue implementations.
Concurrent Constraint Conditional-Branching Timed Interactive Scores
Venue: arXiv cs.LO 2017
Year: 2017

Multimedia scenarios have multimedia content and interactive events associated with computer programs. Interactive Scores (IS) is a formalism to represent such scenarios by temporal objects, temporal relations (TRs) and interactive events. IS describe TRs, but IS cannot represent TRs together with conditional branching. We propose a model for conditional branching timed IS in the Non-deterministic Timed Concurrent Constraint (ntcc) calculus. We ran a prototype of our model in Ntccrt (a real-time capable interpreter for ntcc) and the response time was acceptable for real-time interaction. An advantage of ntcc over Max/MSP or Petri Nets is that conditions and global constraints are represented declaratively.
Resistive communications based on neuristors
Venue: arXiv cs.ET 2017
Year: 2017

Memristors are passive elements that allow us to store information using a single element per bit. However, this is not the only utility of the memristor. Considering the physical chemical structure of the element used, the memristor can function at the same time as memory and as a communication unit. This paper presents a new approach to the use of the memristor and develops the concept of resistive communication.
Communications for Wearable Devices
Venue: arXiv cs.CY 2017
Year: 2017

Wearable devices are transforming computing and the human-computer interaction and they are a primary means for motion recognition of reflexive systems. We review basic wearable deployments and their open wireless communications. An algorithm that uses accelerometer data to provide a control and communication signal is described. Challenges in the further deployment of wearable device in the field of body area network and biometric verification are discussed.
A Multi-Class Dispatching and Charging Scheme for Autonomous Electric Mobility On-Demand
Venue: arXiv cs.SY 2017
Year: 2017

Despite the significant advances in vehicle automation and electrification, the next-decade aspirations for massive deployments of autonomous electric mobility on demand (AEMoD) services are still threatened by two major bottlenecks, namely the computational and charging delays. This paper proposes a solution for these two challenges by suggesting the use of fog computing for AEMoD systems, and developing an optimized multi-class charging and dispatching scheme for its vehicles. A queuing model representing the proposed multi-class charging and dispatching scheme is first introduced. The stability conditions of this model and the number of classes that fit the charging capabilities of any given city zone are then derived. Decisions on the proportions of each class vehicles to partially/fully charge, or directly serve customers are then optimized using a stochastic linear program that minimizes the maximum response time of the system. Results show the merits of our proposed model and optimized decision scheme compared to both the always-charge and the equal split schemes.