OpenRaiser/Intern-Atlas huggingface dataset:
On the intersection of additive perfect codes
Venue: arXiv cs.IT 2006
Year: 2006

The intersection problem for additive (extended and non-extended) perfect codes, i.e. which are the possibilities for the number of codewords in the intersection of two additive codes C1 and C2 of the same length, is investigated. Lower and upper bounds for the intersection number are computed and, for any value between these bounds, codes which have this given intersection value are constructed. For all these codes the abelian group structure of the intersection is characterized. The parameters of this abelian group structure corresponding to the intersection codes are computed and lower and upper bounds for these parameters are established. Finally, constructions of codes the intersection of which fits any parameters between these bounds are given.
Registers
Venue: arXiv cs.DC 2006
Year: 2006

Entry in: Encyclopedia of Algorithms, Ming-Yang Kao, Ed., Springer, To appear. Synonyms: Wait-free registers, wait-free shared variables, asynchronous communication hardware. Problem Definition: Consider a system of asynchronous processes that communicate among themselves by only executing read and write operations on a set of shared variables (also known as shared registers). The system has no global clock or other synchronization primitives.
Predictable Disruption Tolerant Networks and Delivery Guarantees
Venue: arXiv cs.NI 2006
Year: 2006

This article studies disruption tolerant networks (DTNs) where each node knows the probabilistic distribution of contacts with other nodes. It proposes a framework that allows one to formalize the behaviour of such a network. It generalizes extreme cases that have been studied before where (a) either nodes only know their contact frequency with each other or (b) they have a perfect knowledge of who meets who and when. This paper then gives an example of how this framework can be used; it shows how one can find a packet forwarding algorithm optimized to meet the 'delay/bandwidth consumption' trade-off: packets are duplicated so as to (statistically) guarantee a given delay or delivery probability, but not too much so as to reduce the bandwidth, energy, and memory consumption.
Revisiting Matrix Product on Master-Worker Platforms
Venue: arXiv cs.DC 2006
Year: 2006

This paper is aimed at designing efficient parallel matrix-product algorithms for heterogeneous master-worker platforms. While matrix-product is well-understood for homogeneous 2D-arrays of processors (e.g., Cannon algorithm and ScaLAPACK outer product algorithm), there are three key hypotheses that render our work original and innovative: - Centralized data. We assume that all matrix files originate from, and must be returned to, the master. - Heterogeneous star-shaped platforms. We target fully heterogeneous platforms, where computational resources have different computing powers. - Limited memory. Because we investigate the parallelization of large problems, we cannot assume that full matrix panels can be stored in the worker memories and re-used for subsequent updates (as in ScaLAPACK). We have devised efficient algorithms for resource selection (deciding which workers to enroll) and communication ordering (both for input and result messages), and we report a set of numerical experiments on various platforms at Ecole Normale Superieure de Lyon and the University of Tennessee. However, we point out that in this first version of the report, experiments are limited to homogeneous platforms.
Computing the Equilibria of Bimatrix Games using Dominance Heuristics
Venue: arXiv cs.GT 2006
Year: 2006

We propose a formulation of a general-sum bimatrix game as a bipartite directed graph with the objective of establishing a correspondence between the set of the relevant structures of the graph (in particular elementary cycles) and the set of the Nash equilibria of the game. We show that finding the set of elementary cycles of the graph permits the computation of the set of equilibria. For games whose graphs have a sparse adjacency matrix, this serves as a good heuristic for computing the set of equilibria. The heuristic also allows the discarding of sections of the support space that do not yield any equilibrium, thus serving as a useful pre-processing step for algorithms that compute the equilibria through support enumeration.
About the Lifespan of Peer to Peer Networks
Venue: arXiv cs.DC 2006
Year: 2006

We analyze the ability of peer to peer networks to deliver a complete file among the peers. Early on we motivate a broad generalization of network behavior organizing it into one of two successive phases. According to this view the network has two main states: first centralized - few sources (roots) hold the complete file, and next distributed - peers hold some parts (chunks) of the file such that the entire network has the whole file, but no individual has it. In the distributed state we study two scenarios, first, when the peers are ``patient'', i.e, do not leave the system until they obtain the complete file; second, peers are ``impatient'' and almost always leave the network before obtaining the complete file.
SIMPS: Using Sociology for Personal Mobility
Venue: arXiv cs.NI 2006
Year: 2006

