OpenRaiser/Intern-Atlas huggingface dataset:
Proofs of Writing for Efficient and Robust Storage
Venue: arXiv cs.DC 2012
Year: 2012

We present PoWerStore, the first efficient robust storage protocol that achieves optimal latency without using digital signatures. PoWerStore's robustness comprises tolerating asynchrony, maximum number of Byzantine storage servers, any number of Byzantine readers and crash-faulty writers, and guaranteeing wait-freedom and linearizability of read/write operations. PoWerStore's efficiency stems from combining lightweight authentication, erasure coding and metadata write-backs where readers write-back only metadata to achieve linearizability. At the heart of PoWerStore are Proofs of Writing (PoW): a novel storage technique based on lightweight cryptography. PoW enable reads and writes in the single-writer variant of PoWerStore to have latency of 2 rounds of communication between a client and storage servers in the worst-case (which we show optimal). We further present and implement a multi-writer PoWerStore variant featuring 3-round writes/reads where the third read round is invoked only under active attacks, and show that it outperforms existing robust storage protocols, including crash-tolerant ones.
Sum-Rate Maximization with Minimum Power Consumption for MIMO DF Two-Way Relaying: Part II - Network Optimization
Venue: arXiv cs.IT 2012
Year: 2012

In Part II of this two-part paper, a sum-rate-maximizing power allocation with minimum power consumption is found for multiple-input multiple-output (MIMO) decode-and-forward (DF) two-way relaying (TWR) in a network optimization scenario. In this scenario, the relay and the source nodes jointly optimize their power allocation strategies to achieve network optimality. Unlike the relay optimization scenario considered in part I which features low complexity but does not achieve network optimality, the network-level optimal power allocation can be achieved in the network optimization scenario at the cost of higher complexity. The network optimization problem is considered in two cases each with several subcases. It is shown that the considered problem, which is originally nonconvex, can be transferred into different convex problems for all but two subcases. For the remaining two subcases, one for each case, it is proved that the optimal strategies for the source nodes and the relay must satisfy certain properties. Based on these properties, an algorithm is proposed for finding the optimal solution. The effect of asymmetry in the number of antennas, power limits, and channel statistics is also considered. Such asymmetry is shown to have a negative effect on both the achievable sum-rate and the power allocation efficiency in MIMO DF TWR. Simulation results demonstrate the performance of the proposed algorithm and the effect of asymmetry in the system.
An Authentication Technique in Frequency Domain through Wavelet Transform (ATFDWT)
Venue: arXiv cs.CR 2012
Year: 2012

In this paper a DWT based steganography in frequency domain, termed as ATFDWT has been proposed. Here, the cover image is transformed into the time domain signal through DWT, resulting four sub-image components as 'Low resolution', 'Horizontal orientation', 'Vertical orientation' and 'Diagonal orientation'. The secret message/image bits stream in varying positions are embedded in 'Vertical orientation sub-image' followed by reverse transformation to generate embedded/encrypted image. The decoding is done through the reverse procedure. The experimental results against statistical and visual attack has been computed and compared with the existing technique like IAFDDFTT[1], in terms of Mean Square Error (MSE), Peak Signal to Noise Ratio (PSNR), Standard Deviation(SD) and Image Fidelity(IF) analysis, which shows better performances in ATFDWT.
Envy Freedom and Prior-free Mechanism Design
Venue: arXiv cs.GT 2012
Year: 2012

