OpenRaiser/Intern-Atlas huggingface dataset:
Building Better Incentives for Robustness in BitTorrent
Venue: arXiv cs.GT 2011
Year: 2011

BitTorrent is a widely-deployed, peer-to-peer file transfer protocol engineered with a "tit for tat" mechanism that encourages cooperation. Unfortunately, there is little incentive for nodes to altruistically provide service to their peers after they finish downloading a file, and what altruism there is can be exploited by aggressive clients like Bit- Tyrant. This altruism, called seeding, is always beneficial and sometimes essential to BitTorrent's real-world performance. We propose a new long-term incentives mechanism in BitTorrent to encourage peers to seed and we evaluate its effectiveness via simulation. We show that when nodes running our algorithm reward one another for good behavior in previous swarms, they experience as much as a 50% improvement in download times over unrewarded nodes. Even when aggressive clients, such as BitTyrant, participate in the swarm, our rewarded nodes still outperform them, although by smaller margins.
The Meaning of Structure in Interconnected Dynamic Systems
Venue: arXiv cs.SY 2011
Year: 2011

Interconnected dynamic systems are a pervasive component of our modern infrastructures. The complexity of such systems can be staggering, which motivates simplified representations for their manipulation and analysis. This work introduces the complete computational structure of a system as a common baseline for comparing different simplified representations. Linear systems are then used as a vehicle for comparing and contrasting distinct partial structure representations. Such representations simplify the description of a system's complete computational structure at various levels of fidelity while retaining a full description of the system's input-output dynamic behavior. Relationships between these various partial structure representations are detailed, and the landscape of new realization, minimality, and model reduction problems introduced by these representations is briefly surveyed.
Weighted reciprocity in human communication networks
Venue: arXiv cs.SI 2011
Year: 2011

In this paper we define a metric for reciprocity---the degree of balance in a social relationship---appropriate for weighted social networks in order to investigate the distribution of this dyadic feature in a large-scale system built from trace-logs of over a billion cell-phone communication events across millions of actors. We find that dyadic relations in this network are characterized by much larger degrees of imbalance than we would expect if persons kept only those relationships that exhibited close to full reciprocity. We point to two structural features of human communication behavior and relationship formation---the division of contacts into strong and weak ties and the tendency to form relationships with similar others---that either help or hinder the ability of persons to obtain communicative balance in their relationships. We examine the extent to which deviations from reciprocity in the observed network are partially traceable to these characteristics.
Formal Component-Based Semantics
Venue: arXiv cs.LO 2011
Year: 2011

One of the proposed solutions for improving the scalability of semantics of programming languages is Component-Based Semantics, introduced by Peter D. Mosses. It is expected that this framework can also be used effectively for modular meta theoretic reasoning. This paper presents a formalization of Component-Based Semantics in the theorem prover Coq. It is based on Modular SOS, a variant of SOS, and makes essential use of dependent types, while profiting from type classes. This formalization constitutes a contribution towards modular meta theoretic formalizations in theorem provers. As a small example, a modular proof of determinism of a mini-language is developed.
An Optimal Control Approach for the Persistent Monitoring Problem
Venue: arXiv cs.SY 2011
Year: 2011

We propose an optimal control framework for persistent monitoring problems where the objective is to control the movement of mobile agents to minimize an uncertainty metric in a given mission space. For a single agent in a one-dimensional space, we show that the optimal solution is obtained in terms of a sequence of switching locations, thus reducing it to a parametric optimization problem. Using Infinitesimal Perturbation Analysis (IPA) we obtain a complete solution through a gradient-based algorithm. We also discuss a receding horizon controller which is capable of obtaining a near-optimal solution on-the-fly. We illustrate our approach with numerical examples.
Revisiting Epistemic Specifications
Venue: arXiv cs.AI 2011
Year: 2011

