OpenRaiser/Intern-Atlas huggingface dataset:
A New Paradigm for Minimax Search
Venue: arXiv cs.AI 2014
Year: 2014

This paper introduces a new paradigm for minimax game-tree search algo- rithms. MT is a memory-enhanced version of Pearls Test procedure. By changing the way MT is called, a number of best-first game-tree search algorithms can be simply and elegantly constructed (including SSS*). Most of the assessments of minimax search algorithms have been based on simulations. However, these simulations generally do not address two of the key ingredients of high performance game-playing programs: iterative deepening and memory usage. This paper presents experimental data from three game-playing programs (checkers, Othello and chess), covering the range from low to high branching factor. The improved move ordering due to iterative deepening and memory usage results in significantly different results from those portrayed in the literature. Whereas some simulations show Alpha-Beta expanding almost 100% more leaf nodes than other algorithms [12], our results showed variations of less than 20%. One new instance of our framework (MTD-f) out-performs our best alpha- beta searcher (aspiration NegaScout) on leaf nodes, total nodes and execution time. To our knowledge, these are the first reported results that compare both depth-first and best-first algorithms given the same amount of memory
Nearly Optimal Minimax Tree Search?
Venue: arXiv cs.AI 2014
Year: 2014

Knuth and Moore presented a theoretical lower bound on the number of leaves that any fixed-depth minimax tree-search algorithm traversing a uniform tree must explore, the so-called minimal tree. Since real-life minimax trees are not uniform, the exact size of this tree is not known for most applications. Further, most games have transpositions, implying that there exists a minimal graph which is smaller than the minimal tree. For three games (chess, Othello and checkers) we compute the size of the minimal tree and the minimal graph. Empirical evidence shows that in all three games, enhanced Alpha-Beta search is capable of building a tree that is close in size to that of the minimal graph. Hence, it appears game-playing programs build nearly optimal search trees. However, the conventional definition of the minimal graph is wrong. There are ways in which the size of the minimal graph can be reduced: by maximizing the number of transpositions in the search, and generating cutoffs using branches that lead to smaller search trees. The conventional definition of the minimal graph is just a left-most approximation. Calculating the size of the real minimal graph is too computationally intensive. However, upper bound approximations show it to be significantly smaller than the left-most minimal graph. Hence, it appears that game-playing programs are not searching as efficiently as is widely believed. Understanding the left-most and real minimal search graphs leads to some new ideas for enhancing Alpha-Beta search. One of them, enhanced transposition cutoffs, is shown to significantly reduce search tree size.
Detecting a Corrupted Area in a 2-Dimensional Space
Venue: arXiv cs.DS 2014
Year: 2014

Motivated by the fact that 2-dimensional data have become popularly used in many applications without being much considered its integrity checking. We introduce the problem of detecting a corrupted area in a 2-dimensional space, and investigate two possible efficient approaches and show their time and space complexities. Also, we briefly introduce the idea of an approximation scheme using a hash sieve and suggest a novel "adaptive tree" structure revealing granularity of information.
On Resilient Control of Nonlinear Systems under Denial-of-Service
Venue: arXiv cs.SY 2014
Year: 2014

We analyze and design a control strategy for nonlinear systems under Denial-of-Service attacks. Based on an ISS-Lyapunov function analysis, we provide a characterization of the maximal percentage of time during which feedback information can be lost without resulting in the instability of the system. Motivated by the presence of a digital channel we consider event-based controllers for which a minimal inter-sampling time is explicitly characterized.
The Prospects for e-Examinations in Nigeria and Australia
Venue: arXiv cs.CY 2014
Year: 2014

