OpenRaiser/Intern-Atlas huggingface dataset:
Enabling Loosely-Coupled Serial Job Execution on the IBM BlueGene/P Supercomputer and the SiCortex SC5832
Venue: arXiv cs.DC 2008
Year: 2008

Our work addresses the enabling of the execution of highly parallel computations composed of loosely coupled serial jobs with no modifications to the respective applications, on large-scale systems. This approach allows new-and potentially far larger-classes of application to leverage systems such as the IBM Blue Gene/P supercomputer and similar emerging petascale architectures. We present here the challenges of I/O performance encountered in making this model practical, and show results using both micro-benchmarks and real applications on two large-scale systems, the BG/P and the SiCortex SC5832. Our preliminary benchmarks show that we can scale to 4096 processors on the Blue Gene/P and 5832 processors on the SiCortex with high efficiency, and can achieve thousands of tasks/sec sustained execution rates for parallel workloads of ordinary serial applications. We measured applications from two domains, economic energy modeling and molecular dynamics.
Accelerating Large-scale Data Exploration through Data Diffusion
Venue: arXiv cs.DC 2008
Year: 2008

Data-intensive applications often require exploratory analysis of large datasets. If analysis is performed on distributed resources, data locality can be crucial to high throughput and performance. We propose a "data diffusion" approach that acquires compute and storage resources dynamically, replicates data in response to demand, and schedules computations close to data. As demand increases, more resources are acquired, thus allowing faster response to subsequent requests that refer to the same data; when demand drops, resources are released. This approach can provide the benefits of dedicated hardware without the associated high costs, depending on workload and resource characteristics. The approach is reminiscent of cooperative caching, web-caching, and peer-to-peer storage systems, but addresses different application demands. Other data-aware scheduling approaches assume dedicated resources, which can be expensive and/or inefficient if load varies significantly. To explore the feasibility of the data diffusion approach, we have extended the Falkon resource provisioning and task scheduling system to support data caching and data-aware scheduling. Performance results from both micro-benchmarks and a large scale astronomy application demonstrate that our approach improves performance relative to alternative approaches, as well as provides improved scalability as aggregated I/O bandwidth scales linearly with the number of data cache nodes.
Market-Oriented Cloud Computing: Vision, Hype, and Reality for Delivering IT Services as Computing Utilities
Venue: arXiv cs.DC 2008
Year: 2008

This keynote paper: presents a 21st century vision of computing; identifies various computing paradigms promising to deliver the vision of computing utilities; defines Cloud computing and provides the architecture for creating market-oriented Clouds by leveraging technologies such as VMs; provides thoughts on market-based resource management strategies that encompass both customer-driven service management and computational risk management to sustain SLA-oriented resource allocation; presents some representative Cloud platforms especially those developed in industries along with our current work towards realising market-oriented resource allocation of Clouds by leveraging the 3rd generation Aneka enterprise Grid technology; reveals our early thoughts on interconnecting Clouds for dynamically creating an atmospheric computing environment along with pointers to future community research; and concludes with the need for convergence of competing IT paradigms for delivering our 21st century vision.
Classical Knowledge for Quantum Security
Venue: arXiv cs.CR 2008
Year: 2008

We propose a decision procedure for analysing security of quantum cryptographic protocols, combining a classical algebraic rewrite system for knowledge with an operational semantics for quantum distributed computing. As a test case, we use our procedure to reason about security properties of a recently developed quantum secret sharing protocol that uses graph states. We analyze three different scenarios based on the safety assumptions of the classical and quantum channels and discover the path of an attack in the presence of an adversary. The epistemic analysis that leads to this and similar types of attacks is purely based on our classical notion of knowledge.
A game-theoretic version of Oakes' example for randomized forecasting
Venue: arXiv cs.LG 2008
Year: 2008