We consider the provision of an abstract service to single-dimensional agents. Our model includes position auctions, single-minded combinatorial auctions, and constrained matching markets. When the agents' values are drawn from a distribution, the Bayesian optimal mechanism is given by Myerson (1981) as a virtual-surplus optimizer. We develop a framework for prior-free mechanism design and analysis. A good mechanism in our framework approximates the optimal mechanism for the distribution if there is a distribution; moreover, when there is no distribution this mechanism still performs well. We define and characterize optimal envy-free outcomes in symmetric single-dimensional environments. Our characterization mirrors Myerson's theory. Furthermore, unlike in mechanism design where there is no point-wise optimal mechanism, there is always a point-wise optimal envy-free outcome. Envy-free outcomes and incentive-compatible mechanisms are similar in structure and performance. We therefore use the optimal envy-free revenue as a benchmark for measuring the performance of a prior-free mechanism. A good mechanism is one that approximates the envy free benchmark on any profile of agent values. We show that good mechanisms exist, and in particular, a natural generalization of the random sampling auction of Goldberg et al. (2001) is a constant approximation.
Shared Contract-Obedient Endpoints
Venue: arXiv cs.PL 2012
Year: 2012

Most of the existing verification techniques for message-passing programs suppose either that channel endpoints are used in a linear fashion, where at most one thread may send or receive from an endpoint at any given time, or that endpoints may be used arbitrarily by any number of threads. The former approach usually forbids the sharing of channels while the latter limits what is provable about programs. In this paper we propose a midpoint between these techniques by extending a proof system based on separation logic to allow sharing of endpoints. We identify two independent mechanisms for supporting sharing: an extension of fractional shares to endpoints, and a new technique based on what we call reflexive ownership transfer. We demonstrate on a number of examples that a linear treatment of sharing is possible.
On Link Availability Probability of Routing Protocols for Urban Scenario in VANETs
Venue: arXiv cs.NI 2012
Year: 2012

This paper presents the link availability probability. We evaluate and compare the link availability probability for routing protocols; Ad hoc On-demand Distance vector (AODV), Dynamic Source Routing (DSR) and Fisheye State Routing (FSR) for different number of connections and node density. A novel contribution of this work is enhancement in existing parameters of routing protocols; AODV, DSR and FSR as MOD-AODV, MOD-DSR and MOD-FSR. From the results, we observe that MOD-DSR and DSR outperform MOD-AODV, AODV, MODOLSR and OLSR in terms of Packet Delivery Ratio (PDR), Average End-to End Delay (AE2ED), link availability probability at the cost of high value of Normalized Routing Overhead (NRO).
On the notion of balance in social network analysis
Venue: arXiv cs.SI 2012
Year: 2012

The notion of "balance" is fundamental for sociologists who study social networks. In formal mathematical terms, it concerns the distribution of triad configurations in actual networks compared to random networks of the same edge density. On reading Charles Kadushin's recent book "Understanding Social Networks", we were struck by the amount of confusion in the presentation of this concept in the early sections of the book. This confusion seems to lie behind his flawed analysis of a classical empirical data set, namely the karate club graph of Zachary. Our goal here is twofold. Firstly, we present the notion of balance in terms which are logically consistent, but also consistent with the way sociologists use the term. The main message is that the notion can only be meaningfully applied to undirected graphs. Secondly, we correct the analysis of triads in the karate club graph. This results in the interesting observation that the graph is, in a precise sense, quite "unbalanced". We show that this lack of balance is characteristic of a wide class of starlike-graphs, and discuss possible sociological interpretations of this fact, which may be useful in many other situations.
Symbiotic Cognitive Relaying with mobile Secondary nodes in Cognitive Radio Networks
Venue: arXiv cs.NI 2012
Year: 2012

In a Symbiotic Cognitive Relaying (SCR) scenario, the Secondary users(SU) nodes can act as multihop relays to assist the communication between Primary User(PU) nodes in the case of a weak direct link. In return, the SU nodes are incentivised with the right to carry out SU-SU communication using licensed PU band for a fixed amount of time, referred to as the 'Time Incentive'. Existing work on SCR is constrained to a fixed ad-hoc SU network. In this paper, we introduce mobility in SCR by considering mobile SU nodes while keeping the PU nodes fixed. This paper uses a specific mobility pattern and routing strategy for the SU nodes to propose theoretical bounds on the throughput and delay of PU-PU transmission. We derive analytically the least throughput and maximum delay possible in our model.
The Grammar Hammer of 2012
Venue: arXiv cs.FL 2012
Year: 2012