In 1991, Michael Gelfond introduced the language of epistemic specifications. The goal was to develop tools for modeling problems that require some form of meta-reasoning, that is, reasoning over multiple possible worlds. Despite their relevance to knowledge representation, epistemic specifications have received relatively little attention so far. In this paper, we revisit the formalism of epistemic specification. We offer a new definition of the formalism, propose several semantics (one of which, under syntactic restrictions we assume, turns out to be equivalent to the original semantics by Gelfond), derive some complexity results and, finally, show the effectiveness of the formalism for modeling problems requiring meta-reasoning considered recently by Faber and Woltran. All these results show that epistemic specifications deserve much more attention that has been afforded to them so far.
Patterns for Business-to-consumer E-Commerce Applications
Venue: arXiv cs.SE 2011
Year: 2011

E-commerce is one of the most important web applications. We present here a set of patterns that describe shopping carts, products, catalogue, customer accounts, shipping, and invoices. We combine them in the form of composite patterns, which in turn make up a domain model for business-to-consumer e-commerce. We also indicate how to add security constraints to this model. This domain model can be used as a computation-independent model from which specific applications can be produced using a model-driven architecture approach.
Reversibility in Massive Concurrent Systems
Venue: arXiv cs.DC 2011
Year: 2011

Reversing a (forward) computation history means undoing the history. In concurrent systems, undoing the history is not performed in a deterministic way but in a causally consistent fashion, where states that are reached during a backward computation are states that could have been reached during the computation history by just performing independent actions in a different order.
Petri Nets and Bio-Modelling - and how to benefit from their synergy
Venue: arXiv cs.DC 2011
Year: 2011

In this talk we are concerned with the intrinsic similarities and differences between Petri nets on the one hand, and membrane systems and reaction systems on the other hand.
Modelling of Genetic Regulatory Mechanisms with GReg
Venue: arXiv cs.LO 2011
Year: 2011

Most available tools propose simulation frameworks to study models of biological systems, but simulation only explores a few of the most probable behaviours of the system. On the contrary, techniques such as model checking, coming from IT-systems analysis, explore all the possible behaviours of the modelled systems, thus helping to identify emergent properties. A main drawback from most model checking tools in the life sciences domain is that they take as input a language designed for computer scientists, that is not easily understood by non-expert users. We propose in this article an approach based on DSL. It provides a comprehensible language to describe the system while allowing the use of complex and powerful underlying model checking techniques.
A Novel and Robust Evolution Algorithm for Optimizing Complicated Functions
Venue: arXiv cs.NE 2011
Year: 2011

In this paper, a novel mutation operator of differential evolution algorithm is proposed. A new algorithm called divergence differential evolution algorithm (DDEA) is developed by combining the new mutation operator with divergence operator and assimilation operator (divergence operator divides population, and, assimilation operator combines population), which can detect multiple solutions and robustness in noisy environment. The new algorithm is applied to optimize Michalewicz Function and to track changing of rain-induced-attenuation process. The results based on DDEA are compared with those based on Differential Evolution Algorithm (DEA). It shows that DDEA algorithm gets better results than DEA does in the same premise. The new algorithm is significant for optimizing and tracking the characteristics of MIMO (Multiple Input Multiple Output) channel at millimeter waves.
Secure Lossy Transmission of Vector Gaussian Sources
Venue: arXiv cs.IT 2011
Year: 2011

We study the secure lossy transmission of a vector Gaussian source to a legitimate user in the presence of an eavesdropper, where both the legitimate user and the eavesdropper have vector Gaussian side information. The aim of the transmitter is to describe the source to the legitimate user in a way that the legitimate user can reconstruct the source within a certain distortion level while the eavesdropper is kept ignorant of the source as much as possible as measured by the equivocation. We obtain an outer bound for the rate, equivocation and distortion region of this secure lossy transmission problem. This outer bound is tight when the transmission rate constraint is removed. In other words, we obtain the maximum equivocation at the eavesdropper when the legitimate user needs to reconstruct the source within a fixed distortion level while there is no constraint on the transmission rate. This characterization of the maximum equivocation involves two auxiliary random variables. We show that a non-trivial selection for both random variables may be necessary in general. The necessity of two auxiliary random variables also implies that, in general, Wyner-Ziv coding is suboptimal in the presence of an eavesdropper. In addition, we show that, even when there is no rate constraint on the legitimate link, uncoded transmission (deterministic or stochastic) is suboptimal; the presence of an eavesdropper necessitates the use of a coded scheme to attain the maximum equivocation.
Decode-forward and Compute-forward Coding Schemes for the Two-Way Relay Channel
Venue: arXiv cs.IT 2011
Year: 2011