This paper compares the e-Examination system in Nigeria with that of Australia. We consider the experiences of working with commercial firms such as Electronic Testing Company (eTC) and using open-source software. It is important to foster good relationships with accreditation authorities (such as University Authorities, West African Examination Council (WAEC), Joint Admissions and Matriculation Board (JAMB) etc. and the Tasmanian Qualifications Authority) to assist in the transition from paperbased assessment to post-paper assessment. The paper also considers the relative convenience for students, administrators and lecturer/assessors; and to gauges the reliability and security of the two systems in use. It examines the challenges in conducting e-Examinations in both countries by juxtaposing the systems in the two countries and suggests ways of developing more acceptable e-Examination systems.
CernVM Online and Cloud Gateway: a uniform interface for CernVM contextualization and deployment
Venue: arXiv cs.DC 2014
Year: 2014

In a virtualized environment, contextualization is the process of configuring a VM instance for the needs of various deployment use cases. Contextualization in CernVM can be done by passing a handwritten context to the user data field of cloud APIs, when running CernVM on the cloud, or by using CernVM web interface when running the VM locally. CernVM Online is a publicly accessible web interface that unifies these two procedures. A user is able to define, store and share CernVM contexts using CernVM Online and then apply them either in a cloud by using CernVM Cloud Gateway or on a local VM with the single-step pairing mechanism. CernVM Cloud Gateway is a distributed system that provides a single interface to use multiple and different clouds (by location or type, private or public). Cloud gateway has been so far integrated with OpenNebula, CloudStack and EC2 tools interfaces. A user, with access to a number of clouds, can run CernVM cloud agents that will communicate with these clouds using their interfaces, and then use one single interface to deploy and scale CernVM clusters. CernVM clusters are defined in CernVM Online and consist of a set of CernVM instances that are contextualized and can communicate with each other.
Securing vehicle communication systems by the KLJN key exchange protocol
Venue: arXiv cs.CR 2014
Year: 2014

We review the security requirements for vehicular communication networks and provide a critical assessment of some typical communication security solutions. We also propose a novel unconditionally secure vehicular communication architecture that utilizes the Kirchhoff-law-Johnson-noise (KLJN) key distribution scheme.
Fair channel allocation and access design for cognitive ad hoc networks
Venue: arXiv cs.NI 2014
Year: 2014

We investigate the fair channel assignment and access design problem for cognitive radio ad hoc network in this paper. In particular, we consider a scenario where ad hoc network nodes have hardware constraints which allow them to access at most one channel at any time. We investigate a fair channel allocation problem where each node is allocated a subset of channels which are sensed and accessed periodically by their owners by using a MAC protocol. Toward this end, we analyze the complexity of the optimal brute-force search algorithm which finds the optimal solution for this NP-hard problem. We then develop low-complexity algorithms that can work efficiently with a MAC protocol algorithm, which resolves the access contention from neighboring secondary nodes. Also, we develop a throughput analytical model, which is used in the proposed channel allocation algorithm and for performance evaluation of its performance. Finally, we present extensive numerical results to demonstrate the efficacy of the proposed algorithms in achieving fair spectrum sharing among traffic flows in the network.
Possibilistic Information Flow Control for Workflow Management Systems
Venue: arXiv cs.CR 2014
Year: 2014

In workflows and business processes, there are often security requirements on both the data, i.e. confidentiality and integrity, and the process, e.g. separation of duty. Graphical notations exist for specifying both workflows and associated security requirements. We present an approach for formally verifying that a workflow satisfies such security requirements. For this purpose, we define the semantics of a workflow as a state-event system and formalise security properties in a trace-based way, i.e. on an abstract level without depending on details of enforcement mechanisms such as Role-Based Access Control (RBAC). This formal model then allows us to build upon well-known verification techniques for information flow control. We describe how a compositional verification methodology for possibilistic information flow can be adapted to verify that a specification of a distributed workflow management system satisfies security requirements on both data and processes.
Extracting a bilingual semantic grammar from FrameNet-annotated corpora
Venue: arXiv cs.CL 2014
Year: 2014