Using the game-theoretic framework for probability, Vovk and Shafer. have shown that it is always possible, using randomization, to make sequential probability forecasts that pass any countable set of well-behaved statistical tests. This result generalizes work by other authors, who consider only tests of calbration. We complement this result with a lower bound. We show that Vovk and Shafer's result is valid only when the forecasts are computed with unrestrictedly increasing degree of accuracy. When some level of discreteness is fixed, we present a game-theoretic generalization of Oakes' example for randomized forecasting that is a test failing any given method of deferministic forecasting; originally, this example was presented for deterministic calibration.
Understanding Fairness and its Impact on Quality of Service in IEEE 802.11
Venue: arXiv cs.NI 2008
Year: 2008

The Distributed Coordination Function (DCF) aims at fair and efficient medium access in IEEE 802.11. In face of its success, it is remarkable that there is little consensus on the actual degree of fairness achieved, particularly bearing its impact on quality of service in mind. In this paper we provide an accurate model for the fairness of the DCF. Given M greedy stations we assume fairness if a tagged station contributes a share of 1/M to the overall number of packets transmitted. We derive the probability distribution of fairness deviations and support our analytical results by an extensive set of measurements. We find a closed-form expression for the improvement of long-term over short-term fairness. Regarding the random countdown values we quantify the significance of their distribution whereas we discover that fairness is largely insensitive to the distribution parameters. Based on our findings we view the DCF as emulating an ideal fair queuing system to quantify the deviations from a fair rate allocation. We deduce a stochastic service curve model for the DCF to predict packet delays in IEEE 802.11. We show how a station can estimate its fair bandwidth share from passive measurements of its traffic arrivals and departures.
A Simple Extension of the $\modulo$-$Λ$ Transformation
Venue: arXiv cs.IT 2008
Year: 2008

A simple lemma is derived that allows to transform a general scalar (non-Gaussian, non-additive) continuous-alphabet channel as well as a general multiple-access channel into a modulo-additive noise channel. While in general the transformation is information lossy, it allows to leverage linear coding techniques and capacity results derived for networks comprised of additive Gaussian nodes to more general networks.
Networked MIMO with Clustered Linear Precoding
Venue: arXiv cs.IT 2008
Year: 2008

A clustered base transceiver station (BTS) coordination strategy is proposed for a large cellular MIMO network, which includes full intra-cluster coordination to enhance the sum rate and limited inter-cluster coordination to reduce interference for the cluster edge users. Multi-cell block diagonalization is used to coordinate the transmissions across multiple BTSs in the same cluster. To satisfy per-BTS power constraints, three combined precoder and power allocation algorithms are proposed with different performance and complexity tradeoffs. For inter-cluster coordination, the coordination area is chosen to balance fairness for edge users and the achievable sum rate. It is shown that a small cluster size (about 7 cells) is sufficient to obtain most of the sum rate benefits from clustered coordination while greatly relieving channel feedback requirement. Simulations show that the proposed coordination strategy efficiently reduces interference and provides a considerable sum rate gain for cellular MIMO networks.
TrustMAS: Trusted Communication Platform for Multi-Agent Systems
Venue: arXiv cs.CR 2008
Year: 2008

The paper presents TrustMAS - Trusted Communication Platform for Multi-Agent Systems, which provides trust and anonymity for mobile agents. The platform includes anonymous technique based on random-walk algorithm for providing general purpose anonymous communication for agents. All agents, which take part in the proposed platform, benefit from trust and anonymity that is provided for their interactions. Moreover, in TrustMAS there are StegAgents (SA) that are able to perform various steganographic communication. To achieve that goal, SAs may use methods in different layers of TCP/IP model or specialized middleware enabling steganography that allows hidden communication through all layers of mentioned model. In TrustMAS steganographic channels are used to exchange routing tables between StegAgents. Thus all StegAgents in TrustMAS with their ability to exchange information by using hidden channels form distributed steganographic router (Stegrouter).
Achieving the Empirical Capacity Using Feedback Part I: Memoryless Additive Models
Venue: arXiv cs.IT 2008
Year: 2008

