OpenRaiser/Intern-Atlas huggingface dataset:
Sharp utilization thresholds for some real-time scheduling problems
Venue: arXiv cs.PF 2009
Year: 2009

Scheduling policies for real-time systems exhibit threshold behavior that is related to the utilization of the task set they schedule, and in some cases this threshold is sharp. For the rate monotonic scheduling policy, we show that periodic workload with utilization less than a threshold $U_{RM}^{*}$ can be scheduled almost surely and that all workload with utilization greater than $U_{RM}^{*}$ is almost surely not schedulable. We study such sharp threshold behavior in the context of processor scheduling using static task priorities, not only for periodic real-time tasks but for aperiodic real-time tasks as well. The notion of a utilization threshold provides a simple schedulability test for most real-time applications. These results improve our understanding of scheduling policies and provide an interesting characterization of the typical behavior of policies. The threshold is sharp (small deviations around the threshold cause schedulability, as a property, to appear or disappear) for most policies; this is a happy consequence that can be used to address the limitations of existing utilization-based tests for schedulability. We demonstrate the use of such an approach for balancing power consumption with the need to meet deadlines in web servers.
E-commerce between a large firm and a SME supplier: a screening model
Venue: arXiv cs.GT 2009
Year: 2009

This paper derives a model of screening contracts in the presence of positive network effects when building an electronic commerce network (e-commerce) between a large firm and a small and medium sized enterprise (SME) supplier based on Compte (2008). Compte (2008) main insight is that when several potential candidates compete for the task, the principal will in general improve the performance of his firm by inducing the member candidates to assess their competence before signing the contract (through an appropriate choice of contracts). The large firm (principal) must choose between different SME suppliers (agents) to build a business to business e-commerce network. In the presence of positive network externalities, we show that social surplus increases.
Studies on access: a review
Venue: arXiv cs.DL 2009
Year: 2009

A review of the empirical literature on access to scholarly information. This review focuses on surveys of authors, article download and citation analysis.
Using Design Sketch to Teach Bubble Sort in High School
Venue: arXiv cs.CY 2009
Year: 2009

Bubble Sort is simple. Yet, it seems a bit difficult for high school students. This paper presents a pedagogical methodology: Using Design Sketch to visualize the concepts in Bubble Sort, and to evaluate how this approach assists students to understand the pseudo code of Bubble Sort. An experiment is conducted in Wu-Ling Senior High School with 250 students taking part. The statistical analysis of experimental results shows that, for relatively high abstraction concepts, such as iteration number, Design Sketch helps significantly. However, it is not so for low abstraction concepts such as compare, swap, and iteration.
Performance Analysis of AIM-K-means & K-means in Quality Cluster Generation
Venue: arXiv cs.LG 2009
Year: 2009

Among all the partition based clustering algorithms K-means is the most popular and well known method. It generally shows impressive results even in considerably large data sets. The computational complexity of K-means does not suffer from the size of the data set. The main disadvantage faced in performing this clustering is that the selection of initial means. If the user does not have adequate knowledge about the data set, it may lead to erroneous results. The algorithm Automatic Initialization of Means (AIM), which is an extension to K-means, has been proposed to overcome the problem of initial mean generation. In this paper an attempt has been made to compare the performance of the algorithms through implementation
On the Connectivity and Multihop Delay of Ad Hoc Cognitive Radio Networks
Venue: arXiv cs.NI 2009
Year: 2009

We analyze the multihop delay of ad hoc cognitive radio networks, where the transmission delay of each hop consists of the propagation delay and the waiting time for the availability of the communication channel (i.e., the occurrence of a spectrum opportunity at this hop). Using theories and techniques from continuum percolation and ergodicity, we establish the scaling law of the minimum multihop delay with respect to the source-destination distance in cognitive radio networks. When the propagation delay is negligible, we show the starkly different scaling behavior of the minimum multihop delay in instantaneously connected networks as compared to networks that are only intermittently connected due to scarcity of spectrum opportunities. Specifically, if the network is instantaneously connected, the minimum multihop delay is asymptotically independent of the distance; if the network is only intermittently connected, the minimum multihop delay scales linearly with the distance. When the propagation delay is nonnegligible but small, we show that although the scaling order is always linear, the scaling rate for an instantaneously connected network can be orders of magnitude smaller than the one for an intermittently connected network.
Music-ripping: des pratiques qui provoquent la musicologie
Venue: arXiv cs.MM 2009
Year: 2009