We consider the full-duplex two-way relay channel with direct link between two users and propose two coding schemes: a partial decode-forward scheme, and a combined decode-forward and compute-forward scheme. Both schemes use rate-splitting and superposition coding at each user and generate codewords for each node independently. When applied to the Gaussian channel, partial decode-forward can strictly increase the rate region over decode-forward, which is opposite to the one-way relay channel. The combined scheme uses superposition coding of both Gaussian and lattice codes to allow the relay to decode the Gaussian parts and compute the lattice parts. This scheme can also achieve new rates and outperform both decode-forward and compute-forward separately. These schemes are steps towards understanding the optimal coding.
Bounded Parikh Automata
Venue: arXiv cs.FL 2011
Year: 2011

The Parikh finite word automaton model (PA) was introduced and studied by Klaedtke and Ruess in 2003. Here, by means of related models, it is shown that the bounded languages recognized by PA are the same as those recognized by deterministic PA. Moreover, this class of languages is the class of bounded languages whose set of iterations is semilinear.
The complexity of tangent words
Venue: arXiv cs.DM 2011
Year: 2011

In a previous paper, we described the set of words that appear in the coding of smooth (resp. analytic) curves at arbitrary small scale. The aim of this paper is to compute the complexity of those languages.
On the Delone property of (-β)-integers
Venue: arXiv cs.FL 2011
Year: 2011

The (-β)-integers are natural generalisations of the β-integers, and thus of the integers, for negative real bases. They can be described by infinite words which are fixed points of anti-morphisms. We show that they are not necessarily uniformly discrete and relatively dense in the real numbers.
Constructing minimal phylogenetic networks from softwired clusters is fixed parameter tractable
Venue: arXiv cs.CC 2011
Year: 2011

Here we show that, given a set of clusters C on a set of taxa X, where |X|=n, it is possible to determine in time f(k).poly(n) whether there exists a level-<= k network (i.e. a network where each biconnected component has reticulation number at most k) that represents all the clusters in C in the softwired sense, and if so to construct such a network. This extends a polynomial time result from "On the elusiveness of clusters" by Kelk, Scornavacca and Van Iersel(2011). By generalizing the concept of "level-k generator" to general networks, we then extend this fixed parameter tractability result to the problem where k refers not to the level but to the reticulation number of the whole network.
Identifying Design Requirements for Wireless Routing Link Metrics
Venue: arXiv cs.NI 2011
Year: 2011

In this paper, we identify and analyze the requirements to design a new routing link metric for wireless multihop networks. Considering these requirements, when a link metric is proposed, then both the design and implementation of the link metric with a routing protocol become easy. Secondly, the underlying network issues can easily be tackled. Thirdly, an appreciable performance of the network is guaranteed. Along with the existing implementation of three link metrics Expected Transmission Count (ETX), Minimum Delay (MD), and Minimum Loss (ML), we implement inverse ETX; invETX with Optimized Link State Routing (OLSR) using NS-2.34. The simulation results show that how the computational burden of a metric degrades the performance of the respective protocol and how a metric has to trade-off between different performance parameters.
On Distribution Preserving Quantization
Venue: arXiv cs.IT 2011
Year: 2011