Assessing mobility in a thorough fashion is a crucial step toward more efficient mobile network design. Recent research on mobility has focused on two main points: analyzing models and studying their impact on data transport. These works investigate the consequences of mobility. In this paper, instead, we focus on the causes of mobility. Starting from established research in sociology, we propose SIMPS, a mobility model of human crowd motion. This model defines two complimentary behaviors, namely socialize and isolate, that regulate an individual with regard to her/his own sociability level. SIMPS leads to results that agree with scaling laws observed both in small-scale and large-scale human motion. Although our model defines only two simple individual behaviors, we observe many emerging collective behaviors (group formation/splitting, path formation, and evolution). To our knowledge, SIMPS is the first model in the networking community that tackles the roots governing mobility.
Queue Model of Leaf Degree Keeping Process in Gnutella Network
Venue: arXiv cs.NI 2006
Year: 2006

Leaf degree keeping process of Gnutella is discussed in this paper. Queue system based on rules of Gnutella protocol are introduced to modeling this process. The leaf degree distributions resulted from the queue system and from our real measurement are compared. The well match of those distributions reveal that the leaf degree distribution in Gnutella network should not be power law or power law like as reported before. It is more likely a distribution driven by certain queue process specified by the protocol.
Unifying Lexicons in view of a Phonological and Morphological Lexical DB
Venue: arXiv cs.IR 2006
Year: 2006

