OpenRaiser/Intern-Atlas huggingface dataset:
A Fault-Tolerant Emergency-Aware Access Control Scheme for Cyber-Physical Systems
Venue: arXiv cs.NI 2011
Year: 2011

Access control is an issue of paramount importance in cyber-physical systems (CPS). In this paper, an access control scheme, namely FEAC, is presented for CPS. FEAC can not only provide the ability to control access to data in normal situations, but also adaptively assign emergency-role and permissions to specific subjects and inform subjects without explicit access requests to handle emergency situations in a proactive manner. In FEAC, emergency-group and emergency-dependency are introduced. Emergencies are processed in sequence within the group and in parallel among groups. A priority and dependency model called PD-AGM is used to select optimal response-action execution path aiming to eliminate all emergencies that occurred within the system. Fault-tolerant access control polices are used to address failure in emergency management. A case study of the hospital medical care application shows the effectiveness of FEAC.
A Failure Self-recovery Strategy with Balanced Energy Consumption for Wireless Ad Hoc Networks
Venue: arXiv cs.NI 2011
Year: 2011

In energy constrained wireless sensor networks, it is significant to make full use of the limited energy and maximize the network lifetime even when facing some unexpected situation. In this paper, all sensor nodes are grouped into clusters, and for each cluster, it has a mobile cluster head to manage the whole cluster. We consider an emergent situation that one of the mobile cluster heads is broken down, and hence the whole cluster is consequently out of work. An efficient approach is proposed for recovering the failure cluster by selecting multiple static sensor nodes as the cluster heads to collect packets and transmit them to the sink node. Improved simulated annealing algorithm is utilized to achieve the uniform deployment of the cluster heads. The new cluster heads are dynamically changed in order to keep balanced energy consumption. Among the new cluster heads, packets are transmitted through multi-hop forwarding path which is cost-lowest path found by Dijkstra's algorithm. A balanced energy consumption model is provided to help find the cost-lowest path and prolong the lifetime of the network. The forwarding path is updated dynamically according to the cost of the path and residual energy of the node in that path. The experimental results show that the failure cluster is recovered and the lifetime of the cluster is prolonged.
Monitoring Energy Consumption of Smartphones
Venue: arXiv cs.NI 2011
Year: 2011

With the rapid development of new and innovative applications for mobile devices like smartphones, advances in battery technology have not kept pace with rapidly growing energy demands. Thus energy consumption has become a more and more important issue of mobile devices. To meet the requirements of saving energy, it is critical to monitor and analyze the energy consumption of applications on smartphones. For this purpose, we develop a smart energy monitoring system called SEMO for smartphones using Android operating system. It can profile mobile applications with battery usage information, which is vital for both developers and users.
Design and Analysis of Coalitions in Data Swarming Systems
Venue: arXiv cs.NI 2011
Year: 2011

We design and analyze a mechanism for forming coalitions of peers in a data swarming system where peers have heterogeneous upload capacities. A coalition is a set of peers that explicitly cooperate with other peers inside the coalition via choking, data replication, and capacity allocation strategies. Further, each peer interacts with other peers outside its coalition via potentially distinct choking, data replication, and capacity allocation strategies. Following on our preliminary work in IEEE ICNP 2011 that demonstrated significant performance benefits of coalitions, we present here a comprehensive analysis of the choking and data replication strategies for coalitions. We first develop an analytical model to understand a simple random choking strategy as a within-coalition strategy and show that it accurately predicts a coalition's performance. Our analysis formally shows that the random choking strategy can help a coalition achieve near-optimal performance by optimally choosing the re-choking interval lengths and the number unchoke slots. Further, our analytical model can be easily adapted to model a BitTorrent-like swarm. We also introduce a simple data replication strategy which significantly improves data availability within a coalition as compared to the rarest-first piece replication strategy employed in BitTorrent systems. We further propose a cooperation-aware better response strategy that achieves convergence of the dynamic coalition formation process when peers freely join or leave any coalition. Finally, using extensive simulations, we demonstrate improvements in the performance of a swarming system due to coalition formation.
The Network of French Legal Codes
Venue: arXiv cs.AI 2011
Year: 2011