Upon compressing perceptually relevant signals, conventional quantization generally results in unnatural outcomes at low rates. We propose distribution preserving quantization (DPQ) to solve this problem. DPQ is a new quantization concept that confines the probability space of the reconstruction to be identical to that of the source. A distinctive feature of DPQ is that it facilitates a seamless transition between signal synthesis and quantization. A theoretical analysis of DPQ leads to a distribution preserving rate-distortion function (DP-RDF), which serves as a lower bound on the rate of any DPQ scheme, under a constraint on distortion. In general situations, the DP-RDF approaches the classic rate-distortion function for the same source and distortion measure, in the limit of an increasing rate. A practical DPQ scheme based on a multivariate transformation is also proposed. This scheme asymptotically achieves the DP-RDF for i.i.d. Gaussian sources and the mean squared error.
Hamming Weights in Irreducible Cyclic Codes
Venue: arXiv cs.IT 2011
Year: 2011

Irreducible cyclic codes are an interesting type of codes and have applications in space communications. They have been studied for decades and a lot of progress has been made. The objectives of this paper are to survey and extend earlier results on the weight distributions of irreducible cyclic codes, present a divisibility theorem and develop bounds on the weights in irreducible cyclic codes.
City on the Sky: Flexible, Secure Data Sharing on the Cloud
Venue: arXiv cs.DB 2011
Year: 2011

Sharing data from various sources and of diverse kinds, and fusing them together for sophisticated analytics and mash-up applications are emerging trends, and are prerequisites for grand visions such as that of cyber-physical systems enabled smart cities. Cloud infrastructure can enable such data sharing both because it can scale easily to an arbitrary volume of data and computation needs on demand, as well as because of natural collocation of diverse such data sets within the infrastructure. However, in order to convince data owners that their data are well protected while being shared among cloud users, the cloud platform needs to provide flexible mechanisms for the users to express the constraints (access rules) subject to which the data should be shared, and likewise, enforce them effectively. We study a comprehensive set of practical scenarios where data sharing needs to be enforced by methods such as aggregation, windowed frame, value constrains, etc., and observe that existing basic access control mechanisms do not provide adequate flexibility to enable effective data sharing in a secure and controlled manner. In this paper, we thus propose a framework for cloud that extends popular XACML model significantly by integrating flexible access control decisions and data access in a seamless fashion. We have prototyped the framework and deployed it on commercial cloud environment for experimental runs to test the efficacy of our approach and evaluate the performance of the implemented prototype.
Extracting, Transforming and Archiving Scientific Data
Venue: arXiv cs.DL 2011
Year: 2011

It is becoming common to archive research datasets that are not only large but also numerous. In addition, their corresponding metadata and the software required to analyse or display them need to be archived. Yet the manual curation of research data can be difficult and expensive, particularly in very large digital repositories, hence the importance of models and tools for automating digital curation tasks. The automation of these tasks faces three major challenges: (1) research data and data sources are highly heterogeneous, (2) future research needs are difficult to anticipate, (3) data is hard to index. To address these problems, we propose the Extract, Transform and Archive (ETA) model for managing and mechanizing the curation of research data. Specifically, we propose a scalable strategy for addressing the research-data problem, ranging from the extraction of legacy data to its long-term storage. We review some existing solutions and propose novel avenues of research.
Weakness in a Mutual Authentication Scheme for Session Initiation Protocol using Elliptic Curve Cryptography
Venue: arXiv cs.CR 2011
Year: 2011

The session initiation protocol (SIP) is a powerful signaling protocol that controls communication on the Internet, establishing, maintaining, and terminating the sessions. The services that are enabled by SIP are equally applicable in the world of mobile and ubiquitous computing. In 2009, Tsai proposed an authenticated key agreement scheme as an enhancement to SIP. Very recently, Arshad et al. demonstrated that Tsai's scheme was vulnerable to offline password guessing attack and stolen-verifier attack. They also pointed that Tsai's scheme did not provide known-key secrecy and perfect forward secrecy. In order to overcome the weaknesses, Arshad et al. also proposed an improved mutual authentication scheme based on elliptic curve discrete logarithm problem for SIP and claimed that their scheme can withstand various attacks. In this paper, we do a cryptanalysis of Arshad et al.'s scheme and show that Arshad et al.'s scheme is vulnerable to the password guessing attack.
Comparison Of The Consumption Of Resources Between HTTP And SIP
Venue: arXiv cs.NI 2011
Year: 2011