Out of the scope of the usual positions of computing in the field of music and musicology, one notices the emergence of human-computer systems that do exist by breaking off. Though these singular systems take effect in the usual fields of expansion of music, they do not make any systematic reference to known musicological categories. On the contrary, they make possible experiments that open uses where listening, composition and musical transmission get merged in a gesture sometimes named as ?music-ripping?. We will show in which way the music-ripping practices provoke traditional musicology, whose canonical categories happen to be ineffectual to explain here. To achieve that purpose, we shall need: - to make explicit a minimal set of categories that is sufficient to underlie the usual models of computer assisted music;- to do the same for human-computer systems (anti-musicological?) that disturb us; - to examine the possibility conditions of reduction of the second set to the first; - to conclude on the nature of music-ripping.
Elementary Complexity and von Neumann Algebras
Venue: arXiv cs.CC 2009
Year: 2009

In this paper, we show how a construction of an implicit complexity model can be implemented using concepts coming from the core of von Neumann algebras. Namely, our aim is to gain an understanding of classical computation in terms of the hyperfinite $\mathrm{II}_1$ factor, starting from the class of Kalmar recursive functions. More methodologically, we address the problem of finding the right perspective from which to view the new relation between computation and combinatorial aspects in operator algebras. The rich structure of discrete invariants may provide a mathematical setting able to shed light on some basic combinatorial phenomena that are at the basis of our understanding of complexity.
Secure Vehicular Communication Systems: Implementation, Performance, and Research Challenges
Venue: arXiv cs.CR 2009
Year: 2009

Vehicular Communication (VC) systems are on the verge of practical deployment. Nonetheless, their security and privacy protection is one of the problems that have been addressed only recently. In order to show the feasibility of secure VC, certain implementations are required. In [1] we discuss the design of a VC security system that has emerged as a result of the European SeVeCom project. In this second paper, we discuss various issues related to the implementation and deployment aspects of secure VC systems. Moreover, we provide an outlook on open security research issues that will arise as VC systems develop from today's simple prototypes to full-fledged systems.
The Hardness and Approximation Algorithms for L-Diversity
Venue: arXiv cs.DB 2009
Year: 2009

The existing solutions to privacy preserving publication can be classified into the theoretical and heuristic categories. The former guarantees provably low information loss, whereas the latter incurs gigantic loss in the worst case, but is shown empirically to perform well on many real inputs. While numerous heuristic algorithms have been developed to satisfy advanced privacy principles such as l-diversity, t-closeness, etc., the theoretical category is currently limited to k-anonymity which is the earliest principle known to have severe vulnerability to privacy attacks. Motivated by this, we present the first theoretical study on l-diversity, a popular principle that is widely adopted in the literature. First, we show that optimal l-diverse generalization is NP-hard even when there are only 3 distinct sensitive values in the microdata. Then, an (l*d)-approximation algorithm is developed, where d is the dimensionality of the underlying dataset. This is the first known algorithm with a non-trivial bound on information loss. Extensive experiments with real datasets validate the effectiveness and efficiency of proposed solution.
From a Link Semantic to Semantic Links - Building Context in Educational Hypermedia
Venue: arXiv cs.IR 2009
Year: 2009

Modularization and granulation are key concepts in educational content management, whereas teaching, learning and understanding require a discourse within thematic contexts. Even though hyperlinks and semantically typed references provide the context building blocks of hypermedia systems, elaborate concepts to derive, manage and propagate such relations between content objects are not around at present. Based on Semantic Web standards, this paper makes several contributions to content enrichment. Work starts from harvesting multimedia annotations in class-room recordings, and proceeds to deriving a dense educational semantic net between eLearning Objects decorated with extended LOM relations. Special focus is drawn on the processing of recorded speech and on an Ontological Evaluation Layer that autonomously derives meaningful inter-object relations. Further on, a semantic representation of hyperlinks is developed and elaborated to the concept of semantic link contexts, an approach to manage a coherent rhetoric of linking. These solutions have been implemented in the Hypermedia Learning Objects System (hylOs), our eLearning content management system. hylOs is built upon the more general Media Information Repository (MIR) and the MIR adaptive context linking environment (MIRaCLE), its linking extension. MIR is an open system supporting the standards XML and JNDI. hylOs benefits from configurable information structures, sophisticated access logic and high-level authoring tools like the WYSIWYG XML editor and its Instructional Designer.
A general approach to belief change in answer set programming
Venue: arXiv cs.AI 2009
Year: 2009

We address the problem of belief change in (nonmonotonic) logic programming under answer set semantics. Unlike previous approaches to belief change in logic programming, our formal techniques are analogous to those of distance-based belief revision in propositional logic. In developing our results, we build upon the model theory of logic programs furnished by SE models. Since SE models provide a formal, monotonic characterisation of logic programs, we can adapt techniques from the area of belief revision to belief change in logic programs. We introduce methods for revising and merging logic programs, respectively. For the former, we study both subset-based revision as well as cardinality-based revision, and we show that they satisfy the majority of the AGM postulates for revision. For merging, we consider operators following arbitration merging and IC merging, respectively. We also present encodings for computing the revision as well as the merging of logic programs within the same logic programming framework, giving rise to a direct implementation of our approach in terms of off-the-shelf answer set solvers. These encodings reflect in turn the fact that our change operators do not increase the complexity of the base formalism.
Cryptographic Implications for Artificially Mediated Games
Venue: arXiv cs.CR 2009
Year: 2009