We propose an analysis of the codified Law of France as a structured system. Fifty two legal codes are selected on the basis of explicit legal criteria and considered as vertices with their mutual quotations forming the edges in a network which properties are analyzed relying on graph theory. We find that a group of 10 codes are simultaneously the most citing and the most cited by other codes, and are also strongly connected together so forming a "rich club" sub-graph. Three other code communities are also found that somewhat partition the legal field is distinct thematic sub-domains. The legal interpretation of this partition is opening new untraditional lines of research. We also conjecture that many legal systems are forming such new kind of networks that share some properties in common with small worlds but are far denser. We propose to call "concentrated world".
SISO APP Searches in Lattices with Tanner Graphs
Venue: arXiv cs.IT 2011
Year: 2011

An efficient, low-complexity, soft-output detector for general lattices is presented, based on their Tanner graph (TG) representations. Closest-point searches in lattices can be performed as non-binary belief propagation on associated TGs; soft-information output is naturally generated in the process; the algorithm requires no backtrack (cf. classic sphere decoding), and extracts extrinsic information. A lattice's coding gain enables equivalence relations between lattice points, which can be thereby partitioned in cosets. Total and extrinsic a posteriori probabilities at the detector's output further enable the use of soft detection information in iterative schemes. The algorithm is illustrated via two scenarios that transmit a 32-point, uncoded super-orthogonal (SO) constellation for multiple-input multiple-output (MIMO) channels, carved from an 8-dimensional non-orthogonal lattice (a direct sum of two 4-dimensional checkerboard lattice): it achieves maximum likelihood performance in quasistatic fading; and, performs close to interference-free transmission, and identically to list sphere decoding, in independent fading with coordinate interleaving and iterative equalization and detection. Latter scenario outperforms former despite the absence of forward error correction coding---because the inherent lattice coding gain allows for the refining of extrinsic information. The lattice constellation is the same as the one employed in the SO space-time trellis codes first introduced for 2-by-2 MIMO by Ionescu et al., then independently by Jafarkhani and Seshadri. Complexity is log-linear in lattice dimensionality, vs. cubic in sphere decoders.
An Elegant Argument that P is not NP
Venue: arXiv cs.CC 2011
Year: 2011

In this note, we present an elegant argument that P is not NP by demonstrating that the Meet-in-the-Middle algorithm must have the fastest running-time of all deterministic and exact algorithms which solve the SUBSET-SUM problem on a classical computer.
Dirac Notation, Fock Space and Riemann Metric Tensor in Information Retrieval Models
Venue: arXiv cs.IR 2011
Year: 2011

Using Dirac Notation as a powerful tool, we investigate the three classical Information Retrieval (IR) models and some their extensions. We show that almost all such models can be described by vectors in Occupation Number Representations (ONR) of Fock spaces with various specifications on, e.g., occupation number, inner product or term-term interactions. As important cases of study, Concept Fock Space (CFS) is introduced for Boolean model; the basic formulas for Singular Value Decomposition (SVD) of Latent Semantic Indexing (LSI) Model are manipulated in terms of Dirac notation. And, based on SVD, a Riemannian metric tensor is introduced, which not only can be used to calculate the relevance of documents to a query, but also may be used to measure the closeness of documents in data clustering.
On Frequency Optimisation for Power Saving in WSNs: Finding Optimum Hardware Timers Frequencies
Venue: arXiv cs.NI 2012
Year: 2012