We present the creation of an English-Swedish FrameNet-based grammar in Grammatical Framework. The aim of this research is to make existing framenets computationally accessible for multilingual natural language applications via a common semantic grammar API, and to facilitate the porting of such grammar to other languages. In this paper, we describe the abstract syntax of the semantic grammar while focusing on its automatic extraction possibilities. We have extracted a shared abstract syntax from ~58,500 annotated sentences in Berkeley FrameNet (BFN) and ~3,500 annotated sentences in Swedish FrameNet (SweFN). The abstract syntax defines 769 frame-specific valence patterns that cover 77.8% examples in BFN and 74.9% in SweFN belonging to the shared set of 471 frames. As a side result, we provide a unified method for comparing semantic and syntactic valence patterns across framenets.
Efficient Optimal Algorithm of Task Scheduling in Cloud Computing Environment
Venue: arXiv cs.DC 2014
Year: 2014

Cloud computing is an emerging technology in distributed computing which facilitates pay per model as per user demand and requirement.Cloud consist of a collection of virtual machine which includes both computational and storage facility. The primary aim of cloud computing is to provide efficient access to remote and geographically distributed resources. Cloud is developing day by day and faces many challenges, one of them is scheduling. Scheduling refers to a set of policies to control the order of work to be performed by a computer system. A good scheduler adapts its scheduling strategy according to the changing environment and the type of task. In this research paper we presented a Generalized Priority algorithm for efficient execution of task and comparison with FCFS and Round Robin Scheduling. Algorithm should be tested in cloud Sim toolkit and result shows that it gives better performance compared to other traditional scheduling algorithm.
Rational Counterfactuals
Venue: arXiv cs.AI 2014
Year: 2014

This paper introduces the concept of rational countefactuals which is an idea of identifying a counterfactual from the factual (whether perceived or real) that maximizes the attainment of the desired consequent. In counterfactual thinking if we have a factual statement like: Saddam Hussein invaded Kuwait and consequently George Bush declared war on Iraq then its counterfactuals is: If Saddam Hussein did not invade Kuwait then George Bush would not have declared war on Iraq. The theory of rational counterfactuals is applied to identify the antecedent that gives the desired consequent necessary for rational decision making. The rational countefactual theory is applied to identify the values of variables Allies, Contingency, Distance, Major Power, Capability, Democracy, as well as Economic Interdependency that gives the desired consequent Peace.
Sampling-based Roadmap Planners are Probably Near-Optimal after Finite Computation
Venue: arXiv cs.RO 2014
Year: 2014

Sampling-based motion planners have proven to be efficient solutions to a variety of high-dimensional, geometrically complex motion planning problems with applications in several domains. The traditional view of these approaches is that they solve challenges efficiently by giving up formal guarantees and instead attain asymptotic properties in terms of completeness and optimality. Recent work has argued based on Monte Carlo experiments that these approaches also exhibit desirable probabilistic properties in terms of completeness and optimality after finite computation. The current paper formalizes these guarantees. It proves a formal bound on the probability that solutions returned by asymptotically optimal roadmap-based methods (e.g., PRM*) are within a bound of the optimal path length I* with clearance ε after a finite iteration n. This bound has the form P(|In - I* | {\leq} δI*) {\leq} Psuccess, where δ is an error term for the length a path in the PRM* graph, In. This bound is proven for general dimension Euclidean spaces and evaluated in simulation. A discussion on how this bound can be used in practice, as well as bounds for sparse roadmaps are also provided.
Synchronous replication of remote storage
Venue: arXiv cs.NI 2014
Year: 2014

Storage replication is one of the essential requirements for network environments. While many forms of Network Attached Storage (NAS), Storage Area Networks (SAN) and other forms of network storage exist, there is a need for a reliable synchronous storage replication technique between distant sites (less than 1 mile). Such technology allows setting new standards for network failover and failback systems for virtual servers; specifically, addressing the growing need for effective disaster recovery (DR) planning. The purpose of this manuscript is to identify newest technologies such as SAN/iQ and Storage VMotion that allow for remote storage synchronous replication for virtual servers. This study provides an analysis and a comparison of various SANs that create solutions for enterprise needs. Additionally, the interoperability of these technologies with the industry s leading product VMware ESX Server will be discussed.
Resource-Constrained Adaptive Search and Tracking for Sparse Dynamic Targets
Venue: arXiv cs.IT 2014
Year: 2014