There is currently an intersection in the research of game theory and cryptography. Generally speaking, there are two aspects to this partnership. First there is the application of game theory to cryptography. Yet, the purpose of this paper is to focus on the second aspect, the converse of the first, the application of cryptography to game theory. Chiefly, there exist a branch of non-cooperative games which have a correlated equilibrium as their solution. These equilibria tend to be superior to the conventional Nash equilibria. The primary condition for a correlated equilibrium is the presence of a mediator within the game. This is simply a neutral and mutually trusted entity. It is the role of the mediator to make recommendations in terms of strategy profiles to all players, who then act (supposedly) on this advice. Each party privately provides the mediator with the necessary information, and the referee responds privately with their optimized strategy set. However, there seem to be a multitude of situations in which no mediator could exist. Thus, games modeling these sorts of cases could not use these entities as tools for analysis. Yet, if these equilibria are in the best interest of players, it would be rational to construct a machine, or protocol, to calculate them. Of course, this machine would need to satisfy some standard for secure transmission between a player and itself. The requirement that no third party could detect either the input or strategy profile would need to be satisfied by this scheme. Here is the synthesis of cryptography into game theory; analyzing the ability of the players to construct a protocol which can be used successfully in the place of a mediator.
Synchronization Analysis in Physical Layer Network Coding
Venue: arXiv cs.NI 2009
Year: 2009

Physical-layer Network Coding (PNC) makes use of the additive nature of the electromagnetic (EM) waves to apply network coding arithmetic at the physical layer. With PNC,the destructive effect of interference in wireless networks is eliminated and the capacity of networks can be boosted significantly. This paper addresses a key outstanding issue in PNC: synchronization among transmitting nodes. We first investigate the impact of imperfect synchronization (i.e., finite synchronization errors) in a 3-node network. It is shown that with QPSK modulation, PNC still yields significantly higher capacity than straightforward network coding when there are synchronization errors. Significantly, this remains to be so even in the extreme case when synchronization is not performed at all. Moving beyond a 3-node network, we propose and investigate a synchronization scheme for PNC in a general chain network. At last, numerical simulation verifies that PNC is robust to synchronization errors. In particular, for the mutual information performance, there is about 0.5dB loss without time synchronization and there is at most 2dB loss without phase synchronization.
Non-line-of-sight Node Localization based on Semi-Definite Programming in Wireless Sensor Networks
Venue: arXiv cs.IT 2009
Year: 2009

An unknown-position sensor can be localized if there are three or more anchors making time-of-arrival (TOA) measurements of a signal from it. However, the location errors can be very large due to the fact that some of the measurements are from non-line-of-sight (NLOS) paths. In this paper, we propose a semi-definite programming (SDP) based node localization algorithm in NLOS environment for ultra-wideband (UWB) wireless sensor networks. The positions of sensors can be estimated using the distance estimates from location-aware anchors as well as other sensors. However, in the absence of LOS paths, e.g., in indoor networks, the NLOS range estimates can be significantly biased. As a result, the NLOS error can remarkably decrease the location accuracy. And it is not easy to efficiently distinguish LOS from NLOS measurements. In this paper, an algorithm is proposed that achieves high location accuracy without the need of identifying NLOS and LOS measurement.
Undecidability Results for Finite Interactive Systems
Venue: arXiv cs.FL 2009
Year: 2009

A new approach to the design of massively parallel and interactive programming languages has been recently proposed using rv-systems (interactive systems with registers and voices) and Agapia programming. In this paper we present a few theoretical results on FISs (finite interactive systems), the underlying mechanism used for specifying control and interaction in these systems. First, we give a proof for the undecidability of the emptiness problem for FISs, by reduction to the Post Correspondence Problem. Next, we use the construction in this proof to get other undecidability results, e.g., for the accessibility of a transition in a FIS, or for the finiteness of the language recognized by a FIS. Finally, we present a simple proof of the equivalence between FISs and tile systems, making explicit that they precisely capture recognizable two-dimensional languages.
Position Modulation Code for Rewriting Write-Once Memories
Venue: arXiv cs.IT 2009
Year: 2009