Wireless Sensor Networks research and demand are now in full expansion, since people came to understand these are the key to a large number of issues in industry, commerce, home automation, healthcare, agriculture and environment, monitoring, public safety etc. One of the most challenging research problems in sensor networks research is power awareness and power-saving techniques. In this master's thesis, we have studied one particular power-saving technique, i.e. frequency scaling. In particular, we analysed the close relationship between clock frequencies in a microcontroller and several types of constraints imposed on these frequencies, e.g. by other components of the microcontroller, by protocol specifications, by external factors etc. Among these constraints, we were especially interested in the ones imposed by the timer service and by the serial ports' transmission rates. Our efforts resulted in a microcontroller configuration management tool which aims at assisting application programmers in choosing microcontroller configurations, in function of the particular needs and constraints of their application.
On Computing the Shadows and Slices of Polytopes
Venue: arXiv cs.CC 2012
Year: 2012

We study the complexity of computing the projection of an arbitrary $d$-polytope along $k$ orthogonal vectors for various input and output forms. We show that if $d$ and $k$ are part of the input (i.e. not a constant) and we are interested in output-sensitive algorithms, then in most forms the problem is equivalent to enumerating vertices of polytopes, except in two where it is NP-hard. In two other forms the problem is trivial. We also review the complexity of computing projections when the projection directions are in some sense non-degenerate. For full-dimensional polytopes containing origin in the interior, projection is an operation dual to intersecting the polytope with a suitable linear subspace and so the results in this paper can be dualized by interchanging vertices with facets and projection with intersection. To compare the complexity of projection and vertex enumeration, we define new complexity classes based on the complexity of Vertex Enumeration.
On-the-fly Macros
Venue: arXiv cs.AI 2012
Year: 2012

We present a domain-independent algorithm that computes macros in a novel way. Our algorithm computes macros "on-the-fly" for a given set of states and does not require previously learned or inferred information, nor prior domain knowledge. The algorithm is used to define new domain-independent tractable classes of classical planning that are proved to include \emph{Blocksworld-arm} and \emph{Towers of Hanoi}.
Near-Optimal Radio Use For Wireless Network Synchronization
Venue: arXiv cs.DS 2012
Year: 2012

We consider the model of communication where wireless devices can either switch their radios off to save energy, or switch their radios on and engage in communication. We distill a clean theoretical formulation of this problem of minimizing radio use and present near-optimal solutions. Our base model ignores issues of communication interference, although we also extend the model to handle this requirement. We assume that nodes intend to communicate periodically, or according to some time-based schedule. Clearly, perfectly synchronized devices could switch their radios on for exactly the minimum periods required by their joint schedules. The main challenge in the deployment of wireless networks is to synchronize the devices' schedules, given that their initial schedules may be offset relative to one another (even if their clocks run at the same speed). We significantly improve previous results, and show optimal use of the radio for two processors and near-optimal use of the radio for synchronization of an arbitrary number of processors. In particular, for two processors we prove deterministically matching $Θ(\sqrt{n})$ upper and lower bounds on the number of times the radio has to be on, where $n$ is the discretized uncertainty period of the clock shift between the two processors. (In contrast, all previous results for two processors are randomized.) For $m=n^β$ processors (for any $β< 1$) we prove $Ω(n^{(1-β)/2})$ is the lower bound on the number of times the radio has to be switched on (per processor), and show a nearly matching (in terms of the radio use) $Õ(n^{(1-β)/2})$ randomized upper bound per processor, with failure probability exponentially close to 0. For $β\geq 1$ our algorithm runs with at most $poly-log(n)$ radio invocations per processor. Our bounds also hold in a radio-broadcast model where interference must be taken into account.
Large System Analysis of Linear Precoding in Correlated MISO Broadcast Channels under Limited Feedback
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we study the sum rate performance of zero-forcing (ZF) and regularized ZF (RZF) precoding in large MISO broadcast systems under the assumptions of imperfect channel state information at the transmitter and per-user channel transmit correlation. Our analysis assumes that the number of transmit antennas $M$ and the number of single-antenna users $K$ are large while their ratio remains bounded. We derive deterministic approximations of the empirical signal-to-interference plus noise ratio (SINR) at the receivers, which are tight as $M,K\to\infty$. In the course of this derivation, the per-user channel correlation model requires the development of a novel deterministic equivalent of the empirical Stieltjes transform of large dimensional random matrices with generalized variance profile. The deterministic SINR approximations enable us to solve various practical optimization problems. Under sum rate maximization, we derive (i) for RZF the optimal regularization parameter, (ii) for ZF the optimal number of users, (iii) for ZF and RZF the optimal power allocation scheme and (iv) the optimal amount of feedback in large FDD/TDD multi-user systems. Numerical simulations suggest that the deterministic approximations are accurate even for small $M,K$.
Harvesting SSL Certificate Data to Identify Web-Fraud
Venue: arXiv cs.CR 2012
Year: 2012

