OpenRaiser/Intern-Atlas huggingface dataset:
Toward Governance of Cross-Cloud Application Deployment
Venue: arXiv cs.DC 2012
Year: 2012

In this article, the authors introduce the main ideas around the governance of cross-Cloud application deployment and their related concepts. It is argued that, due to the increasing complexity and nature of the Cloud market, an intermediary specialized in brokering the deployment of different components of a same application onto different Cloud products could both facilitate said deployment and in some cases improve its quality in terms of cost, security & reliability and QoS. In order to fulfill these objectives, the authors propose a high level architecture that relies on their previous work on governance of policy & rule driven distributed systems. This architecture aims at supplying five main functions of 1) translation of Service Level Agreements (SLAs) and pricing into a common shared DSL, 2) correlation of analytical data (e.g. monitoring, metering), 3) combination of Cloud products, 4) information from third parties regarding different aspects of Quality of Service (QoS) and 5) cross-Cloud application deployment specification and governance.
Finitely presented monoids with linear Dehn function need not have regular cross-sections
Venue: arXiv cs.FL 2012
Year: 2012

This paper shows that a finitely presented monoid with linear Dehn function need not have a regular cross-section, strengthening the previously-known result that such a monoid need not be presented by a finite complete string rewriting system, and contrasting the fact that finitely presented groups with linear Dehn function always have regular cross-sections.
Towards Electronic Shopping of Composite Product
Venue: arXiv cs.SE 2012
Year: 2012

In the paper, frameworks for electronic shopping of composite (modular) products are described: (a) multicriteria selection (product is considered as a whole system, it is a traditional approach), (b) combinatorial synthesis (composition) of the product from its components, (c) aggregation of the product from several selected products/prototypes. The following product model is examined: (i) general tree-like structure, (ii) set of system parts/components (leaf nodes), (iii) design alternatives (DAs) for each component, (iv) ordinal priorities for DAs, and (v) estimates of compatibility between DAs for different components. The combinatorial synthesis is realized as morphological design of a composite (modular) product or an extended composite product (e.g., product and support services as financial instruments). Here the solving process is based on Hierarchical Morphological Multicriteria Design (HMMD): (i) multicriteria selection of alternatives for system parts, (ii) composing the selected alternatives into a resultant combination (while taking into account ordinal quality of the alternatives above and their compatibility). The aggregation framework is based on consideration of aggregation procedures, for example: (i) addition procedure: design of a products substructure or an extended substructure ('kernel') and addition of elements, and (ii) design procedure: design of the composite solution based on all elements of product superstructure. Applied numerical examples (e.g., composite product, extended composite product, product repair plan, and product trajectory) illustrate the proposed approaches.
On the Role of Vehicular Mobility in Cooperative Content Caching
Venue: arXiv cs.NI 2012
Year: 2012

In this paper, we analyze the performance of cooperative content caching in vehicular ad hoc networks (VANETs). In particular, we characterize, using analysis and simulations, the behavior of the probability of outage (i.e. not finding a requested data chunk at a neighbor) under freeway vehicular mobility. First, we introduce a formal definition for the probability of outage in the context of cooperative content caching. Second, we characterize, analytically, the outage probability under vehicular and random mobility scenarios. Next, we verify the analytical results using simulations and compare the performance under a number of plausible mobility scenarios. This provides key insights into the problem and the involved trade-offs and enable us to assess the potential opportunity offered by the, somewhat structured, vehicular mobility that can be exploited by cooperative content caching schemes. The presented numerical results exhibit complete agreement between the analytical and simulation studies. Finally, we observe that vehicular mobility creates opportunities for enhanced outage performance under practically relevant scenarios.
The maximum number of minimal codewords in an $[n,k]-$code
Venue: arXiv cs.IT 2012
Year: 2012

Upper and lower bounds are derived for the quantity in the title, which is tabulated for modest values of $n$ and $k.$ An application to graphs with many cycles is given.
Resource Availability-Aware Advance Reservation for Parallel Jobs with Deadlines
Venue: arXiv cs.DC 2012
Year: 2012

Advance reservation is important to guarantee the quality of services of jobs by allowing exclusive access to resources over a defined time interval on resources. It is a challenge for the scheduler to organize available resources efficiently and to allocate them for parallel AR jobs with deadline constraint appropriately. This paper provides a slot-based data structure to organize available resources of multiprocessor systems in a way that enables efficient search and update operations, and formulates a suite of scheduling policies to allocate resources for dynamically arriving AR requests. The performance of the scheduling algorithms were investigated by simulations with different job sizes and durations, system loads and scheduling flexibilities. Simulation results show that job sizes and durations, system load and the flexibility of scheduling will impact the performance metrics of all the scheduling algorithms, and the PE-Worst-Fit algorithm becomes the best algorithm for the scheduler with the highest acceptance rate of AR requests, and the jobs with the First-Fit algorithm experience the lowest average slowdown. The data structure and scheduling policies can be used to organize and allocate resources for parallel AR jobs with deadline constraint in large-scale computing systems.
A review of EO image information mining
Venue: arXiv cs.IR 2012
Year: 2012

