OpenRaiser/Intern-Atlas huggingface dataset:
Distributed Algorithms for Finding Local Clusters Using Heat Kernel Pagerank
Venue: arXiv cs.DC 2016
Year: 2016

A distributed algorithm performs local computations on pieces of input and communicates the results through given communication links. When processing a massive graph in a distributed algorithm, local outputs must be configured as a solution to a graph problem without shared memory and with few rounds of communication. In this paper we consider the problem of computing a local cluster in a massive graph in the distributed setting. Computing local clusters are of certain application-specific interests, such as detecting communities in social networks or groups of interacting proteins in biological networks. When the graph models the computer network itself, detecting local clusters can help to prevent communication bottlenecks. We give a distributed algorithm that computes a local cluster in time that depends only logarithmically on the size of the graph in the CONGEST model. In particular, when the value of the optimal local cluster is known, the algorithm runs in time entirely independent of the size of the graph and depends only on error bounds for approximation. We also show that the local cluster problem can be computed in the k-machine distributed model in sublinear time. The speedup of our local cluster algorithms is mainly due to the use of our distributed algorithm for heat kernel pagerank.
Tractable Resource Management with Uplink Decoupled Millimeter-Wave Overlay in Ultra-Dense Cellular Networks
Venue: arXiv cs.IT 2016
Year: 2016

The forthcoming 5G cellular network is expected to overlay millimeter-wave (mmW) transmissions with the incumbent micro-wave (μW) architecture. The overall mm-μW resource management should therefore harmonize with each other. This paper aims at maximizing the overall downlink (DL) rate with a minimum uplink (UL) rate constraint, and concludes: mmW tends to focus more on DL transmissions while μW has high priority for complementing UL, under time-division duplex (TDD) mmW operations. Such UL dedication of μW results from the limited use of mmW UL bandwidth due to excessive power consumption and/or high peak-to-average power ratio (PAPR) at mobile users. To further relieve this UL bottleneck, we propose mmW UL decoupling that allows each legacy μW base station (BS) to receive mmW signals. Its impact on mm-μW resource management is provided in a tractable way by virtue of a novel closed-form mm-μW spectral efficiency (SE) derivation. In an ultra-dense cellular network (UDN), our derivation verifies mmW (or μW) SE is a logarithmic function of BS-to-user density ratio. This strikingly simple yet practically valid analysis is enabled by exploiting stochastic geometry in conjunction with real three dimensional (3D) building blockage statistics in Seoul, Korea.
Single-Carrier Modulation for Large-Scale Antenna Systems
Venue: arXiv cs.IT 2016
Year: 2016

Large-scale antenna (LSA) has gained a lot of attention due to its great potential to significantly improve system throughput. In most existing works on LSA systems, orthogonal frequency division multiplexing (OFDM) is presumed to deal with frequency selectivity of wireless channels. Although LSA-OFDM is a natural evolution from multiple-input multiple-output OFDM (MIMO-OFDM), the drawbacks of LSA-OFDM are inevitable, especially when used for the uplink. In this paper, we investigate single-carrier (SC) modulation for the uplink transmission in LSA systems based on a novel waveform recovery theory, where the receiver is designed to recover the transmit waveform while the information-bearing symbols can be recovered by directly sampling the recovered waveform. The waveform recovery adopts the assumption that the antenna number is infinite and the channels at different antennas are independent. In practical environments, however, the antenna number is always finite and the channels at different antennas are also correlated when placing hundreds of antennas in a small area. Therefore, we will also analyze the impacts of such non-ideal environments.
Queuing models for abstracting interactions in Bacterial communities
Venue: arXiv cs.ET 2016
Year: 2016

Microbial communities play a significant role in bioremediation,plant growth,human and animal digestion,global elemental cycles including the carbon-cycle,and water treatment.They are also posed to be the engines of renewable energy via microbial fuel cells which can reverse the process of electrosynthesis.Microbial communication regulates many virulence mechanisms used by bacteria.Thus,it is of fundamental importance to understand interactions in microbial communities and to develop predictive tools that help control them,in order to aid the design of systems exploiting bacterial capabilities.This position paper explores how abstractions from communications,networking and information theory can play a role in understanding and modeling bacterial interactions.In particular,two forms of interactions in bacterial systems will be examined:electron transfer and quorum sensing.While the diffusion of chemical signals has been heavily studied,electron transfer occurring in living cells and its role in cell-cell interaction is less understood.Recent experimental observations open up new frontiers in the design of microbial systems based on electron transfer,which may coexist with the more well-known interaction strategies based on molecular diffusion.In quorum sensing,the concentration of certain signature chemical compounds emitted by the bacteria is used to estimate the bacterial population size,so as to activate collective behaviors.In this position paper,queuing models for electron transfer are summarized and adapted to provide new models for quorum sensing.These models are stochastic,and thus capture the inherent randomness exhibited by cell colonies in nature.It is shown that queuing models allow the characterization of the state of a single cell as a function of interactions with other cells and the environment,while being amenable to complexity reduction.
MAP Support Detection for Greedy Sparse Signal Recovery Algorithms in Compressive Sensing
Venue: arXiv cs.IT 2016
Year: 2016