This paper considers the problem of resource-constrained and noise-limited localization and estimation of dynamic targets that are sparsely distributed over a large area. We generalize an existing framework [Bashan et al, 2008] for adaptive allocation of sensing resources to the dynamic case, accounting for time-varying target behavior such as transitions to neighboring cells and varying amplitudes over a potentially long time horizon. The proposed adaptive sensing policy is driven by minimization of a modified version of the previously introduced ARAP objective function, which is a surrogate function for mean squared error within locations containing targets. We provide theoretical upper bounds on the performance of adaptive sensing policies by analyzing solutions with oracle knowledge of target locations, gaining insight into the effect of target motion and amplitude variation as well as sparsity. Exact minimization of the multi-stage objective function is infeasible, but myopic optimization yields a closed-form solution. We propose a simple non-myopic extension, the Dynamic Adaptive Resource Allocation Policy (D-ARAP), that allocates a fraction of resources for exploring all locations rather than solely exploiting the current belief state. Our numerical studies indicate that D-ARAP has the following advantages: (a) it is more robust than the myopic policy to noise, missing data, and model mismatch; (b) it performs comparably to well-known approximate dynamic programming solutions but at significantly lower computational complexity; and (c) it improves greatly upon non-adaptive uniform resource allocation in terms of estimation error and probability of detection.
A Novel Anonymous Cloud Architecture Design; Providing Secure Online Services and Electronic Payments
Venue: arXiv cs.CR 2014
Year: 2014

Anonymous cloud architecture provides secure environment for business and also e-commerce approaches. By using this type of architecture, we can propose anonymous online applications. Customers who need secure and reliable online services should pay for provided services. A big problem is electronic payment that is needed for billing customers. But customer identity should be remained anonymous during and also after payment procedure. In this paper we propose a novel and modified anonymous architecture that ensures customers that hide their identity from others. This architecture is used from common network protocols and we eliminate Tor anonymous service from architecture design space because of independency. The here is introduced scalability parameter in anonymous cloud architecture design space. After all we compare proposed architecture with other popular cloud architectures in this range and we obtain its advantages according to efficiency, security and anonymity.
Improving soft FEC performance for higher-order modulations via optimized bit channel mappings
Venue: arXiv cs.IT 2014
Year: 2014

Soft forward error correction with higher-order modulations is often implemented in practice via the pragmatic bit-interleaved coded modulation paradigm, where a single binary code is mapped to a nonbinary modulation. In this paper, we study the optimization of the mapping of the coded bits to the modulation bits for a polarization-multiplexed fiber-optical system without optical inline dispersion compensation. Our focus is on protograph-based low-density parity-check (LDPC) codes which allow for an efficient hardware implementation, suitable for high-speed optical communications. The optimization is applied to the AR4JA protograph family, and further extended to protograph-based spatially coupled LDPC codes assuming a windowed decoder. Full field simulations via the split-step Fourier method are used to verify the analysis. The results show performance gains of up to 0.25 dB, which translate into a possible extension of the transmission reach by roughly up to 8%, without significantly increasing the system complexity.
TARDIS: Stably shifting traffic in space and time (extended version)
Venue: arXiv cs.NI 2014
Year: 2014

This paper describes TARDIS (Traffic Assignment and Retiming Dynamics with Inherent Stability) which is an algorithmic procedure designed to reallocate traffic within Internet Service Provider (ISP) networks. Recent work has investigated the idea of shifting traffic in time (from peak to off-peak) or in space (by using different links). This work gives a unified scheme for both time and space shifting to reduce costs. Particular attention is given to the commonly used 95th percentile pricing scheme. The work has three main innovations: firstly, introducing the Shapley Gradient, a way of comparing traffic pricing between different links at different times of day; secondly, a unified way of reallocating traffic in time and/or in space; thirdly, a continuous approximation to this system is proved to be stable. A trace-driven investigation using data from two service providers shows that the algorithm can create large savings in transit costs even when only small proportions of the traffic can be shifted.
Wireless Transmission of Video for Biomechanical Analysis
Venue: arXiv cs.CE 2014
Year: 2014