We address the problem of universal communications over an unknown channel with an instantaneous noiseless feedback, and show how rates corresponding to the empirical behavior of the channel can be attained, although no rate can be guaranteed in advance. First, we consider a discrete modulo-additive channel with alphabet $\mathcal{X}$, where the noise sequence $Z^n$ is arbitrary and unknown and may causally depend on the transmitted and received sequences and on the encoder's message, possibly in an adversarial fashion. Although the classical capacity of this channel is zero, we show that rates approaching the empirical capacity $\log|\mathcal{X}|-H_{emp}(Z^n)$ can be universally attained, where $H_{emp}(Z^n)$ is the empirical entropy of $Z^n$. For the more general setting where the channel can map its input to an output in an arbitrary unknown fashion subject only to causality, we model the empirical channel actions as the modulo-addition of a realized noise sequence, and show that the same result applies if common randomness is available. The results are proved constructively, by providing a simple sequential transmission scheme approaching the empirical capacity. In part II of this work we demonstrate how even higher rates can be attained by using more elaborate models for channel actions, and by utilizing possible empirical dependencies in its behavior.
A Variational Inference Framework for Soft-In-Soft-Out Detection in Multiple Access Channels
Venue: arXiv cs.IT 2008
Year: 2008

We propose a unified framework for deriving and studying soft-in-soft-out (SISO) detection in interference channels using the concept of variational inference. The proposed framework may be used in multiple-access interference (MAI), inter-symbol interference (ISI), and multiple-input multiple-outpu (MIMO) channels. Without loss of generality, we will focus our attention on turbo multiuser detection, to facilitate a more concrete discussion. It is shown that, with some loss of optimality, variational inference avoids the exponential complexity of a posteriori probability (APP) detection by optimizing a closely-related, but much more manageable, objective function called variational free energy. In addition to its systematic appeal, there are several other advantages to this viewpoint. First of all, it provides unified and rigorous justifications for numerous detectors that were proposed on radically different grounds, and facilitates convenient joint detection and decoding (utilizing the turbo principle) when error-control codes are incorporated. Secondly, efficient joint parameter estimation and data detection is possible via the variational expectation maximization (EM) algorithm, such that the detrimental effect of inaccurate channel knowledge at the receiver may be dealt with systematically. We are also able to extend BPSK-based SISO detection schemes to arbitrary square QAM constellations in a rigorous manner using a variational argument.
A functional view of upper bounds on codes
Venue: arXiv cs.IT 2008
Year: 2008

Functional and linear-algebraic approaches to the Delsarte problem of upper bounds on codes are discussed. We show that Christoffel-Darboux kernels and Levenshtein polynomials related to them arise as stationary points of the moment functionals of some distributions. We also show that they can be derived as eigenfunctions of the Jacobi operator. This motivates the choice of polynomials used to derive linear programming upper bounds on codes in homogeneous spaces.
Degrees of Freedom of the $K$ User $M \times N$ MIMO Interference Channel
Venue: arXiv cs.IT 2008
Year: 2008

We provide innerbound and outerbound for the total number of degrees of freedom of the $K$ user multiple input multiple output (MIMO) Gaussian interference channel with $M$ antennas at each transmitter and $N$ antennas at each receiver if the channel coefficients are time-varying and drawn from a continuous distribution. The bounds are tight when the ratio $\frac{\max(M,N)}{\min(M,N)}=R$ is equal to an integer. For this case, we show that the total number of degrees of freedom is equal to $\min(M,N)K$ if $K \leq R$ and $\min(M,N)\frac{R}{R+1}K$ if $K > R$. Achievability is based on interference alignment. We also provide examples where using interference alignment combined with zero forcing can achieve more degrees of freedom than merely zero forcing for some MIMO interference channels with constant channel coefficients.
On the nature of long-range letter correlations in texts
Venue: arXiv cs.CL 2008
Year: 2008

The origin of long-range letter correlations in natural texts is studied using random walk analysis and Jensen-Shannon divergence. It is concluded that they result from slow variations in letter frequency distribution, which are a consequence of slow variations in lexical composition within the text. These correlations are preserved by random letter shuffling within a moving window. As such, they do reflect structural properties of the text, but in a very indirect manner.
The Complexity of Enriched Mu-Calculi
Venue: arXiv cs.LO 2008
Year: 2008