A reliable support detection is essential for a greedy algorithm to reconstruct a sparse signal accurately from compressed and noisy measurements. This paper proposes a novel support detection method for greedy algorithms, which is referred to as "\textit{maximum a posteriori (MAP) support detection}". Unlike existing support detection methods that identify support indices with the largest correlation value in magnitude per iteration, the proposed method selects them with the largest likelihood ratios computed under the true and null support hypotheses by simultaneously exploiting the distributions of sensing matrix, sparse signal, and noise. Leveraging this technique, MAP-Matching Pursuit (MAP-MP) is first presented to show the advantages of exploiting the proposed support detection method, and a sufficient condition for perfect signal recovery is derived for the case when the sparse signal is binary. Subsequently, a set of iterative greedy algorithms, called MAP-generalized Orthogonal Matching Pursuit (MAP-gOMP), MAP-Compressive Sampling Matching Pursuit (MAP-CoSaMP), and MAP-Subspace Pursuit (MAP-SP) are presented to demonstrate the applicability of the proposed support detection method to existing greedy algorithms. From empirical results, it is shown that the proposed greedy algorithms with highly reliable support detection can be better, faster, and easier to implement than basis pursuit via linear programming.
Implementation of the Log-Conformation Formulation for Two-Dimensional Viscoelastic Flow
Venue: arXiv cs.CE 2016
Year: 2016

We have implemented the log-conformation method for two-dimensional viscoelastic flow in COMSOL, a commercial high-level finite element package. The code is verified for an Oldroyd-B fluid flowing past a confined cylinder. We are also able to describe the well-known bistability of the viscoelastic flow in a cross-slot geometry for a FENE-CR fluid, and we describe the changes required for performing simulations with the Phan-Thien-Tanner (PTT), Giesekus and FENE-P models. Finally, we calculate the flow of a FENE-CR fluid in a geometry with three in- and outlets. The implementation is included in the supplementary material, and we hope that it can inspire new as well as experienced researchers in the field of differential constitutive equations for viscoelastic flow.
The QBF Gallery: Behind the Scenes
Venue: arXiv cs.LO 2016
Year: 2016

Over the last few years, much progress has been made in the theory and practice of solving quantified Boolean formulas (QBF). Novel solvers have been presented that either successfully enhance established techniques or implement novel solving paradigms. Powerful preprocessors have been realized that tune the encoding of a formula to make it easier to solve. Frameworks for certification and solution extraction emerged that allow for a detailed interpretation of a QBF solver's results, and new types of QBF encodings were presented for various application problems. To capture these developments the QBF Gallery was established in 2013. The QBF Gallery aims at providing a forum to assess QBF tools and to collect new, expressive benchmarks that allow for documenting the status quo and that indicate promising research directions. These benchmarks became the basis for the experiments conducted in the context of the QBF Gallery 2013 and follow-up evaluations. In this paper, we report on the setup of the QBF Gallery. To this end, we conducted numerous experiments which allowed us not only to assess the quality of the tools, but also the quality of the benchmarks.
Meta-MapReduce: A Technique for Reducing Communication in MapReduce Computations
Venue: arXiv cs.DB 2016
Year: 2016

MapReduce has proven to be one of the most useful paradigms in the revolution of distributed computing, where cloud services and cluster computing become the standard venue for computing. The federation of cloud and big data activities is the next challenge where MapReduce should be modified to avoid (big) data migration across remote (cloud) sites. This is exactly our scope of research, where only the very essential data for obtaining the result is transmitted, reducing communication, processing and preserving data privacy as much as possible. In this work, we propose an algorithmic technique for MapReduce algorithms, called Meta-MapReduce, that decreases the communication cost by allowing us to process and move metadata to clouds and from the map phase to reduce phase. In Meta-MapReduce, the reduce phase fetches only the required data at required iterations, which in turn, assists in preserving the data privacy.
The Mixing Time of the Dikin Walk in a Polytope - A Simple Proof
Venue: arXiv cs.DS 2016
Year: 2016

We study the mixing time of the Dikin walk in a polytope - a random walk based on the log-barrier from the interior point method literature. This walk, and a close variant, were studied by Narayanan (2016) and Kannan-Narayanan (2012). Bounds on its mixing time are important for algorithms for sampling and optimization over polytopes. Here, we provide a simple proof of their result that this random walk mixes in time O(mn) for an n-dimensional polytope described using m inequalities.
Average Error Probability in Wireless Sensor Networks with Imperfect Sensing and Communication for Different Decision Rules
Venue: arXiv cs.IT 2016
Year: 2016