When there is a possibility to wirelessly stream video over a network, a sophisticated computer analysis of the transmitted video is possible. Such process is used in biomechanics when it is important to analyze athletes performance via streaming digital uncompressed video to a computer and then analyzing it using specific software such as Arial Performance Analysis Systems or Dartfish. This manuscript presents some approaches and challenges in streaming video as well as some applications of Information Technology in biomechanics. An example of how scientists from Indiana State University approached the wireless transmission of video is also introduced.
Multiple Access Analog Fountain Codes
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we propose a novel rateless multiple access scheme based on the recently proposed capacity-approaching analog fountain code (AFC). We show that the multiple access process will create an equivalent analog fountain code, referred to as the multiple access analog fountain code (MA-AFC), at the destination. Thus, the standard belief propagation (BP) decoder can be effectively used to jointly decode all the users. We further analyse the asymptotic performance of the BP decoder by using a density evolution approach and show that the average log-likelihood ratio (LLR) of each user's information symbol is proportional to its transmit signal to noise ratio (SNR), when all the users utilize the same AFC code. Simulation results show that the proposed scheme can approach the sum-rate capacity of the Gaussian multiple access channel in a wide range of signal to noise ratios.
Frugal Online Incentive Mechanisms for Crowdsourcing Tasks Truthfully
Venue: arXiv cs.GT 2014
Year: 2014

Mobile Crowd Sensing (MCS) is a new paradigm which takes advantage of pervasive smartphones to efficiently collect data, enabling numerous novel applications. To achieve good service quality for a MCS application, incentive mechanisms are necessary to attract more user participation. Most of existing mechanisms apply only for the offline scenario where all users' information are known a priori. On the contrary, we focus on a more realistic scenario where users arrive one by one online in a random order. Based on the online auction model, we investigate the problem that users submit their private profiles to the crowdsourcer when they arrive, and the crowdsourcer aims at selecting a subset of users before a specified deadline for minimizing the total payment while a specific number of tasks can be completed.We design three online mechanisms, Homo-OMZ, Hetero-OMZ and Hetero-OMG, all of which can satisfy the computational efficiency, individual rationality, cost-truthfulness, and consumer sovereignty. The Homo-OMZ mechanism is applicable to the homogeneous user model and can satisfy the social efficiency but not constant frugality. The Hetero-OMZ and Hetero-OMG mechanisms are applicable to both the homogeneous and heterogeneous user models, and can satisfy the constant frugality. Besides, the Hetero-OMG mechanism can also satisfy the time-truthfulness. Through extensive simulations, we evaluate the performance and validate the theoretical properties of our online mechanisms.
MIMO MAC-BC Duality with Linear-Feedback Coding Schemes
Venue: arXiv cs.IT 2014
Year: 2014

We show that for the multi-antenna Gaussian multi-access channel (MAC) and broadcast channel (BC) with perfect feedback, the rate regions achieved by linear-feedback coding schemes (called linear-feedback capacity regions) coincide when the same total input-power constraint is imposed on both channels and when the MAC channel matrices are the transposes of the BC channel matrices. Such a pair of MAC and BC is called dual. We also identify sub-classes of linear-feedback coding schemes that achieve the linear-feedback capacity regions of these two channels and present multi-letter expressions for the linear-feedback capacity regions. Moreover, within the two sub-classes of coding schemes that achieve the linear-feedback capacity regions for a given MAC and its dual BC, we identify for each MAC scheme a BC scheme and for each BC scheme a MAC scheme so that the two schemes have same total input power and achieve the same rate regions.