Currently, the development of research around VoIP experience a tremendous growth. In the community of open source Asterisk represents a reliable alternative for a lower cost solution. In this same community as the SIP protocol is a supplement to the more asterisk PBX. to share the benefits claimed by proponents of free software co-existence with other Asterisk server is not yet proven. In this context this paper we show a comparison of the use of simplified resource material for the apache server using the HTTP protocol and server that uses the asterisk SIP.
Why is language well-designed for communication? (Commentary on Christiansen and Chater: 'Language as shaped by the brain')
Venue: arXiv cs.CL 2011
Year: 2011

Selection through iterated learning explains no more than other non-functional accounts, such as universal grammar, why language is so well-designed for communicative efficiency. It does not predict several distinctive features of language like central embedding, large lexicons or the lack of iconicity, that seem to serve communication purposes at the expense of learnability.
Lagrangian Relaxation Applied to Sparse Global Network Alignment
Venue: arXiv cs.DS 2011
Year: 2011

Data on molecular interactions is increasing at a tremendous pace, while the development of solid methods for analyzing this network data is lagging behind. This holds in particular for the field of comparative network analysis, where one wants to identify commonalities between biological networks. Since biological functionality primarily operates at the network level, there is a clear need for topology-aware comparison methods. In this paper we present a method for global network alignment that is fast and robust, and can flexibly deal with various scoring schemes taking both node-to-node correspondences as well as network topologies into account. It is based on an integer linear programming formulation, generalizing the well-studied quadratic assignment problem. We obtain strong upper and lower bounds for the problem by improving a Lagrangian relaxation approach and introduce the software tool natalie 2.0, a publicly available implementation of our method. In an extensive computational study on protein interaction networks for six different species, we find that our new method outperforms alternative state-of-the-art methods with respect to quality and running time.
SNF Project Locomotion: Final report 2009-2010
Venue: arXiv cs.RO 2011
Year: 2011

Summary of results in last project period (1. 10. 2009 - 30. 9. 2010) of SNFS Project "From locomotion to cognition" The research that we have been involved in, and will continue to do, starts from the insight that in order to understand and design intelligent behavior, we must adopt an embodied perspective, i.e. we must take the entire agent, including its shape or morphology, the materials out of which it is built, and its interaction with the environment into account, in addition to the neural control. A lot of our research in the past has been on relatively low-level sensory-motor tasks such as locomotion (e.g. walking, running, jumping), navigation, and grasping. While this research is of interest in itself, in the context of artificial intelligence and cognitive science, this leads to the question of what these kinds of tasks have to do with higher levels of cognition, or to put it more provocatively, "What does walking have to do with thinking?" This question is of course reminiscent of the notorious "symbol grounding problem". In contrast to most of the research on symbol grounding, we propose to exploit the dynamic interaction between the embodied agent and the environment as the basis for grounding. We use the term "morphological computation" to designate the fact that some of the control or computation can be taken over by the dynamic interaction derived from morphological properties (e.g. the passive forward swing of the leg in walking, the spring-like properties of the muscles, and the weight distribution). By taking morphological computation into account, an agent will be able to achieve not only faster, more robust, and more energy-efficient behavior, but also more situated exploration by the agent for the comprehensive understanding of the environment.
Information Flow Safety in Multiparty Sessions
Venue: arXiv cs.CR 2011
Year: 2011

We consider a calculus for multiparty sessions enriched with security levels for messages. We propose a monitored semantics for this calculus, which blocks the execution of processes as soon as they attempt to leak information. We illustrate the use of our monitored semantics with various examples, and show that the induced safety property implies a noninterference property studied previously.