The fully enriched μ-calculus is the extension of the propositional μ-calculus with inverse programs, graded modalities, and nominals. While satisfiability in several expressive fragments of the fully enriched μ-calculus is known to be decidable and ExpTime-complete, it has recently been proved that the full calculus is undecidable. In this paper, we study the fragments of the fully enriched μ-calculus that are obtained by dropping at least one of the additional constructs. We show that, in all fragments obtained in this way, satisfiability is decidable and ExpTime-complete. Thus, we identify a family of decidable logics that are maximal (and incomparable) in expressive power. Our results are obtained by introducing two new automata models, showing that their emptiness problems are ExpTime-complete, and then reducing satisfiability in the relevant logics to these problems. The automata models we introduce are two-way graded alternating parity automata over infinite trees (2GAPTs) and fully enriched automata (FEAs) over infinite forests. The former are a common generalization of two incomparable automata models from the literature. The latter extend alternating automata in a similar way as the fully enriched μ-calculus extends the standard μ-calculus.
Binary Random Sequences Obtained From Decimal Sequences
Venue: arXiv cs.CR 2008
Year: 2008

This paper presents a twist to the generation of binary random sequences by starting with decimal sequences. Rather than representing the prime reciprocal sequence directly in base 2, we first right the prime reciprocal in base 10 and then convert it into the binary form. The autocorrelation and cross-correlation properties of these binary random (BRD) sequences are discussed.
Entropy Concentration and the Empirical Coding Game
Venue: arXiv cs.IT 2008
Year: 2008

We give a characterization of Maximum Entropy/Minimum Relative Entropy inference by providing two `strong entropy concentration' theorems. These theorems unify and generalize Jaynes' `concentration phenomenon' and Van Campenhout and Cover's `conditional limit theorem'. The theorems characterize exactly in what sense a prior distribution Q conditioned on a given constraint, and the distribution P, minimizing the relative entropy D(P ||Q) over all distributions satisfying the constraint, are `close' to each other. We then apply our theorems to establish the relationship between entropy concentration and a game-theoretic characterization of Maximum Entropy Inference due to Topsoe and others.
Tight Bounds on Minimum Maximum Pointwise Redundancy
Venue: arXiv cs.IT 2008
Year: 2008

This paper presents new lower and upper bounds for the optimal compression of binary prefix codes in terms of the most probable input symbol, where compression efficiency is determined by the nonlinear codeword length objective of minimizing maximum pointwise redundancy. This objective relates to both universal modeling and Shannon coding, and these bounds are tight throughout the interval. The upper bounds also apply to a related objective, that of dth exponential redundancy.
Network Coding Security: Attacks and Countermeasures
Venue: arXiv cs.CR 2008
Year: 2008

By allowing intermediate nodes to perform non-trivial operations on packets, such as mixing data from multiple streams, network coding breaks with the ruling store and forward networking paradigm and opens a myriad of challenging security questions. Following a brief overview of emerging network coding protocols, we provide a taxonomy of their security vulnerabilities, which highlights the differences between attack scenarios in which network coding is particularly vulnerable and other relevant cases in which the intrinsic properties of network coding allow for stronger and more efficient security solutions than classical routing. Furthermore, we give practical examples where network coding can be combined with classical cryptography both for secure communication and secret key distribution. Throughout the paper we identify a number of research challenges deemed relevant towards the applicability of secure network coding in practical networks.
Probabilistic Systems with LimSup and LimInf Objectives
Venue: arXiv cs.GT 2008
Year: 2008

We give polynomial-time algorithms for computing the values of Markov decision processes (MDPs) with limsup and liminf objectives. A real-valued reward is assigned to each state, and the value of an infinite path in the MDP is the limsup (resp. liminf) of all rewards along the path. The value of an MDP is the maximal expected value of an infinite path that can be achieved by resolving the decisions of the MDP. Using our result on MDPs, we show that turn-based stochastic games with limsup and liminf objectives can be solved in NP \cap coNP.
Betweenness Centrality : Algorithms and Lower Bounds
Venue: arXiv cs.DS 2008
Year: 2008