Web-fraud is one of the most unpleasant features of today's Internet. Two well-known examples of fraudulent activities on the web are phishing and typosquatting. Their effects range from relatively benign (such as unwanted ads) to downright sinister (especially, when typosquatting is combined with phishing). This paper presents a novel technique to detect web-fraud domains that utilize HTTPS. To this end, we conduct the first comprehensive study of SSL certificates. We analyze certificates of legitimate and popular domains and those used by fraudulent ones. Drawing from extensive measurements, we build a classifier that detects such malicious domains with high accuracy.
Using Premia and Nsp for Constructing a Risk Management Benchmark for Testing Parallel Architecture
Venue: arXiv cs.CE 2012
Year: 2012

Financial institutions have massive computations to carry out overnight which are very demanding in terms of the consumed CPU. The challenge is to price many different products on a cluster-like architecture. We have used the Premia software to valuate the financial derivatives. In this work, we explain how Premia can be embedded into Nsp, a scientific software like Matlab, to provide a powerful tool to valuate a whole portfolio. Finally, we have integrated an MPI toolbox into Nsp to enable to use Premia to solve a bunch of pricing problems on a cluster. This unified framework can then be used to test different parallel architectures.
Tight products and Expansion
Venue: arXiv cs.DM 2012
Year: 2012

In this paper we study a new product of graphs called {\em tight product}. A graph $H$ is said to be a tight product of two (undirected multi) graphs $G_1$ and $G_2$, if $V(H)=V(G_1)\times V(G_2)$ and both projection maps $V(H)\to V(G_1)$ and $V(H)\to V(G_2)$ are covering maps. It is not a priori clear when two given graphs have a tight product (in fact, it is $NP$-hard to decide). We investigate the conditions under which this is possible. This perspective yields a new characterization of class-1 $(2k+1)$-regular graphs. We also obtain a new model of random $d$-regular graphs whose second eigenvalue is almost surely at most $O(d^{3/4})$. This construction resembles random graph lifts, but requires fewer random bits.
Energy Parity Games
Venue: arXiv cs.LO 2012
Year: 2012

Energy parity games are infinite two-player turn-based games played on weighted graphs. The objective of the game combines a (qualitative) parity condition with the (quantitative) requirement that the sum of the weights (i.e., the level of energy in the game) must remain positive. Beside their own interest in the design and synthesis of resource-constrained omega-regular specifications, energy parity games provide one of the simplest model of games with combined qualitative and quantitative objective. Our main results are as follows: (a) exponential memory is necessary and sufficient for winning strategies in energy parity games; (b) the problem of deciding the winner in energy parity games can be solved in NP \cap coNP; and (c) we give an algorithm to solve energy parity by reduction to energy games. We also show that the problem of deciding the winner in energy parity games is polynomially equivalent to the problem of deciding the winner in mean-payoff parity games, while optimal strategies may require infinite memory in mean-payoff parity games. As a consequence we obtain a conceptually simple algorithm to solve mean-payoff parity games.
A Secure Variant of the Hill Cipher
Venue: arXiv cs.CR 2012
Year: 2012