We analyze the state of the art of content-based retrieval in Earth observation image archives focusing on complete systems showing promise for operational implementation. The different paradigms at the basis of the main system families are introduced. The approaches taken are analyzed, focusing in particular on the phases after primitive feature extraction. The solutions envisaged for the issues related to feature simplification and synthesis, indexing, semantic labeling are reviewed. The methodologies for query specification and execution are analyzed.
Modeling the geographical studies with GeoGebra-software
Venue: arXiv cs.CG 2012
Year: 2012

The problem of mathematical modeling in geography is one of the most important strategies in order to establish the evolution and the prevision of geographical phenomena. Models must have a simplified structure, to reflect essential components and must be selective, structured, and suggestive and approximate the reality. Models could be static or dynamic, developed in a theoretical, symbolic, conceptual or mental way, mathematically modeled. The present paper is focused on the virtual model which uses GeoGebra software, free and available at www.geogebra.org, in order to establish new methods of geographical analysis in a dynamic, didactic way.
Can the Eureqa symbolic regression program, computer algebra and numerical analysis help each other?
Venue: arXiv cs.MS 2012
Year: 2012

The Eureqa symbolic regression program has recently received extensive press praise. A representative quote is "There are very clever 'thinking machines' in existence today, such as Watson, the IBM computer that conquered Jeopardy! last year. But next to Eureqa, Watson is merely a glorified search engine." The program was designed to work with noisy experimental data. However, if the data is generated from an expression for which there exists more concise equivalent expressions, sometimes some of the Eureqa results are one or more of those more concise equivalents. If not, perhaps one or more of the returned Eureqa results might be a sufficiently accurate approximation that is more concise than the given expression. Moreover, when there is no known closed form expression, the data points can be generated by numerical methods, enabling Eureqa to find expressions that concisely fit those data points with sufficient accuracy. In contrast to typical regression software, the user does not have to explicitly or implicitly provide a specific expression or class of expressions containiing unknown constants for the software to determine. Is Eureqa useful enough in these regards to provide an additional tool for experimental mathematics, computer algebra users and numerical analysis? Yes if used carefully. Can computer algebra and numerical methods help Eureqa? Definitely.
A Symbolic Approach to the Design of Nonlinear Networked Control Systems
Venue: arXiv cs.SY 2012
Year: 2012

Networked control systems (NCS) are spatially distributed systems where communication among plants, sensors, actuators and controllers occurs in a shared communication network. NCS have been studied for the last ten years and important research results have been obtained. These results are in the area of stability and stabilizability. However, while important, these results must be complemented in different areas to be able to design effective NCS. In this paper we approach the control design of NCS using symbolic (finite) models. Symbolic models are abstract descriptions of continuous systems where one symbol corresponds to an "aggregate" of continuous states. We consider a fairly general multiple-loop network architecture where plants communicate with digital controllers through a shared, non-ideal, communication network characterized by variable sampling and transmission intervals, variable communication delays, quantization errors, packet losses and limited bandwidth. We first derive a procedure to obtain symbolic models that are proven to approximate NCS in the sense of alternating approximate bisimulation. We then use these symbolic models to design symbolic controllers that realize specifications expressed in terms of automata on infinite strings. An example is provided where we address the control design of a pair of nonlinear control systems sharing a common communication network. The closed-loop NCS obtained is validated through the OMNeT++ network simulation framework.
Search Combinators
Venue: arXiv cs.AI 2012
Year: 2012

The ability to model search in a constraint solver can be an essential asset for solving combinatorial problems. However, existing infrastructure for defining search heuristics is often inadequate. Either modeling capabilities are extremely limited or users are faced with a general-purpose programming language whose features are not tailored towards writing search heuristics. As a result, major improvements in performance may remain unexplored. This article introduces search combinators, a lightweight and solver-independent method that bridges the gap between a conceptually simple modeling language for search (high-level, functional and naturally compositional) and an efficient implementation (low-level, imperative and highly non-modular). By allowing the user to define application-tailored search strategies from a small set of primitives, search combinators effectively provide a rich domain-specific language (DSL) for modeling search to the user. Remarkably, this DSL comes at a low implementation cost to the developer of a constraint solver. The article discusses two modular implementation approaches and shows, by empirical evaluation, that search combinators can be implemented without overhead compared to a native, direct implementation in a constraint solver.
Dynamic Packet Scheduling in Wireless Networks
Venue: arXiv cs.NI 2012
Year: 2012