This paper presents a framework to evaluate the probability that a decision error event occurs in wireless sensor networks, including sensing and communication errors. We consider a scenario where sensors need to identify whether a given event has occurred based on its periodic, noisy, observations of a given signal. Such information about the signal needs to be sent to a fusion center that decides about the actual state at that specific observation time. The communication links -- single- or multi-hop -- are modeled as binary symmetric channels, which may have different error probabilities. The decision at the fusion center is based on OR, AND, K-OUT-OF-N and MAJORITY Boolean operations on the received signals associated to individual sensor observations. We derive closed-form equations for the average decision error probability as a function of the system parameters (e.g. number of sensors and hops) and the input signal characterization. Our analyses show the best decision rule is closely related to the frequency that the observed events occur and the number of sensors. In our numerical example, we show that the AND rule outperforms MAJORITY if such an event is rare and there is only a handful number of sensors. Conversely, if there is a large number of sensors or more evenly distributed event occurrences, the MAJORITY is the best choice. We further show that, while the error probability using the MAJORITY rule asymptotically goes to 0 with increasing number of sensors, it is also more susceptible to higher channel error probabilities.
The Multivariate Covering Lemma and its Converse
Venue: arXiv cs.IT 2016
Year: 2016

The multivariate covering lemma states that given a collection of $k$ codebooks, each of sufficiently large cardinality and independently generated according to one of the marginals of a joint distribution, one can always choose one codeword from each codebook such that the resulting $k$-tuple of codewords is jointly typical with respect to the joint distribution. We give a proof of this lemma for weakly typical sets. This allows achievability proofs that rely on the covering lemma to go through for continuous channels (e.g., Gaussian) without the need for quantization. The covering lemma and its converse are widely used in information theory, including in rate-distortion theory and in achievability results for multi-user channels.
Fundamental limitations of network reconstruction
Venue: arXiv cs.SY 2016
Year: 2016

Network reconstruction is the first step towards understanding, diagnosing and controlling the dynamics of complex networked systems. It allows us to infer properties of the interaction matrix, which characterizes how nodes in a system directly interact with each other. Despite a decade of extensive studies, network reconstruction remains an outstanding challenge. The fundamental limitations governing which properties of the interaction matrix (e.g., adjacency pattern, sign pattern and degree sequence) can be inferred from given temporal data of individual nodes remain unknown. Here we rigorously derive necessary conditions to reconstruct any property of the interaction matrix. These conditions characterize how uncertain can we be about the coupling functions that characterize the interactions between nodes, and how informative does the measured temporal data need to be; rendering two classes of fundamental limitations of network reconstruction. Counterintuitively, we find that reconstructing any property of the interaction matrix is generically as difficult as reconstructing the interaction matrix itself, requiring equally informative temporal data. Revealing these fundamental limitations shed light on the design of better network reconstruction algorithms, which offer practical improvements over existing methods.
Coordination Complexity: Small Information Coordinating Large Populations
Venue: arXiv cs.DS 2016
Year: 2016

We initiate the study of a quantity that we call coordination complexity. In a distributed optimization problem, the information defining a problem instance is distributed among $n$ parties, who need to each choose an action, which jointly will form a solution to the optimization problem. The coordination complexity represents the minimal amount of information that a centralized coordinator, who has full knowledge of the problem instance, needs to broadcast in order to coordinate the $n$ parties to play a nearly optimal solution. We show that upper bounds on the coordination complexity of a problem imply the existence of good jointly differentially private algorithms for solving that problem, which in turn are known to upper bound the price of anarchy in certain games with dynamically changing populations. We show several results. We fully characterize the coordination complexity for the problem of computing a many-to-one matching in a bipartite graph by giving almost matching lower and upper bounds.Our upper bound in fact extends much more generally, to the problem of solving a linearly separable convex program. We also give a different upper bound technique, which we use to bound the coordination complexity of coordinating a Nash equilibrium in a routing game, and of computing a stable matching.
Performance Characterization of Relay-Assisted Wireless Optical CDMA Networks in Turbulent Underwater Channel
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we characterize the performance of relay-assisted underwater wireless optical code division multiple access (OCDMA) networks over turbulent channels. In addition to scattering and absorption effects of underwater channels, we also consider optical turbulence as a log-normal fading coefficient in our analysis. To simultaneously and asynchronously share medium among many users, we assign a unique optical orthogonal code (OOC) to each user in order to actualize OCDMA-based underwater network. The most significant challenge in underwater optical communication is in the ability to extend the short range of its coverage. In order to expand the viable communication range, we consider multi-hop transmission to the destination. Moreover, we evaluate the performance of a relay-assisted point-to-point UWOC system as a special case of the proposed relay-assisted OCDMA network. Our numerical results indicate significant performance improvement by employing intermediate relays, e.g., one can achieve $32$ {dB} improvement in the bit error rate (BER) of $10^{-6}$ using only a dual-hop transmission in a $90$ {m} point-to-point clear ocean link.
Mechanism Design via Dantzig-Wolfe Decomposition
Venue: arXiv cs.GT 2016
Year: 2016