One of the most fundamental problems in large scale network analysis is to determine the importance of a particular node in a network. Betweenness centrality is the most widely used metric to measure the importance of a node in a network. In this paper, we present a randomized parallel algorithm and an algebraic method for computing betweenness centrality of all nodes in a network. We prove that any path-comparison based algorithm cannot compute betweenness in less than O(nm) time.
Low congestion online routing and an improved mistake bound for online prediction of graph labeling
Venue: arXiv cs.DS 2008
Year: 2008

In this paper, we show a connection between a certain online low-congestion routing problem and an online prediction of graph labeling. More specifically, we prove that if there exists a routing scheme that guarantees a congestion of $α$ on any edge, there exists an online prediction algorithm with mistake bound $α$ times the cut size, which is the size of the cut induced by the label partitioning of graph vertices. With previous known bound of $O(\log n)$ for $α$ for the routing problem on trees with $n$ vertices, we obtain an improved prediction algorithm for graphs with high effective resistance. In contrast to previous approaches that move the graph problem into problems in vector space using graph Laplacian and rely on the analysis of the perceptron algorithm, our proof are purely combinatorial. Further more, our approach directly generalizes to the case where labels are not binary.
Informed Network Coding for Minimum Decoding Delay
Venue: arXiv cs.IT 2008
Year: 2008

Network coding is a highly efficient data dissemination mechanism for wireless networks. Since network coded information can only be recovered after delivering a sufficient number of coded packets, the resulting decoding delay can become problematic for delay-sensitive applications such as real-time media streaming. Motivated by this observation, we consider several algorithms that minimize the decoding delay and analyze their performance by means of simulation. The algorithms differ both in the required information about the state of the neighbors' buffers and in the way this knowledge is used to decide which packets to combine through coding operations. Our results show that a greedy algorithm, whose encodings maximize the number of nodes at which a coded packet is immediately decodable significantly outperforms existing network coding protocols.
Simpler Analyses of Local Search Algorithms for Facility Location
Venue: arXiv cs.DS 2008
Year: 2008

We study local search algorithms for metric instances of facility location problems: the uncapacitated facility location problem (UFL), as well as uncapacitated versions of the $k$-median, $k$-center and $k$-means problems. All these problems admit natural local search heuristics: for example, in the UFL problem the natural moves are to open a new facility, close an existing facility, and to swap a closed facility for an open one; in $k$-medians, we are allowed only swap moves. The local-search algorithm for $k$-median was analyzed by Arya et al. (SIAM J. Comput. 33(3):544-562, 2004), who used a clever ``coupling'' argument to show that local optima had cost at most constant times the global optimum. They also used this argument to show that the local search algorithm for UFL was 3-approximation; their techniques have since been applied to other facility location problems. In this paper, we give a proof of the $k$-median result which avoids this coupling argument. These arguments can be used in other settings where the Arya et al. arguments have been used. We also show that for the problem of opening $k$ facilities $F$ to minimize the objective function $Φ_p(F) = \big(\sum_{j \in V} d(j, F)^p\big)^{1/p}$, the natural swap-based local-search algorithm is a $Θ(p)$-approximation. This implies constant-factor approximations for $k$-medians (when $p=1$), and $k$-means (when $p = 2$), and an $O(\log n)$-approximation algorithm for the $k$-center problem (which is essentially $p = \log n$).
Mathematical Tool of Discrete Dynamic Modeling of Complex Systems in Control Loop
Venue: arXiv cs.MA 2008
Year: 2008

In this paper we present a method of discrete modeling and analysis of multi-level dynamics of complex large-scale hierarchical dynamic systems subject to external dynamic control mechanism. In a model each state describes parallel dynamics and simultaneous trends of changes in system parameters. The essence of the approach is in analysis of system state dynamics while it is in the control loop.