We consider protocols that serve communication requests arising over time in a wireless network that is subject to interference. Unlike previous approaches, we take the geometry of the network and power control into account, both allowing to increase the network's performance significantly. We introduce a stochastic and an adversarial model to bound the packet injection. Although taken as the primary motivation, this approach is not only suitable for models based on the signal-to-interference-plus-noise ratio (SINR). It also covers virtually all other common interference models, for example the multiple-access channel, the radio-network model, the protocol model, and distance-2 matching. Packet-routing networks allowing each edge or each node to transmit or receive one packet at a time can be modeled as well. Starting from algorithms for the respective scheduling problem with static transmission requests, we build distributed stable protocols. This is more involved than in previous, similar approaches because the algorithms we consider do not necessarily scale linearly when scaling the input instance. We can guarantee a throughput that is as large as the one of the original static algorithm. In particular, for SINR models the competitive ratios of the protocol in comparison to optimal ones in the respective model are between constant and O(log^2 m) for a network of size m.
An Exploratory Study of Critical Factors Affecting the Efficiency of Sorting Techniques (Shell, Heap and Treap)
Venue: arXiv cs.DS 2012
Year: 2012

The efficiency of sorting techniques has a significant impact on the overall efficiency of a program. The efficiency of Shell, Heap and Treap sorting techniques in terms of both running time and memory usage was studied, experiments conducted and results subjected to factor analysis by SPSS. The study revealed the main factor affecting these sorting techniques was time taken to sort.
NLSEmagic: Nonlinear Schrödinger Equation Multidimensional Matlab-based GPU-accelerated Integrators using Compact High-order Schemes
Venue: arXiv cs.MS 2012
Year: 2012

We present a simple to use, yet powerful code package called NLSEmagic to numerically integrate the nonlinear Schrödinger equation in one, two, and three dimensions. NLSEmagic is a high-order finite-difference code package which utilizes graphic processing unit (GPU) parallel architectures. The codes running on the GPU are many times faster than their serial counterparts, and are much cheaper to run than on standard parallel clusters. The codes are developed with usability and portability in mind, and therefore are written to interface with MATLAB utilizing custom GPU-enabled C codes with the MEX-compiler interface. The packages are freely distributed, including user manuals and set-up files.
Optimal Use of Current and Outdated Channel State Information - Degrees of Freedom of the MISO BC with Mixed CSIT
Venue: arXiv cs.IT 2012
Year: 2012

We consider a multiple-input-single-output (MISO) broadcast channel with mixed channel state information at the transmitter (CSIT) that consists of imperfect current CSIT and perfect outdated CSIT. Recent work by Kobayashi et al. presented a scheme which exploits both imperfect current CSIT and perfect outdated CSIT and achieves higher degrees of freedom (DoF) than possible with only imperfect current CSIT or only outdated CSIT individually. In this work, we further improve the achievable DoF in this setting by incorporating additional private messages, and provide a tight information theoretic DoF outer bound, thereby identifying the DoF optimal use of mixed CSIT. The new result is stronger even in the original setting of only delayed CSIT, because it allows us to remove the restricting assumption of statistically equivalent fading for all users.
Model based Software Develeopment: Issues & Challenges
Venue: arXiv cs.SE 2012
Year: 2012

One of the goals of software design is to model a system in such a way that it is easily understandable. Nowadays the tendency for software development is changing from manual coding to automatic code generation; it is becoming model-based. This is a response to the software crisis, in which the cost of hardware has decreased and conversely the cost of software development has increased sharply. The methodologies that allowed this change are model-based, thus relieving the human from detailed coding. Still there is a long way to achieve this goal, but work is being done worldwide to achieve this objective. This paper presents the drastic changes related to modeling and important challenging issues and techniques that recur in MBSD.
Region-based memory management for Mercury programs
Venue: arXiv cs.PL 2012
Year: 2012

Region-based memory management (RBMM) is a form of compile time memory management, well-known from the functional programming world. In this paper we describe our work on implementing RBMM for the logic programming language Mercury. One interesting point about Mercury is that it is designed with strong type, mode, and determinism systems. These systems not only provide Mercury programmers with several direct software engineering benefits, such as self-documenting code and clear program logic, but also give language implementors a large amount of information that is useful for program analyses. In this work, we make use of this information to develop program analyses that determine the distribution of data into regions and transform Mercury programs by inserting into them the necessary region operations. We prove the correctness of our program analyses and transformation. To execute the annotated programs, we have implemented runtime support that tackles the two main challenges posed by backtracking. First, backtracking can require regions removed during forward execution to be "resurrected"; and second, any memory allocated during a computation that has been backtracked over must be recovered promptly and without waiting for the regions involved to come to the end of their life. We describe in detail our solution of both these problems. We study in detail how our RBMM system performs on a selection of benchmark programs, including some well-known difficult cases for RBMM. Even with these difficult cases, our RBMM-enabled Mercury system obtains clearly faster runtimes for 15 out of 18 benchmarks compared to the base Mercury system with its Boehm runtime garbage collector, with an average runtime speedup of 24%, and an average reduction in memory requirements of 95%. In fact, our system achieves optimal memory consumption in some programs.
AD in Fortran, Part 2: Implementation via Prepreprocessor
Venue: arXiv cs.PL 2012
Year: 2012