A write-once memory (wom) is a storage medium formed by a number of ``write-once'' bit positions (wits), where each wit initially is in a `0' state and can be changed to a `1' state irreversibly. Examples of write-once memories include SLC flash memories and optical disks. This paper presents a low complexity coding scheme for rewriting such write-once memories, which is applicable to general problem configurations. The proposed scheme is called the \emph{position modulation code}, as it uses the positions of the zero symbols to encode some information. The proposed technique can achieve code rates higher than state-of-the-art practical solutions for some configurations. For instance, there is a position modulation code that can write 56 bits 10 times on 278 wits, achieving rate 2.01. In addition, the position modulation code is shown to achieve a rate at least half of the optimal rate.
Polynomial Constraint Satisfaction, Graph Bisection, and the Ising Partition Function
Venue: arXiv cs.DM 2009
Year: 2009

We introduce a problem class we call Polynomial Constraint Satisfaction Problems, or PCSP. Where the usual CSPs from computer science and optimization have real-valued score functions, and partition functions from physics have monomials, PCSP has scores that are arbitrary multivariate formal polynomials, or indeed take values in an arbitrary ring. Although PCSP is much more general than CSP, remarkably, all (exact, exponential-time) algorithms we know of for 2-CSP (where each score depends on at most 2 variables) extend to 2-PCSP, at the expense of just a polynomial factor in running time. Specifically, we extend the reduction-based algorithm of Scott and Sorkin; the specialization of that approach to sparse random instances, where the algorithm runs in polynomial expected time; dynamic-programming algorithms based on tree decompositions; and the split-and-list matrix-multiplication algorithm of Williams. This gives the first polynomial-space exact algorithm more efficient than exhaustive enumeration for the well-studied problems of finding a minimum bisection of a graph, and calculating the partition function of an Ising model, and the most efficient algorithm known for certain instances of Maximum Independent Set. Furthermore, PCSP solves both optimization and counting versions of a wide range of problems, including all CSPs, and thus enables samplers including uniform sampling of optimal solutions and Gibbs sampling of all solutions.
Approximation and Inapproximability Results for Maximum Clique of Disc Graphs in High Dimensions
Venue: arXiv cs.CG 2009
Year: 2009

We prove algorithmic and hardness results for the problem of finding the largest set of a fixed diameter in the Euclidean space. In particular, we prove that if $A^*$ is the largest subset of diameter $r$ of $n$ points in the Euclidean space, then for every $ε>0$ there exists a polynomial time algorithm that outputs a set $B$ of size at least $|A^*|$ and of diameter at most $r(\sqrt{2}+ε)$. On the hardness side, roughly speaking, we show that unless $P=NP$ for every $ε>0$ it is not possible to guarantee the diameter $r(\sqrt{4/3}-ε)$ for $B$ even if the algorithm is allowed to output a set of size $({95\over 94}-ε)^{-1}|A^*|$.
Polygraphic programs and polynomial-time functions
Venue: arXiv cs.LO 2009
Year: 2009

We study the computational model of polygraphs. For that, we consider polygraphic programs, a subclass of these objects, as a formal description of first-order functional programs. We explain their semantics and prove that they form a Turing-complete computational model. Their algebraic structure is used by analysis tools, called polygraphic interpretations, for complexity analysis. In particular, we delineate a subclass of polygraphic programs that compute exactly the functions that are Turing-computable in polynomial time.
DMTCP: Transparent Checkpointing for Cluster Computations and the Desktop
Venue: arXiv cs.DC 2009
Year: 2009

DMTCP (Distributed MultiThreaded CheckPointing) is a transparent user-level checkpointing package for distributed applications. Checkpointing and restart is demonstrated for a wide range of over 20 well known applications, including MATLAB, Python, TightVNC, MPICH2, OpenMPI, and runCMS. RunCMS runs as a 680 MB image in memory that includes 540 dynamic libraries, and is used for the CMS experiment of the Large Hadron Collider at CERN. DMTCP transparently checkpoints general cluster computations consisting of many nodes, processes, and threads; as well as typical desktop applications. On 128 distributed cores (32 nodes), checkpoint and restart times are typically 2 seconds, with negligible run-time overhead. Typical checkpoint times are reduced to 0.2 seconds when using forked checkpointing. Experimental results show that checkpoint time remains nearly constant as the number of nodes increases on a medium-size cluster. DMTCP automatically accounts for fork, exec, ssh, mutexes/semaphores, TCP/IP sockets, UNIX domain sockets, pipes, ptys (pseudo-terminals), terminal modes, ownership of controlling terminals, signal handlers, open file descriptors, shared open file descriptors, I/O (including the readline library), shared memory (via mmap), parent-child process relationships, pid virtualization, and other operating system artifacts. By emphasizing an unprivileged, user-space approach, compatibility is maintained across Linux kernels from 2.6.9 through the current 2.6.28. Since DMTCP is unprivileged and does not require special kernel modules or kernel patches, DMTCP can be incorporated and distributed as a checkpoint-restart module within some larger package.