In random allocation rules, typically first an optimal fractional point is calculated via solving a linear program. The calculated point represents a fractional assignment of objects or more generally packages of objects to agents. In order to implement an expected assignment, the mechanism designer must decompose the fractional point into integer solutions, each satisfying underlying constraints. The resulting convex combination can then be viewed as a probability distribution over feasible assignments out of which a random assignment can be sampled. This approach has been successfully employed in combinatorial optimization as well as mechanism design with or without money. In this paper, we show that both finding the optimal fractional point as well as its decomposition into integer solutions can be done at once. We propose an appropriate linear program which provides the desired solution. We show that the linear program can be solved via Dantzig-Wolfe decomposition. Dantzig-Wolfe decomposition is a direct implementation of the revised simplex method which is well known to be highly efficient in practice. We also show how to use the Benders decomposition as an alternative method to solve the problem. The proposed method can also find a decomposition into integer solutions when the fractional point is readily present perhaps as an outcome of other algorithms rather than linear programming. The resulting convex decomposition in this case is tight in terms of the number of integer points according to the Carath{é}odory's theorem.
Towards Vulnerability Discovery Using Staged Program Analysis
Venue: arXiv cs.CR 2016
Year: 2016

Eliminating vulnerabilities from low-level code is vital for securing software. Static analysis is a promising approach for discovering vulnerabilities since it can provide developers early feedback on the code they write. But, it presents multiple challenges not the least of which is understanding what makes a bug exploitable and conveying this information to the developer. In this paper, we present the design and implementation of a practical vulnerability assessment framework, called Melange. Melange performs data and control flow analysis to diagnose potential security bugs, and outputs well-formatted bug reports that help developers understand and fix security bugs. Based on the intuition that real-world vulnerabilities manifest themselves across multiple parts of a program, Melange performs both local and global analyses. To scale up to large programs, global analysis is demand-driven. Our prototype detects multiple vulnerability classes in C and C++ code including type confusion, and garbage memory reads. We have evaluated Melange extensively. Our case studies show that Melange scales up to large codebases such as Chromium, is easy-to-use, and most importantly, capable of discovering vulnerabilities in real-world code. Our findings indicate that static analysis is a viable reinforcement to the software testing tool set.
Tolerating Correlated Failures in Massively Parallel Stream Processing Engines
Venue: arXiv cs.DC 2016
Year: 2016

Fault-tolerance techniques for stream processing engines can be categorized into passive and active approaches. A typical passive approach periodically checkpoints a processing task's runtime states and can recover a failed task by restoring its runtime state using its latest checkpoint. On the other hand, an active approach usually employs backup nodes to run replicated tasks. Upon failure, the active replica can take over the processing of the failed task with minimal latency. However, both approaches have their own inadequacies in Massively Parallel Stream Processing Engines (MPSPE). The passive approach incurs a long recovery latency especially when a number of correlated nodes fail simultaneously, while the active approach requires extra replication resources. In this paper, we propose a new fault-tolerance framework, which is Passive and Partially Active (PPA). In a PPA scheme, the passive approach is applied to all tasks while only a selected set of tasks will be actively replicated. The number of actively replicated tasks depends on the available resources. If tasks without active replicas fail, tentative outputs will be generated before the completion of the recovery process. We also propose effective and efficient algorithms to optimize a partially active replication plan to maximize the quality of tentative outputs. We implemented PPA on top of Storm, an open-source MPSPE and conducted extensive experiments using both real and synthetic datasets to verify the effectiveness of our approach.
Decoupling conflicts for configurable resolution in an open replication system
Venue: arXiv cs.DC 2016
Year: 2016

Replikativ is a replication middleware supporting a new kind of confluent replicated datatype resembling a distributed version control system. It retains the order of write operations at the trade-off of reduced availability with after-the- fact conflict resolution. The system allows to develop applications with distributed state in a similar fashion as native applications with exclusive local state, while transparently exposing the necessary compromises in terms of the CAP theorem. In this paper, we give a specification of the replicated datatype and discuss its usage in the replikativ middleware. Experiments with the implementation show the feasibility of the concept as a foundation for replication as a service (RaaS).