This document is a case study in aggressive self-archiving. It collects all initiatives undertaken by its author in 2012, including unpublished ones, explains their relevance and relation with one another. Discussed topics include guided convergence of formal grammars in a broad sense, programmable grammar transformation operator suites, metasyntactic specifications and methods of their manipulation, tolerant (soft computing) methods in parsing theory, megamodelling as modelling linguistic architecture of software systems, repositories of grammatical knowledge, open notebook computer science, as well as the number of minor topics (new parsing algorithms, visualisation techniques, etc). A brief overview of involved venues is also included in the report.
Extending a system in the calculus of structures with a self-dual quantifier
Venue: arXiv cs.LO 2012
Year: 2012

We recall that SBV, a proof system developed under the methodology of deep inference, extends multiplicative linear logic with the self-dual non-commutative logical operator Seq. We introduce SBVQ that extends SBV by adding the self-dual quantifier Sdq. The system SBVQ is consistent because we prove that (the analogous of) cut elimination holds for it. Its new logical operator Sdq operationally behaves as a binder, in a way that the interplay between Seq, and Sdq can model β-reduction of linear λ-calculus inside the cut-free subsystem BVQ of SBVQ. The long term aim is to keep developing a programme whose goal is to give pure logical accounts of computational primitives under the proof-search-as-computation analogy, by means of minimal, and incremental extensions of SBV.
Low Speed Automation, a French Initiative
Venue: arXiv cs.RO 2012
Year: 2012

Nowadays, vehicle safety is constantly increasing thanks to the improvement of vehicle passive and active safety. However, on a daily usage of the car, traffic jams remains a problem. With limited space for road infrastructure, automation of the driving task on specific situation seems to be a possible solution. The French project ABV, which stands for low speed automation, tries to demonstrate the feasibility of the concept and to prove the benefits. In this article, we describe the scientific background of the project and expected outputs.
New inequalities of Mill's ratio and Its Application to The Inverse Q-function Approximation
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we investigate the Mill's ratio estimation problem and get two new inequalities. Compared to the well known results obtained by Gordon, they becomes tighter. Furthermore, we also discuss the inverse Q-function approximation problem and present some useful results on the inverse solution. Numerical results confirm the validness of our theoretical analysis. In addition, we also present a conjecture on the bounds of inverse solution on Q-function.
Automatic landmark annotation and dense correspondence registration for 3D human facial images
Venue: arXiv cs.CV 2012
Year: 2012

Dense surface registration of three-dimensional (3D) human facial images holds great potential for studies of human trait diversity, disease genetics, and forensics. Non-rigid registration is particularly useful for establishing dense anatomical correspondences between faces. Here we describe a novel non-rigid registration method for fully automatic 3D facial image mapping. This method comprises two steps: first, seventeen facial landmarks are automatically annotated, mainly via PCA-based feature recognition following 3D-to-2D data transformation. Second, an efficient thin-plate spline (TPS) protocol is used to establish the dense anatomical correspondence between facial images, under the guidance of the predefined landmarks. We demonstrate that this method is robust and highly accurate, even for different ethnicities. The average face is calculated for individuals of Han Chinese and Uyghur origins. While fully automatic and computationally efficient, this method enables high-throughput analysis of human facial feature variation.
A Study on the Open Source Digital Library Software's: Special Reference to DSpace, EPrints and Greenstone
Venue: arXiv cs.DL 2012
Year: 2012

The richness in knowledge has changed access methods for all stake holders in retrieving key knowledge and relevant information. This paper presents a study of three open source digital library management software used to assimilate and disseminate information to world audience. The methodology followed involves online survey and study of related software documentation and associated technical manuals.
Practical, scalable alternative session encryption using one-time pads
Venue: arXiv cs.CR 2012
Year: 2012