The Hill cipher is a classical symmetric encryption algorithm that succumbs to the know-plaintext attack. Although its vulnerability to cryptanalysis has rendered it unusable in practice, it still serves an important pedagogical role in cryptology and linear algebra. In this paper, a variant of the Hill cipher is introduced that makes the Hill cipher secure while it retains the efficiency. The proposed scheme includes a ciphering core for which a cryptographic protocol is introduced.
Approximating the Fréchet Distance for Realistic Curves in Near Linear Time
Venue: arXiv cs.CG 2012
Year: 2012

We present simple and practical $(1+\eps)$-approximation algorithm for the Frechet distance between curves. To analyze this algorithm we introduce a new realistic family of curves, $c$-packed curves, that is closed under simplification. We believe the notion of $c$-packed curves to be of independent interest. We show that our algorithm has near linear running time for $c$-packed curves, and show similar results for other input models.
Unbiased Offline Evaluation of Contextual-bandit-based News Article Recommendation Algorithms
Venue: arXiv cs.LG 2012
Year: 2012

Contextual bandit algorithms have become popular for online recommendation systems such as Digg, Yahoo! Buzz, and news recommendation in general. \emph{Offline} evaluation of the effectiveness of new algorithms in these applications is critical for protecting online user experiences but very challenging due to their "partial-label" nature. Common practice is to create a simulator which simulates the online environment for the problem at hand and then run an algorithm against this simulator. However, creating simulator itself is often difficult and modeling bias is usually unavoidably introduced. In this paper, we introduce a \emph{replay} methodology for contextual bandit algorithm evaluation. Different from simulator-based approaches, our method is completely data-driven and very easy to adapt to different applications. More importantly, our method can provide provably unbiased evaluations. Our empirical results on a large-scale news article recommendation dataset collected from Yahoo! Front Page conform well with our theoretical results. Furthermore, comparisons between our offline replay and online bucket evaluation of several contextual bandit algorithms show accuracy and effectiveness of our offline evaluation method.
A new bound for the capacity of the deletion channel with high deletion probabilities
Venue: arXiv cs.IT 2012
Year: 2012

Let $C(d)$ be the capacity of the binary deletion channel with deletion probability $d$. It was proved by Drinea and Mitzenmacher that, for all $d$, $C(d)/(1-d)\geq 0.1185 $. Fertonani and Duman recently showed that $\limsup_{d\to 1}C(d)/(1-d)\leq 0.49$. In this paper, it is proved that $\lim_{d\to 1}C(d)/(1-d)$ exists and is equal to $\inf_{d}C(d)/(1-d)$. This result suggests the conjecture that the curve $C(d)$ my be convex in the interval $d\in [0,1]$. Furthermore, using currently known bounds for $C(d)$, it leads to the upper bound $\lim_{d\to 1}C(d)/(1-d)\leq 0.4143$.
Impact of Connection Admission Process on the Direct Retry Load Balancing Algorithm in Cellular Network
Venue: arXiv cs.NI 2012
Year: 2012

We present an analytical framework for modeling a priority-based load balancing scheme in cellular networks based on a new algorithm called direct retry with truncated offloading channel resource pool (DR$_{K}$). The model, developed for a baseline case of two cell network, differs in many respects from previous works on load balancing. Foremost, it incorporates the call admission process, through random access. In specific, the proposed model implements the Physical Random Access Channel used in 3GPP network standards. Furthermore, the proposed model allows the differentiation of users based on their priorities. The quantitative results illustrate that, for example, cellular network operators can control the manner in which traffic is offloaded between neighboring cells by simply adjusting the length of the random access phase. Our analysis also allows for the quantitative determination of the blocking probability individual users will experience given a specific length of random access phase. Furthermore, we observe that the improvement in blocking probability per shared channel for load balanced users using DR$_{K}$ is maximized at an intermediate number of shared channels, as opposed to the maximum number of these shared resources. This occurs because a balance is achieved between the number of users requesting connections and those that are already admitted to the network. We also present an extension of our analytical model to a multi-cell network (by means of an approximation) and an application of the proposed load balancing scheme in the context of opportunistic spectrum access.