The present work falls in the line of activities promoted by the European Languguage Resource Association (ELRA) Production Committee (PCom) and raises issues in methods, procedures and tools for the reusability, creation, and management of Language Resources. A two-fold purpose lies behind this experiment. The first aim is to investigate the feasibility, define methods and procedures for combining two Italian lexical resources that have incompatible formats and complementary information into a Unified Lexicon (UL). The adopted strategy and the procedures appointed are described together with the driving criterion of the merging task, where a balance between human and computational efforts is pursued. The coverage of the UL has been maximized, by making use of simple and fast matching procedures. The second aim is to exploit this newly obtained resource for implementing the phonological and morphological layers of the CLIPS lexical database. Implementing these new layers and linking them with the already exisitng syntactic and semantic layers is not a trivial task. The constraints imposed by the model, the impact at the architectural level and the solution adopted in order to make the whole database `speak' efficiently are presented. Advantages vs. disadvantages are discussed.
Interactive Configuration by Regular String Constraints
Venue: arXiv cs.AI 2006
Year: 2006

A product configurator which is complete, backtrack free and able to compute the valid domains at any state of the configuration can be constructed by building a Binary Decision Diagram (BDD). Despite the fact that the size of the BDD is exponential in the number of variables in the worst case, BDDs have proved to work very well in practice. Current BDD-based techniques can only handle interactive configuration with small finite domains. In this paper we extend the approach to handle string variables constrained by regular expressions. The user is allowed to change the strings by adding letters at the end of the string. We show how to make a data structure that can perform fast valid domain computations given some assignment on the set of string variables. We first show how to do this by using one large DFA. Since this approach is too space consuming to be of practical use, we construct a data structure that simulates the large DFA and in most practical cases are much more space efficient. As an example a configuration problem on $n$ string variables with only one solution in which each string variable is assigned to a value of length of $k$ the former structure will use $Ω(k^n)$ space whereas the latter only need $O(kn)$. We also show how this framework easily can be combined with the recent BDD techniques to allow both boolean, integer and string variables in the configuration problem.
The Parma Polyhedra Library: Toward a Complete Set of Numerical Abstractions for the Analysis and Verification of Hardware and Software Systems
Venue: arXiv cs.MS 2006
Year: 2006

Since its inception as a student project in 2001, initially just for the handling (as the name implies) of convex polyhedra, the Parma Polyhedra Library has been continuously improved and extended by joining scrupulous research on the theoretical foundations of (possibly non-convex) numerical abstractions to a total adherence to the best available practices in software development. Even though it is still not fully mature and functionally complete, the Parma Polyhedra Library already offers a combination of functionality, reliability, usability and performance that is not matched by similar, freely available libraries. In this paper, we present the main features of the current version of the library, emphasizing those that distinguish it from other similar libraries and those that are important for applications in the field of analysis and verification of hardware and software systems.
Non-Clairvoyant Batch Sets Scheduling: Fairness is Fair enough
Venue: arXiv cs.DC 2006
Year: 2006

Scheduling questions arise naturally in many different areas among which operating system design, compiling,... In real life systems, the characteristics of the jobs (such as release time and processing time) are usually unknown and unpredictable beforehand. The system is typically unaware of the remaining work in each job or of the ability of the job to take advantage of more resources. Following these observations, we adopt the job model by Edmonds et al (2000, 2003) in which the jobs go through a sequence of different phases. Each phase consists of a certain quantity of work and a speed-up function that models how it takes advantage of the number of processors it receives. We consider the non-clairvoyant online setting where a collection of jobs arrives at time 0. We consider the metrics setflowtime introduced by Robert et al (2007). The goal is to minimize the sum of the completion time of the sets, where a set is completed when all of its jobs are done. If the input consists of a single set of jobs, this is simply the makespan of the jobs; and if the input consists of a collection of singleton sets, it is simply the flowtime of the jobs. We show that the non-clairvoyant strategy EQUIoEQUI that evenly splits the available processors among the still unserved sets and then evenly splits these processors among the still uncompleted jobs of each unserved set, achieves a competitive ratio (2+\sqrt3+o(1))\frac{ln n}{lnln n} for the setflowtime minimization and that this is asymptotically optimal (up to a constant factor), where n is the size of the largest set. For makespan minimization, we show that the non-clairvoyant strategy EQUI achieves a competitive ratio of (1+o(1))\frac{ln n}{lnln n}, which is again asymptotically optimal.
Reduction of Algebraic Parametric Systems by Rectification of their Affine Expanded Lie Symmetries
Venue: arXiv cs.SC 2006
Year: 2006

Lie group theory states that knowledge of a $m$-parameters solvable group of symmetries of a system of ordinary differential equations allows to reduce by $m$ the number of equations. We apply this principle by finding some \emph{affine derivations} that induces \emph{expanded} Lie point symmetries of considered system. By rewriting original problem in an invariant coordinates set for these symmetries, we \emph{reduce} the number of involved parameters. We present an algorithm based on this standpoint whose arithmetic complexity is \emph{quasi-polynomial} in input's size.
Using state space differential geometry for nonlinear blind source separation
Venue: arXiv cs.LG 2006
Year: 2006

Given a time series of multicomponent measurements of an evolving stimulus, nonlinear blind source separation (BSS) seeks to find a "source" time series, comprised of statistically independent combinations of the measured components. In this paper, we seek a source time series with local velocity cross correlations that vanish everywhere in stimulus state space. However, in an earlier paper the local velocity correlation matrix was shown to constitute a metric on state space. Therefore, nonlinear BSS maps onto a problem of differential geometry: given the metric observed in the measurement coordinate system, find another coordinate system in which the metric is diagonal everywhere. We show how to determine if the observed data are separable in this way, and, if they are, we show how to construct the required transformation to the source coordinate system, which is essentially unique except for an unknown rotation that can be found by applying the methods of linear BSS. Thus, the proposed technique solves nonlinear BSS in many situations or, at least, reduces it to linear BSS, without the use of probabilistic, parametric, or iterative procedures. This paper also describes a generalization of this methodology that performs nonlinear independent subspace separation. In every case, the resulting decomposition of the observed data is an intrinsic property of the stimulus' evolution in the sense that it does not depend on the way the observer chooses to view it (e.g., the choice of the observing machine's sensors). In other words, the decomposition is a property of the evolution of the "real" stimulus that is "out there" broadcasting energy to the observer. The technique is illustrated with analytic and numerical examples.
Algorithms and Approaches of Proxy Signature: A Survey
Venue: arXiv cs.CR 2006
Year: 2006

Numerous research studies have been investigated on proxy signatures over the last decade. This survey reviews the research progress on proxy signatures, analyzes a few notable proposals, and provides an overall remark of these proposals.
Maximum Entropy MIMO Wireless Channel Models
Venue: arXiv cs.IT 2006
Year: 2006

In this contribution, models of wireless channels are derived from the maximum entropy principle, for several cases where only limited information about the propagation environment is available. First, analytical models are derived for the cases where certain parameters (channel energy, average energy, spatial correlation matrix) are known deterministically. Frequently, these parameters are unknown (typically because the received energy or the spatial correlation varies with the user position), but still known to represent meaningful system characteristics. In these cases, analytical channel models are derived by assigning entropy-maximizing distributions to these parameters, and marginalizing them out. For the MIMO case with spatial correlation, we show that the distribution of the covariance matrices is conveniently handled through its eigenvalues. The entropy-maximizing distribution of the covariance matrix is shown to be a Wishart distribution. Furthermore, the corresponding probability density function of the channel matrix is shown to be described analytically by a function of the channel Frobenius norm. This technique can provide channel models incorporating the effect of shadow fading and spatial correlation between antennas without the need to assume explicit values for these parameters. The results are compared in terms of mutual information to the classical i.i.d. Gaussian model.
On Completeness of Logical Relations for Monadic Types
Venue: arXiv cs.LO 2006
Year: 2006

Software security can be ensured by specifying and verifying security properties of software using formal methods with strong theoretical bases. In particular, programs can be modeled in the framework of lambda-calculi, and interesting properties can be expressed formally by contextual equivalence (a.k.a. observational equivalence). Furthermore, imperative features, which exist in most real-life software, can be nicely expressed in the so-called computational lambda-calculus. Contextual equivalence is difficult to prove directly, but we can often use logical relations as a tool to establish it in lambda-calculi. We have already defined logical relations for the computational lambda-calculus in previous work. We devote this paper to the study of their completeness w.r.t. contextual equivalence in the computational lambda-calculus.
Fragmentation in Large Object Repositories
Venue: arXiv cs.DB 2006
Year: 2006

Fragmentation leads to unpredictable and degraded application performance. While these problems have been studied in detail for desktop filesystem workloads, this study examines newer systems such as scalable object stores and multimedia repositories. Such systems use a get/put interface to store objects. In principle, databases and filesystems can support such applications efficiently, allowing system designers to focus on complexity, deployment cost and manageability. Although theoretical work proves that certain storage policies behave optimally for some workloads, these policies often behave poorly in practice. Most storage benchmarks focus on short-term behavior or do not measure fragmentation. We compare SQL Server to NTFS and find that fragmentation dominates performance when object sizes exceed 256KB-1MB. NTFS handles fragmentation better than SQL Server. Although the performance curves will vary with other systems and workloads, we expect the same interactions between fragmentation and free space to apply. It is well-known that fragmentation is related to the percentage free space. We found that the ratio of free space to object size also impacts performance. Surprisingly, in both systems, storing objects of a single size causes fragmentation, and changing the size of write requests affects fragmentation. These problems could be addressed with simple changes to the filesystem and database interfaces. It is our hope that an improved understanding of fragmentation will lead to predictable storage systems that require less maintenance after deployment.
Demaq: A Foundation for Declarative XML Message Processing
Venue: arXiv cs.DB 2006
Year: 2006

This paper gives an overview of Demaq, an XML message processing system operating on the foundation of transactional XML message queues. We focus on the syntax and semantics of its fully declarative, rule-based application language and demonstrate our message-based programming paradigm in the context of a case study. Further, we discuss optimization opportunities for executing Demaq programs.
Gossiping with Multiple Messages
Venue: arXiv cs.NI 2006
Year: 2006

This paper investigates the dissemination of multiple pieces of information in large networks where users contact each other in a random uncoordinated manner, and users upload one piece per unit time. The underlying motivation is the design and analysis of piece selection protocols for peer-to-peer networks which disseminate files by dividing them into pieces. We first investigate one-sided protocols, where piece selection is based on the states of either the transmitter or the receiver. We show that any such protocol relying only on pushes, or alternatively only on pulls, is inefficient in disseminating all pieces to all users. We propose a hybrid one-sided piece selection protocol -- INTERLEAVE -- and show that by using both pushes and pulls it disseminates $k$ pieces from a single source to $n$ users in $10(k+\log n)$ time, while obeying the constraint that each user can upload at most one piece in one unit of time, with high probability for large $n$. An optimal, unrealistic centralized protocol would take $k+\log_2 n$ time in this setting. Moreover, efficient dissemination is also possible if the source implements forward erasure coding, and users push the latest-released coded pieces (but do not pull). We also investigate two-sided protocols where piece selection is based on the states of both the transmitter and the receiver. We show that it is possible to disseminate $n$ pieces to $n$ users in $n+O(\log n)$ time, starting from an initial state where each user has a unique piece.
Large N Analysis of Amplify-and-Forward MIMO Relay Channels with Correlated Rayleigh Fading
Venue: arXiv cs.IT 2006
Year: 2006

In this correspondence the cumulants of the mutual information of the flat Rayleigh fading amplify-and-forward MIMO relay channel without direct link between source and destination are derived in the large array limit. The analysis is based on the replica trick and covers both spatially independent and correlated fading in the first and the second hop, while beamforming at all terminals is restricted to deterministic weight matrices. Expressions for mean and variance of the mutual information are obtained. Their parameters are determined by a nonlinear equation system. All higher cumulants are shown to vanish as the number of antennas n goes to infinity. In conclusion the distribution of the mutual information I becomes Gaussian in the large n limit and is completely characterized by the expressions obtained for mean and variance of I. Comparisons with simulation results show that the asymptotic results serve as excellent approximations for systems with only few antennas at each node. The derivation of the results follows the technique formalized by Moustakas et al. in [1]. Although the evaluations are more involved for the MIMO relay channel compared to point-to-point MIMO channels, the structure of the results is surprisingly simple again. In particular an elegant formula for the mean of the mutual information is obtained, i.e., the ergodic capacity of the two-hop amplify-and-forward MIMO relay channel without direct link.