When I was smaller, a five megabyte fixed disk cost $5,000, a 300 bps modem cost hundreds of dollars, and communication links were intercepted by attaching devices to the target subscriber's local loop. From then to now there have been three great implosions: the cost of storage, the cost of bandwidth, and the cost of surveillance. The wake of the first two implosions sheared away most obstacles to using one-time pads to encrypt data in flight, and the final imposition -- I mean implosion -- now makes consideration of one-time pads a practical necessity. So far as assurance of confidentiality is concerned, today's block ciphers and public key cryptosystems flunk the exam. I don't know how to recover an AES key or compute the discrete logarithm of an elliptic curve element, but there exists no proof that another cannot. Moreover, encrypted communications can be recorded and stored for later attack by algorithms and devices yet to be discovered. Equally concerning is that when a significant "break" is discovered for solving either puzzle, the safety of an entire planet's communication and data dissolves like instant pudding. The world is unready to ingest so much pudding. We need balance in our cryptographic diet, and we need that balance now. In this paper, I discredit many myths concerning one-time pads, discuss practical steps to address perceived shortcomings, and shatter the notion that secure generation, distribution, and use of mammoth cryptographic keys cannot be practiced in every home, church, school, and business. I also discuss my own implementations, their capabilities and track record, and where they should lead.
Rewrite Closure and CF Hedge Automata
Venue: arXiv cs.LO 2012
Year: 2012

We introduce an extension of hedge automata called bidimensional context-free hedge automata. The class of unranked ordered tree languages they recognize is shown to be preserved by rewrite closure with inverse-monadic rules. We also extend the parameterized rewriting rules used for modeling the W3C XQuery Update Facility in previous works, by the possibility to insert a new parent node above a given node. We show that the rewrite closure of hedge automata languages with these extended rewriting systems are context-free hedge languages.
Statistical Traffic State Analysis in Large-scale Transportation Networks Using Locality-Preserving Non-negative Matrix Factorization
Venue: arXiv cs.CE 2012
Year: 2012

Statistical traffic data analysis is a hot topic in traffic management and control. In this field, current research progresses focus on analyzing traffic flows of individual links or local regions in a transportation network. Less attention are paid to the global view of traffic states over the entire network, which is important for modeling large-scale traffic scenes. Our aim is precisely to propose a new methodology for extracting spatio-temporal traffic patterns, ultimately for modeling large-scale traffic dynamics, and long-term traffic forecasting. We attack this issue by utilizing Locality-Preserving Non-negative Matrix Factorization (LPNMF) to derive low-dimensional representation of network-level traffic states. Clustering is performed on the compact LPNMF projections to unveil typical spatial patterns and temporal dynamics of network-level traffic states. We have tested the proposed method on simulated traffic data generated for a large-scale road network, and reported experimental results validate the ability of our approach for extracting meaningful large-scale space-time traffic patterns. Furthermore, the derived clustering results provide an intuitive understanding of spatial-temporal characteristics of traffic flows in the large-scale network, and a basis for potential long-term forecasting.
An Effective Machine-Part Grouping Algorithm to Construct Manufacturing Cells
Venue: arXiv cs.CE 2012
Year: 2012

The machine-part cell formation problem consists of creating machine cells and their corresponding part families with the objective of minimizing the inter-cell and intra-cell movement while maximizing the machine utilization. This article demonstrates a hybrid clustering approach for the cell formation problem in cellular manufacturing that conjoins Sorenson s similarity coefficient based method to form the production cells. Computational results are shown over the test datasets obtained from the past literature. The hybrid technique is shown to outperform the other methods proposed in literature and including powerful soft computing approaches such as genetic algorithms, genetic programming by exceeding the solution quality on the test problems.
Towards the Evolution of Novel Vertical-Axis Wind Turbines
Venue: arXiv cs.NE 2012
Year: 2012