We describe an implementation of the Farfel Fortran AD extensions. These extensions integrate forward and reverse AD directly into the programming model, with attendant benefits to flexibility, modularity, and ease of use. The implementation we describe is a "prepreprocessor" that generates input to existing Fortran-based AD tools. In essence, blocks of code which are targeted for AD by Farfel constructs are put into subprograms which capture their lexical variable context, and these are closure-converted into top-level subprograms and specialized to eliminate EXTERNAL arguments, rendering them amenable to existing AD preprocessors, which are then invoked, possibly repeatedly if the AD is nested.
On the Influence of Informed Agents on Learning and Adaptation over Networks
Venue: arXiv cs.IT 2012
Year: 2012

Adaptive networks consist of a collection of agents with adaptation and learning abilities. The agents interact with each other on a local level and diffuse information across the network through their collaborations. In this work, we consider two types of agents: informed agents and uninformed agents. The former receive new data regularly and perform consultation and in-network tasks, while the latter do not collect data and only participate in the consultation tasks. We examine the performance of adaptive networks as a function of the proportion of informed agents and their distribution in space. The results reveal some interesting and surprising trade-offs between convergence rate and mean-square performance. In particular, among other results, it is shown that the performance of adaptive networks does not necessarily improve with a larger proportion of informed agents. Instead, it is established that the larger the proportion of informed agents is, the faster the convergence rate of the network becomes albeit at the expense of some deterioration in mean-square performance. The results further establish that uninformed agents play an important role in determining the steady-state performance of the network, and that it is preferable to keep some of the highly connected agents uninformed. The arguments reveal an important interplay among three factors: the number and distribution of informed agents in the network, the convergence rate of the learning process, and the estimation accuracy in steady-state. Expressions that quantify these relations are derived, and simulations are included to support the theoretical findings. We further apply the results to two models that are widely used to represent behavior over complex networks, namely, the Erdos-Renyi and scale-free models.
The Complexity of the Puzzles of Final Fantasy XIII-2
Venue: arXiv cs.CC 2012
Year: 2012

We analyze the computational complexity of solving the three "temporal rift" puzzles in the recent popular video game Final Fantasy XIII-2. We show that the Tile Trial puzzle is NP-hard and we provide an efficient algorithm for solving the Crystal Bonds puzzle. We also show that slight generalizations of the Crystal Bonds and Hands of Time puzzles are NP-hard.
A Survey of Prediction Using Social Media
Venue: arXiv cs.SI 2012
Year: 2012

Social media comprises interactive applications and platforms for creating, sharing and exchange of user-generated contents. The past ten years have brought huge growth in social media, especially online social networking services, and it is changing our ways to organize and communicate. It aggregates opinions and feelings of diverse groups of people at low cost. Mining the attributes and contents of social media gives us an opportunity to discover social structure characteristics, analyze action patterns qualitatively and quantitatively, and sometimes the ability to predict future human related events. In this paper, we firstly discuss the realms which can be predicted with current social media, then overview available predictors and techniques of prediction, and finally discuss challenges and possible future directions.
CensorSpoofer: Asymmetric Communication with IP Spoofing for Censorship-Resistant Web Browsing
Venue: arXiv cs.CR 2012
Year: 2012

A key challenge in censorship-resistant web browsing is being able to direct legitimate users to redirection proxies while preventing censors, posing as insiders, from discovering their addresses and blocking them. We propose a new framework for censorship-resistant web browsing called {\it CensorSpoofer} that addresses this challenge by exploiting the asymmetric nature of web browsing traffic and making use of IP spoofing. CensorSpoofer de-couples the upstream and downstream channels, using a low-bandwidth indirect channel for delivering outbound requests (URLs) and a high-bandwidth direct channel for downloading web content. The upstream channel hides the request contents using steganographic encoding within email or instant messages, whereas the downstream channel uses IP address spoofing so that the real address of the proxies is not revealed either to legitimate users or censors. We built a proof-of-concept prototype that uses encrypted VoIP for this downstream channel and demonstrated the feasibility of using the CensorSpoofer framework in a realistic environment.