Renewable and sustainable energy is one of the most important challenges currently facing mankind. Wind has made an increasing contribution to the world's energy supply mix, but still remains a long way from reaching its full potential. In this paper, we investigate the use of artificial evolution to design vertical-axis wind turbine prototypes that are physically instantiated and evaluated under approximated wind tunnel conditions. An artificial neural network is used as a surrogate model to assist learning and found to reduce the number of fabrications required to reach a higher aerodynamic efficiency, resulting in an important cost reduction. Unlike in other approaches, such as computational fluid dynamics simulations, no mathematical formulations are used and no model assumptions are made.
Multi-Objective AI Planning: Evaluating DAE-YAHSP on a Tunable Benchmark
Venue: arXiv cs.AI 2012
Year: 2012

All standard AI planners to-date can only handle a single objective, and the only way for them to take into account multiple objectives is by aggregation of the objectives. Furthermore, and in deep contrast with the single objective case, there exists no benchmark problems on which to test the algorithms for multi-objective planning. Divide and Evolve (DAE) is an evolutionary planner that won the (single-objective) deterministic temporal satisficing track in the last International Planning Competition. Even though it uses intensively the classical (and hence single-objective) planner YAHSP, it is possible to turn DAE-YAHSP into a multi-objective evolutionary planner. A tunable benchmark suite for multi-objective planning is first proposed, and the performances of several variants of multi-objective DAE-YAHSP are compared on different instances of this benchmark, hopefully paving the road to further multi-objective competitions in AI planning.
Dual-Based Bounds for Resource Allocation in Zero-forcing Beamforming OFDMA-SDMA Systems
Venue: arXiv cs.IT 2012
Year: 2012

We consider multi-antenna base stations using orthogonal frequency division multiple access and space division multiple access techniques to serve single-antenna users. Some users, called real-time users, have minimum rate requirements and must be served in the current time slot while others, called non real-time users, do not have strict timing constraints and are served on a best-effort basis. The resource allocation problem is to find the assignment of users to subcarriers and the transmit beamforming vectors that maximize the total user rates subject to power and minimum rate constraints. In general, this is a nonlinear and non-convex program and the zero-forcing technique used here makes it integer as well, exact optimal solutions cannot be computed in reasonable time for realistic cases. For this reason, we present a technique to compute both upper and lower bounds and show that these are quite close for some realistic cases. First, we formulate the dual problem whose optimum provides an upper bound to all feasible solutions. We then use a simple method to get a primal-feasible point starting from the dual optimal solution, which is a lower bound on the primal optimal solution. Numerical results for several cases show that the two bounds are close so that the dual method can be used to benchmark any heuristic used to solve this problem. As an example, we provide numerical results showing the performance gap of the well-known weight adjustment method and show that there is considerable room for improvement.
Convex Hull and Linear Programming in Read-only Setup with Limited Work-space
Venue: arXiv cs.CG 2012
Year: 2012

Prune-and-search is an important paradigm for solving many important geometric problems. We show that the general prune-and-search technique can be implemented where the objects are given in read-only memory. As examples we consider convex-hull in 2D, and linear programming in 2D and 3D. For the convex-hull problem, designing sub-quadratic algorithm in a read-only setup with sub-linear space is an open problem for a long time. We first propose a simple algorithm for this problem that runs in $O(n^{3/2+ε)}$ time and $O(n^(1/2))$ space. Next, we consider a restricted version of the problem where the points in $P$ are given in sorted order with respect to their $x$-coordinates in a read-only array. For the linear programming problems, the constraints are given in the read-only array. The last three algorithms use {\it prune-and-search}, and their time and extra work-space complexities are $O(n^{1 + ε})$ and $O(\log n)$ respectively, where $ε$ is a small constant satisfying $\sqrt{\frac{\log\log n}{\log n}} < ε< 1$.