您当前的位置: 首页 > 网页快照
subscribe to arXiv mailings
arXiv:2108.12092 ?[ pdf , other ]? cs.DL Replaying Archived Twitter: When your bird is broken, will it bring you down? Authors: Kritika Garg , Himarsha R. Jayanetti , Sawood Alam , Michele C. Weigle , Michael L. Nelson Abstract : Historians and researchers trust web archives to preserve social media content that no longer exists on the live web. However, what we see on the live web and how it is replayed in the archive are not always the same. In this paper, we document and analyze the problems in archiving Twitter ever since Twitter forced the use of its new UI in June 2020. Most web archives were unable to archive the ne… ▽ More Historians and researchers trust web archives to preserve social media content that no longer exists on the live web. However, what we see on the live web and how it is replayed in the archive are not always the same. In this paper, we document and analyze the problems in archiving Twitter ever since Twitter forced the use of its new UI in June 2020. Most web archives were unable to archive the new UI, resulting in archived Twitter pages displaying Twitter's "Something went wrong" error. The challenges in archiving the new UI forced web archives to continue using the old UI. To analyze the potential loss of information in web archival data due to this change, we used the personal Twitter account of the 45th President of the United States, @realDonaldTrump, which was suspended by Twitter on January 8, 2021. Trump's account was heavily labeled by Twitter for spreading misinformation, however we discovered that there is no evidence in web archives to prove that some of his tweets ever had a label assigned to them. We also studied the possibility of temporal violations in archived versions of the new UI, which may result in the replay of pages that never existed on the live web. Our goal is to educate researchers who may use web archives and caution them when drawing conclusions based on archived Twitter pages. △ Less Submitted 26 August, 2021; originally announced August 2021. arXiv:2105.09602 ?[ pdf , ps , other ]? cs.DM cs.DS Characterization of Super-stable Matchings Authors: Changyong Hu , Vijay K. Garg Abstract : An instance of the super-stable matching problem with incomplete lists and ties is an undirected bipartite graph $G = (A \cup B, E)$, with an adjacency list being a linearly ordered list of ties. Ties are subsets of vertices equally good for a given vertex. An edge $(x,y) \in E \backslash M$ is a blocking edge for a matching $M$ if by getting matched to each other neither of the vertices $x$ and… ▽ More An instance of the super-stable matching problem with incomplete lists and ties is an undirected bipartite graph $G = (A \cup B, E)$, with an adjacency list being a linearly ordered list of ties. Ties are subsets of vertices equally good for a given vertex. An edge $(x,y) \in E \backslash M$ is a blocking edge for a matching $M$ if by getting matched to each other neither of the vertices $x$ and $y$ would become worse off. Thus, there is no disadvantage if the two vertices would like to match up. A matching $M$ is super-stable if there is no blocking edge with respect to $M$. It has previously been shown that super-stable matchings form a distributive lattice and the number of super-stable matchings can be exponential in the number of vertices. We give two compact representations of size $O(m)$ that can be used to construct all super-stable matchings, where $m$ denotes the number of edges in the graph. The construction of the second representation takes $O(mn)$ time, where $n$ denotes the number of vertices in the graph, and gives an explicit rotation poset similar to the rotation poset in the classical stable marriage problem. We also give a polyhedral characterisation of the set of all super-stable matchings and prove that the super-stable matching polytope is integral, thus solving an open problem stated in the book by Gusfield and Irving . △ Less Submitted 20 May, 2021; originally announced May 2021. arXiv:2103.06264 ?[ pdf , other ]? cs.DC cs.DS A Lattice Linear Predicate Parallel Algorithm for the Dynamic Programming Problems Authors: Vijay K. Garg Abstract : It has been shown that the parallel Lattice Linear Predicate (LLP) algorithm solves many combinatorial optimization problems such as the shortest path problem, the stable marriage problem and the market clearing price problem. In this paper, we give the parallel LLP algorithm for many dynamic programming problems. In particular, we show that the LLP algorithm solves the longest subsequence problem… ▽ More It has been shown that the parallel Lattice Linear Predicate (LLP) algorithm solves many combinatorial optimization problems such as the shortest path problem, the stable marriage problem and the market clearing price problem. In this paper, we give the parallel LLP algorithm for many dynamic programming problems. In particular, we show that the LLP algorithm solves the longest subsequence problem, the optimal binary search tree problem, and the knapsack problem. Furthermore, the algorithm can be used to solve the constrained versions of these problems so long as the constraints are lattice linear. The parallel LLP algorithm requires only read-write atomicity and no higher-level atomic instructions. △ Less Submitted 10 March, 2021; originally announced March 2021. arXiv:2008.08023 ?[ pdf ]? cs.CV Multilanguage Number Plate Detection using Convolutional Neural Networks Authors: Jatin Gupta , Vandana Saini , Kamaldeep Garg Abstract : Object Detection is a popular field of research for recent technologies. In recent years, profound learning performance attracts the researchers to use it in many applications. Number plate (NP) detection and classification is analyzed over decades however, it needs approaches which are more precise and state, language and design independent since cars are now moving from state to another easily.… ▽ More Object Detection is a popular field of research for recent technologies. In recent years, profound learning performance attracts the researchers to use it in many applications. Number plate (NP) detection and classification is analyzed over decades however, it needs approaches which are more precise and state, language and design independent since cars are now moving from state to another easily. In this paperwe suggest a new strategy to detect NP and comprehend the nation, language and layout of NPs. YOLOv2 sensor with ResNet attribute extractor heart is proposed for NP detection and a brand new convolutional neural network architecture is suggested to classify NPs. The detector achieves average precision of 99.57% and country, language and layout classification precision of 99.33%. The results outperforms the majority of the previous works and can move the area forward toward international NP detection and recognition. △ Less Submitted 18 August, 2020; originally announced August 2020. arXiv:2007.09513 ?[ pdf , other ]? cs.CL cs.SI Feature-level Rating System using Customer Reviews and Review Votes Authors: Koteswar Rao Jerripothula , Ankit Rai , Kanu Garg , Yashvardhan Singh Rautela Abstract : This work studies how we can obtain feature-level ratings of the mobile products from the customer reviews and review votes to influence decision making, both for new customers and manufacturers. Such a rating system gives a more comprehensive picture of the product than what a product-level rating system offers. While product-level ratings are too generic, feature-level ratings are particular; we… ▽ More This work studies how we can obtain feature-level ratings of the mobile products from the customer reviews and review votes to influence decision making, both for new customers and manufacturers. Such a rating system gives a more comprehensive picture of the product than what a product-level rating system offers. While product-level ratings are too generic, feature-level ratings are particular; we exactly know what is good or bad about the product. There has always been a need to know which features fall short or are doing well according to the customer's perception. It keeps both the manufacturer and the customer well-informed in the decisions to make in improving the product and buying, respectively. Different customers are interested in different features. Thus, feature-level ratings can make buying decisions personalized. We analyze the customer reviews collected on an online shopping site (Amazon) about various mobile products and the review votes. Explicitly, we carry out a feature-focused sentiment analysis for this purpose. Eventually, our analysis yields ratings to 108 features for 4k+ mobiles sold online. It helps in decision making on how to improve the product (from the manufacturer's perspective) and in making the personalized buying decisions (from the buyer's perspective) a possibility. Our analysis has applications in recommender systems, consumer research, etc. △ Less Submitted 18 July, 2020; originally announced July 2020. Comments: 10 pages, 7 figures, and accepted by IEEE Transactions on Computational Social Systems arXiv:2007.07121 ?[ pdf , ps , other ]? cs.GT cs.DM Improved Paths to Stability for the Stable Marriage Problem Authors: Vijay Kumar Garg , Changyong Hu Abstract : The stable marriage problem requires one to find a marriage with no blocking pair. Given a matching that is not stable, Roth and Vande Vate have shown that there exists a sequence of matchings that leads to a stable matching in which each successive matching is obtained by satisfying a blocking pair. The sequence produced by Roth and Vande Vate's algorithm is of length $O(n^3)$ where $n$ is the nu… ▽ More The stable marriage problem requires one to find a marriage with no blocking pair. Given a matching that is not stable, Roth and Vande Vate have shown that there exists a sequence of matchings that leads to a stable matching in which each successive matching is obtained by satisfying a blocking pair. The sequence produced by Roth and Vande Vate's algorithm is of length $O(n^3)$ where $n$ is the number of men (and women). In this paper, we present an algorithm that achieves stability in a sequence of matchings of length $O(n^2)$. We also give an efficient algorithm to find the stable matching closest to the given initial matching under an appropriate distance function between matchings. △ Less Submitted 14 July, 2020; originally announced July 2020. arXiv:2007.00977 ?[ pdf , other ]? cs.CV cs.AI cs.GR cs.LG PerceptionGAN: Real-world Image Construction from Provided Text through Perceptual Understanding Authors: Kanish Garg , Ajeet kumar Singh , Dorien Herremans , Brejesh Lall Abstract : Generating an image from a provided descriptive text is quite a challenging task because of the difficulty in incorporating perceptual information (object shapes, colors, and their interactions) along with providing high relevancy related to the provided text. Current methods first generate an initial low-resolution image, which typically has irregular object shapes, colors, and interaction betwee… ▽ More Generating an image from a provided descriptive text is quite a challenging task because of the difficulty in incorporating perceptual information (object shapes, colors, and their interactions) along with providing high relevancy related to the provided text. Current methods first generate an initial low-resolution image, which typically has irregular object shapes, colors, and interaction between objects. This initial image is then improved by conditioning on the text. However, these methods mainly address the problem of using text representation efficiently in the refinement of the initially generated image, while the success of this refinement process depends heavily on the quality of the initially generated image, as pointed out in the DM-GAN paper. Hence, we propose a method to provide good initialized images by incorporating perceptual understanding in the discriminator module. We improve the perceptual information at the first stage itself, which results in significant improvement in the final generated image. In this paper, we have applied our approach to the novel StackGAN architecture. We then show that the perceptual information included in the initial image is improved while modeling image distribution at multiple stages. Finally, we generated realistic multi-colored images conditioned by text. These images have good quality along with containing improved basic perceptual information. More importantly, the proposed method can be integrated into the pipeline of other state-of-the-art text-based-image-generation models to generate initial low-resolution images. We also worked on improving the refinement process in StackGAN by augmenting the third stage of the generator-discriminator pair in the StackGAN architecture. Our experimental analysis and comparison with the state-of-the-art on a large but sparse dataset MS COCO further validate the usefulness of our proposed approach. △ Less Submitted 2 July, 2020; originally announced July 2020. Comments: Proceedings of IEEE International Conference on Imaging, Vision & Pattern Recognition, (IVPR 2020, Japan) MSC Class: 68Txx; 68-XX ACM Class: I.4; I.5; I.3; I.2 Journal ref: Proceedings of IEEE International Conference on Imaging, Vision & Pattern Recognition, (IVPR 2020, Japan) arXiv:2002.06157 ?[ pdf , ps , other ]? cs.LG stat.ML Generalization and Representational Limits of Graph Neural Networks Authors: Vikas K. Garg , Stefanie Jegelka , Tommi Jaakkola Abstract : We address two fundamental questions about graph neural networks (GNNs). First, we prove that several important graph properties cannot be computed by GNNs that rely entirely on local information. Such GNNs include the standard message passing models, and more powerful spatial variants that exploit local graph structure (e.g., via relative orientation of messages, or local port ordering) to distin… ▽ More We address two fundamental questions about graph neural networks (GNNs). First, we prove that several important graph properties cannot be computed by GNNs that rely entirely on local information. Such GNNs include the standard message passing models, and more powerful spatial variants that exploit local graph structure (e.g., via relative orientation of messages, or local port ordering) to distinguish neighbors of each node. Our treatment includes a novel graph-theoretic formalism. Second, we provide the first data dependent generalization bounds for message passing GNNs. This analysis explicitly accounts for the local permutation invariance of GNNs. Our bounds are much tighter than existing VC-dimension based guarantees for GNNs, and are comparable to Rademacher bounds for recurrent neural networks. △ Less Submitted 14 February, 2020; originally announced February 2020. arXiv:2002.05660 ?[ pdf , other ]? cs.LG stat.ML Learn to Expect the Unexpected: Probably Approximately Correct Domain Generalization Authors: Vikas K. Garg , Adam Kalai , Katrina Ligett , Zhiwei Steven Wu Abstract : Domain generalization is the problem of machine learning when the training data and the test data come from different data domains. We present a simple theoretical model of learning to generalize across domains in which there is a meta-distribution over data distributions, and those data distributions may even have different supports. In our model, the training data given to a learning algorithm c… ▽ More Domain generalization is the problem of machine learning when the training data and the test data come from different data domains. We present a simple theoretical model of learning to generalize across domains in which there is a meta-distribution over data distributions, and those data distributions may even have different supports. In our model, the training data given to a learning algorithm consists of multiple datasets each from a single domain drawn in turn from the meta-distribution. We study this model in three different problem settings---a multi-domain Massart noise setting, a decision tree multi-dataset setting, and a feature selection setting, and find that computationally efficient, polynomial-sample domain generalization is possible in each. Experiments demonstrate that our feature selection algorithm indeed ignores spurious correlations and improves generalization. △ Less Submitted 13 February, 2020; originally announced February 2020. arXiv:2001.03133 ?[ pdf , other ]? cs.DM cs.MA A Generalization of Teo and Sethuraman's Median Stable Marriage Theorem Authors: Vijay K. Garg Abstract : Let $L$ be any finite distributive lattice and $B$ be any boolean predicate defined on $L$ such that the set of elements satisfying $B$ is a sublattice of $L$. Consider any subset $M$ of $L$ of size $k$ of elements of $L$ that satisfy $B$. Then, we show that $k$ generalized median elements generated from $M$ also satisfy $B$. We call this result generalized median theorem on finite distributive la… ▽ More Let $L$ be any finite distributive lattice and $B$ be any boolean predicate defined on $L$ such that the set of elements satisfying $B$ is a sublattice of $L$. Consider any subset $M$ of $L$ of size $k$ of elements of $L$ that satisfy $B$. Then, we show that $k$ generalized median elements generated from $M$ also satisfy $B$. We call this result generalized median theorem on finite distributive lattices. When this result is applied to the stable matching, we get Teo and Sethuraman's median stable matching theorem. Our proof is much simpler than that of Teo and Sethuraman. When the generalized median theorem is applied to the assignment problem, we get an analogous result for market clearing price vectors. △ Less Submitted 9 January, 2020; originally announced January 2020. Comments: 5 pages arXiv:1910.13386 ?[ pdf , ps , other ]? cs.DS cs.DC NC Algorithms for Popular Matchings in One-Sided Preference Systems and Related Problems Authors: Changyong Hu , Vijay K. Garg Abstract : The popular matching problem is of matching a set of applicants to a set of posts, where each applicant has a preference list, ranking a non-empty subset of posts in the order of preference, possibly with ties. A matching M is popular if there is no other matching M' such that more applicants prefer M' to M. We give the first NC algorithm to solve the popular matching problem without ties. We also… ▽ More The popular matching problem is of matching a set of applicants to a set of posts, where each applicant has a preference list, ranking a non-empty subset of posts in the order of preference, possibly with ties. A matching M is popular if there is no other matching M' such that more applicants prefer M' to M. We give the first NC algorithm to solve the popular matching problem without ties. We also give an NC algorithm that solves the maximum-cardinality popular matching problem. No NC or RNC algorithms were known for the matching problem in preference systems prior to this work. Moreover, we give an NC algorithm for a weaker version of the stable matching problem, that is, the problem of finding the "next" stable matching given a stable matching. △ Less Submitted 20 December, 2019; v1 submitted 23 October, 2019; originally announced October 2019. arXiv:1908.10408 ?[ pdf , other ]? cs.LG cs.IR stat.ML Multiresolution Transformer Networks: Recurrence is Not Essential for Modeling Hierarchical Structure Authors: Vikas K. Garg , Inderjit S. Dhillon , Hsiang-Fu Yu Abstract : The architecture of Transformer is based entirely on self-attention, and has been shown to outperform models that employ recurrence on sequence transduction tasks such as machine translation. The superior performance of Transformer has been attributed to propagating signals over shorter distances, between positions in the input and the output, compared to the recurrent architectures. We establish… ▽ More The architecture of Transformer is based entirely on self-attention, and has been shown to outperform models that employ recurrence on sequence transduction tasks such as machine translation. The superior performance of Transformer has been attributed to propagating signals over shorter distances, between positions in the input and the output, compared to the recurrent architectures. We establish connections between the dynamics in Transformer and recurrent networks to argue that several factors including gradient flow along an ensemble of multiple weakly dependent paths play a paramount role in the success of Transformer. We then leverage the dynamics to introduce {\em Multiresolution Transformer Networks} as the first architecture that exploits hierarchical structure in data via self-attention. Our models significantly outperform state-of-the-art recurrent and hierarchical recurrent models on two real-world datasets for query suggestion, namely, \aol and \amazon. In particular, on AOL data, our model registers at least 20\% improvement on each precision score, and over 25\% improvement on the BLEU score with respect to the best performing recurrent model. We thus provide strong evidence that recurrence is not essential for modeling hierarchical structure. △ Less Submitted 27 August, 2019; originally announced August 2019. Comments: Initial version arXiv:1905.12169 ?[ pdf , other ]? cs.LG stat.ML Strategic Prediction with Latent Aggregative Games Authors: Vikas K. Garg , Tommi Jaakkola Abstract : We introduce a new class of context dependent, incomplete information games to serve as structured prediction models for settings with significant strategic interactions. Our games map the input context to outcomes by first condensing the input into private player types that specify the utilities, weighted interactions, as well as the initial strategies for the players. The game is played over mul… ▽ More We introduce a new class of context dependent, incomplete information games to serve as structured prediction models for settings with significant strategic interactions. Our games map the input context to outcomes by first condensing the input into private player types that specify the utilities, weighted interactions, as well as the initial strategies for the players. The game is played over multiple rounds where players respond to weighted aggregates of their neighbors' strategies. The predicted output from the model is a mixed strategy profile (a near-Nash equilibrium) and each observation is thought of as a sample from this strategy profile. We introduce two new aggregator paradigms with provably convergent game dynamics, and characterize the conditions under which our games are identifiable from data. Our games can be parameterized in a transferable manner so that the sets of players can change from one game to another. We demonstrate empirically that our games as models can recover meaningful strategic interactions from real voting data. △ Less Submitted 28 May, 2019; originally announced May 2019. arXiv:1905.12158 ?[ pdf , other ]? cs.LG stat.ML Solving graph compression via optimal transport Authors: Vikas K. Garg , Tommi Jaakkola Abstract : We propose a new approach to graph compression by appeal to optimal transport. The transport problem is seeded with prior information about node importance, attributes, and edges in the graph. The transport formulation can be setup for either directed or undirected graphs, and its dual characterization is cast in terms of distributions over the nodes. The compression pertains to the support of nod… ▽ More We propose a new approach to graph compression by appeal to optimal transport. The transport problem is seeded with prior information about node importance, attributes, and edges in the graph. The transport formulation can be setup for either directed or undirected graphs, and its dual characterization is cast in terms of distributions over the nodes. The compression pertains to the support of node distributions and makes the problem challenging to solve directly. To this end, we introduce Boolean relaxations and specify conditions under which these relaxations are exact. The relaxations admit algorithms with provably fast convergence. Moreover, we provide an exact $O(d \log d)$ algorithm for the subproblem of projecting a $d$-dimensional vector to transformed simplex constraints. Our method outperforms state-of-the-art compression methods on graph classification. △ Less Submitted 28 May, 2019; originally announced May 2019. arXiv:1812.10499 ?[ pdf , other ]? cs.DC cs.DS Removing Sequential Bottleneck of Dijkstra's Algorithm for the Shortest Path Problem Authors: Vijay K. Garg Abstract : All traditional methods of computing shortest paths depend upon edge-relaxation where the cost of reaching a vertex from a source vertex is possibly decreased if that edge is used. We introduce a method which maintains lower bounds as well as upper bounds for reaching a vertex. This method enables one to find the optimal cost for multiple vertices in one iteration and thereby reduces the sequentia… ▽ More All traditional methods of computing shortest paths depend upon edge-relaxation where the cost of reaching a vertex from a source vertex is possibly decreased if that edge is used. We introduce a method which maintains lower bounds as well as upper bounds for reaching a vertex. This method enables one to find the optimal cost for multiple vertices in one iteration and thereby reduces the sequential bottleneck in Dijkstra's algorithm. We present four algorithms in this paper --- $SP_1$, $SP_2$, $SP_3$ and $SP_4$. $SP_1$ and $SP_2$ reduce the number of heap operations in Dijkstra's algorithm. For directed acyclic graphs, or directed unweighted graphs they have the optimal complexity of $O(e)$ where $e$ is the number of edges in the graph which is better than that of Dijkstra's algorithm. For general graphs, their worst case complexity matches that of Dijkstra's algorithm for a sequential implementation but allows for greater parallelism. Algorithms $SP_3$ and $SP_4$ allow for even more parallelism but with higher work complexity. Algorithm $SP_3$ requires $O(n + e(\max(\log n, Δ)))$ work where $n$ is the number of vertices and $Δ$ is the maximum in-degree of a node. Algorithm $SP_4$ has the most parallelism. It requires $O(ne)$ work. These algorithms generalize the work by Crauser, Mehlhorn, Meyer, and Sanders on parallelizing Dijkstra's algorithm. △ Less Submitted 26 December, 2018; originally announced December 2018. arXiv:1812.10431 ?[ pdf , other ]? cs.DS Applying Predicate Detection to the Constrained Optimization Problems Authors: Vijay K. Garg Abstract : We present a method to design parallel algorithms for constrained combinatorial optimization problems. Our method solves and generalizes many classical combinatorial optimization problems including the stable marriage problem, the shortest path problem and the market clearing price problem. These three problems are solved in the literature using Gale-Shapley algorithm, Dijkstra's algorithm, and De… ▽ More We present a method to design parallel algorithms for constrained combinatorial optimization problems. Our method solves and generalizes many classical combinatorial optimization problems including the stable marriage problem, the shortest path problem and the market clearing price problem. These three problems are solved in the literature using Gale-Shapley algorithm, Dijkstra's algorithm, and Demange, Gale, Sotomayor algorithm. Our method solves all these problems by casting them as searching for an element that satisfies an appropriate predicate in a distributive lattice. Moreover, it solves generalizations of all these problems - namely finding the optimal solution satisfying additional constraints called {\em lattice-linear} predicates. For stable marriage problems, an example of such a constraint is that Peter's regret is less than that of Paul. For shortest path problems, an example of such a constraint is that cost of reaching vertex $v_1$ is at least the cost of reaching vertex $v_2$. For the market clearing price problem, an example of such a constraint is that $item_1$ is priced at least as much as $item_2$. In addition to finding the optimal solution, our method is useful in enumerating all constrained stable matchings, and all constrained market clearing price vectors. △ Less Submitted 26 December, 2018; originally announced December 2018. arXiv:1810.07301 ?[ pdf , ps , other ]? cs.LG stat.ML Online Markov Decoding: Lower Bounds and Near-Optimal Approximation Algorithms Authors: Vikas K. Garg , Tamar Pichkhadze Abstract : We resolve the fundamental problem of online decoding with general $n^{th}$ order ergodic Markov chain models. Specifically, we provide deterministic and randomized algorithms whose performance is close to that of the optimal offline algorithm even when latency is small. Our algorithms admit efficient implementation via dynamic programs, and readily extend to (adversarial) non-stationary or time-v… ▽ More We resolve the fundamental problem of online decoding with general $n^{th}$ order ergodic Markov chain models. Specifically, we provide deterministic and randomized algorithms whose performance is close to that of the optimal offline algorithm even when latency is small. Our algorithms admit efficient implementation via dynamic programs, and readily extend to (adversarial) non-stationary or time-varying settings. We also establish lower bounds for online methods under latency constraints in both deterministic and randomized settings, and show that no online algorithm can perform significantly better than our algorithms. Empirically, just with latency one, our algorithm outperforms the online step algorithm by over 30\% in terms of decoding agreement with the optimal algorithm on genome sequence data. △ Less Submitted 30 May, 2019; v1 submitted 16 October, 2018; originally announced October 2018. Comments: Added experiments, fixed typos, and polished presentation. Currently under review arXiv:1810.05871 ?[ pdf , other ]? cs.DC Linearizable Replicated State Machines with Lattice Agreement Authors: Xiong Zheng , Vijay K. Garg , John Kaippallimalil Abstract : This paper studies the lattice agreement problem in asynchronous systems and explores its application to building linearizable replicated state machines (RSM). First, we propose an algorithm to solve the lattice agreement problem in $O(\log f)$ asynchronous rounds, where $f$ is the number of crash failures that the system can tolerate. This is an exponential improvement over the previous best uppe… ▽ More This paper studies the lattice agreement problem in asynchronous systems and explores its application to building linearizable replicated state machines (RSM). First, we propose an algorithm to solve the lattice agreement problem in $O(\log f)$ asynchronous rounds, where $f$ is the number of crash failures that the system can tolerate. This is an exponential improvement over the previous best upper bound. Second, Faleiro et al have shown in [Faleiro et al. PODC, 2012] that combination of conflict-free data types and lattice agreement protocols can be applied to implement linearizable RSM. They give a Paxos style lattice agreement protocol, which can be adapted to implement linearizable RSM and guarantee that a command can be learned in at most $O(n)$ message delays, where $n$ is the number of proposers. Later on, Xiong et al in [Xiong et al. DISC, 2018] give a lattice agreement protocol which improves the $O(n)$ guarantee to be $O(f)$. However, neither protocols is practical for building a linearizable RSM. Thus, in the second part of the paper, we first give an improved protocol based on the one proposed by Xiong et al. Then, we implement a simple linearizable RSM using the our improved protocol and compare our implementation with an open source Java implementation of Paxos. Results show that better performance can be obtained by using lattice agreement based protocols to implement a linearizable RSM compared to traditional consensus based protocols. △ Less Submitted 13 October, 2018; originally announced October 2018. arXiv:1808.01363 ?[ pdf , other ]? cs.NE GeneSys: Enabling Continuous Learning through Neural Network Evolution in Hardware Authors: Ananda Samajdar , Parth Mannan , Kartikay Garg , Tushar Krishna Abstract : Modern deep learning systems rely on (a) a hand-tuned neural network topology, (b) massive amounts of labeled training data, and (c) extensive training over large-scale compute resources to build a system that can perform efficient image classification or speech recognition. Unfortunately, we are still far away from implementing adaptive general purpose intelligent systems which would need to lear… ▽ More Modern deep learning systems rely on (a) a hand-tuned neural network topology, (b) massive amounts of labeled training data, and (c) extensive training over large-scale compute resources to build a system that can perform efficient image classification or speech recognition. Unfortunately, we are still far away from implementing adaptive general purpose intelligent systems which would need to learn autonomously in unknown environments and may not have access to some or any of these three components. Reinforcement learning and evolutionary algorithm (EA) based methods circumvent this problem by continuously interacting with the environment and updating the models based on obtained rewards. However, deploying these algorithms on ubiquitous autonomous agents at the edge (robots/drones) demands extremely high energy-efficiency due to (i) tight power and energy budgets, (ii) continuous/lifelong interaction with the environment, (iii) intermittent or no connectivity to the cloud to run heavy-weight processing. To address this need, we present GENESYS, an HW-SW prototype of an EA-based learning system, that comprises a closed loop learning engine called EvE and an inference engine called ADAM. EvE can evolve the topology and weights of neural networks completely in hardware for the task at hand, without requiring hand-optimization or backpropagation training. ADAM continuously interacts with the environment and is optimized for efficiently running the irregular neural networks generated by EvE. GENESYS identifies and leverages multiple unique avenues of parallelism unique to EAs that we term 'gene'- level parallelism, and 'population'-level parallelism. We ran GENESYS with a suite of environments from OpenAI gym and observed 2-5 orders of magnitude higher energy-efficiency over state-of-the-art embedded and desktop CPU and GPU systems. △ Less Submitted 13 September, 2018; v1 submitted 3 August, 2018; originally announced August 2018. Comments: This work is accepted and will appear in MICRO-51 arXiv:1807.11557 ?[ pdf , other ]? cs.DC Lattice Agreement in Message Passing Systems Authors: Xiong Zheng , Changyong Hu , Vijay K. Garg Abstract : This paper studies the lattice agreement problem and the generalized lattice agreement problem in distributed message passing systems. In the lattice agreement problem, given input values from a lattice, processes have to non-trivially decide output values that lie on a chain. We consider the lattice agreement problem in both synchronous and asynchronous systems. For synchronous lattice agreement,… ▽ More This paper studies the lattice agreement problem and the generalized lattice agreement problem in distributed message passing systems. In the lattice agreement problem, given input values from a lattice, processes have to non-trivially decide output values that lie on a chain. We consider the lattice agreement problem in both synchronous and asynchronous systems. For synchronous lattice agreement, we present two algorithms which run in $\log f$ and $\min \{O(\log^2 h(L)), O(\log^2 f)\}$ rounds, respectively, where $h(L)$ denotes the height of the {\em input sublattice} $L$, $f < n$ is the number of crash failures the system can tolerate, and $n$ is the number of processes in the system. These algorithms have significant better round complexity than previously known algorithms. The algorithm by Attiya et al. \cite{attiya1995atomic} takes $\log n$ synchronous rounds, and the algorithm by Mavronicolasa \cite{mavronicolasabound} takes $\min \{O(h(L)), O(\sqrt{f})\}$ rounds. For asynchronous lattice agreement, we propose an algorithm which has time complexity of $2 \cdot \min \{h(L), f + 1\}$ message delays which improves on the previously known time complexity of $O(n)$ message delays. The generalized lattice agreement problem defined by Faleiro et al in \cite{faleiro2012generalized} is a generalization of the lattice agreement problem where it is applied for the replicated state machine. We propose an algorithm which guarantees liveness when a majority of the processes are correct in asynchronous systems. Our algorithm requires $\min \{O(h(L)), O(f)\}$ units of time in the worst case which is better than $O(n)$ units of time required by the algorithm of Faleiro et al. \cite{faleiro2012generalized}. △ Less Submitted 30 July, 2018; originally announced July 2018. arXiv:1803.02388 ?[ pdf , other ]? cs.LG Learning SMaLL Predictors Authors: Vikas K. Garg , Ofer Dekel , Lin Xiao Abstract : We present a new machine learning technique for training small resource-constrained predictors. Our algorithm, the Sparse Multiprototype Linear Learner (SMaLL), is inspired by the classic machine learning problem of learning $k$-DNF Boolean formulae. We present a formal derivation of our algorithm and demonstrate the benefits of our approach with a detailed empirical study. We present a new machine learning technique for training small resource-constrained predictors. Our algorithm, the Sparse Multiprototype Linear Learner (SMaLL), is inspired by the classic machine learning problem of learning $k$-DNF Boolean formulae. We present a formal derivation of our algorithm and demonstrate the benefits of our approach with a detailed empirical study. △ Less Submitted 6 March, 2018; originally announced March 2018. arXiv:1801.06161 ?[ pdf , other ]? cs.SI physics.soc-ph Topic Lifecycle on Social Networks: Analyzing the Effects of Semantic Continuity and Social Communities Authors: Kuntal Dey , Saroj Kaushik , Kritika Garg , Ritvik Shrivastava Abstract : Topic lifecycle analysis on Twitter, a branch of study that investigates Twitter topics from their birth through lifecycle to death, has gained immense mainstream research popularity. In the literature, topics are often treated as one of (a) hashtags (independent from other hashtags), (b) a burst of keywords in a short time span or (c) a latent concept space captured by advanced text analysis meth… ▽ More Topic lifecycle analysis on Twitter, a branch of study that investigates Twitter topics from their birth through lifecycle to death, has gained immense mainstream research popularity. In the literature, topics are often treated as one of (a) hashtags (independent from other hashtags), (b) a burst of keywords in a short time span or (c) a latent concept space captured by advanced text analysis methodologies, such as Latent Dirichlet Allocation (LDA). The first two approaches are not capable of recognizing topics where different users use different hashtags to express the same concept (semantically related), while the third approach misses out the user's explicit intent expressed via hashtags. In our work, we use a word embedding based approach to cluster different hashtags together, and the temporal concurrency of the hashtag usages, thus forming topics (a semantically and temporally related group of hashtags).We present a novel analysis of topic lifecycles with respect to communities. We characterize the participation of social communities in the topic clusters, and analyze the lifecycle of topic clusters with respect to such participation. We derive first-of-its-kind novel insights with respect to the complex evolution of topics over communities and time: temporal morphing of topics over hashtags within communities, how the hashtags die in some communities but morph into some other hashtags in some other communities (that, it is a community-level phenomenon), and how specific communities adopt to specific hashtags. Our work is fundamental in the space of topic lifecycle modeling and understanding in communities: it redefines our understanding of topic lifecycles and shows that the social boundaries of topic lifecycles are deeply ingrained with community behavior. △ Less Submitted 18 January, 2018; originally announced January 2018. Comments: 12 pages, 5 figures (13 figures if sub-figures are counted separately), To Appear in ECIR 2018 arXiv:1710.00069 ?[ pdf , other ]? cs.HC cs.CY doi 10.1145/3143402 When Simpler Data Does Not Imply Less Information: A Study of User Profiling Scenarios with Constrained View of Mobile HTTP(S) Traffic Authors: Souneil Park , Aleksandar Matic , Kamini Garg , Nuria Oliver Abstract : The exponential growth in smartphone adoption is contributing to the availability of vast amounts of human behavioral data. This data enables the development of increasingly accurate data-driven user models that facilitate the delivery of personalized services which are often free in exchange for the use of its customers' data. Although such usage conventions have raised many privacy concerns, the… ▽ More The exponential growth in smartphone adoption is contributing to the availability of vast amounts of human behavioral data. This data enables the development of increasingly accurate data-driven user models that facilitate the delivery of personalized services which are often free in exchange for the use of its customers' data. Although such usage conventions have raised many privacy concerns, the increasing value of personal data is motivating diverse entities to aggressively collect and exploit the data. In this paper, we unfold profiling scenarios around mobile HTTP(S) traffic, focusing on those that have limited but meaningful segments of the data. The capability of the scenarios to profile personal information is examined with real user data, collected in-the-wild from 61 mobile phone users for a minimum of 30 days. Our study attempts to model heterogeneous user traits and interests, including personality, boredom proneness, demographics, and shopping interests. Based on our modeling results, we discuss various implications to personalization, privacy, and personal data rights. △ Less Submitted 29 September, 2017; originally announced October 2017. Journal ref: ACM Trans. Web Volume 12 Issue 2, January 2018 arXiv:1709.05262 ?[ pdf , other ]? cs.AI cs.LG stat.ML Supervising Unsupervised Learning Authors: Vikas K. Garg , Adam Kalai Abstract : We introduce a framework to leverage knowledge acquired from a repository of (heterogeneous) supervised datasets to new unsupervised datasets. Our perspective avoids the subjectivity inherent in unsupervised learning by reducing it to supervised learning, and provides a principled way to evaluate unsupervised algorithms. We demonstrate the versatility of our framework via simple agnostic bounds on… ▽ More We introduce a framework to leverage knowledge acquired from a repository of (heterogeneous) supervised datasets to new unsupervised datasets. Our perspective avoids the subjectivity inherent in unsupervised learning by reducing it to supervised learning, and provides a principled way to evaluate unsupervised algorithms. We demonstrate the versatility of our framework via simple agnostic bounds on unsupervised problems. In the context of clustering, our approach helps choose the number of clusters and the clustering algorithm, remove the outliers, and provably circumvent the Kleinberg's impossibility result. Experimental results across hundreds of problems demonstrate improved performance on unsupervised data with simple algorithms, despite the fact that our problems come from heterogeneous domains. Additionally, our framework lets us leverage deep networks to learn common features from many such small datasets, and perform zero shot learning. △ Less Submitted 16 February, 2018; v1 submitted 14 September, 2017; originally announced September 2017. Comments: 11 two column pages. arXiv admin note: substantial text overlap with arXiv:1612.09030 arXiv:1709.01586 ?[ pdf , other ]? eess.SY cs.MA doi 10.1109/CDC.2017.8264163 Robust Semi-Cooperative Multi-Agent Coordination in the Presence of Stochastic Disturbances Authors: Kunal Garg , Dongkun Han , Dimitra Panagou Abstract : This paper presents a robust distributed coordination protocol that achieves generation of collision-free trajectories for multiple unicycle agents in the presence of stochastic uncertainties. We build upon our earlier work on semi-cooperative coordination and we redesign the coordination controllers so that the agents counteract a class of state (wind) disturbances and measurement noise. Safety a… ▽ More This paper presents a robust distributed coordination protocol that achieves generation of collision-free trajectories for multiple unicycle agents in the presence of stochastic uncertainties. We build upon our earlier work on semi-cooperative coordination and we redesign the coordination controllers so that the agents counteract a class of state (wind) disturbances and measurement noise. Safety and convergence is proved analytically, while simulation results demonstrate the efficacy of the proposed solution. △ Less Submitted 5 January, 2018; v1 submitted 5 September, 2017; originally announced September 2017. Comments: K. Garg, D. Han and D. Panagou "Robust Semi-Cooperative Multi-Agent Coordination in the Presence of Stochastic Disturbances", 56th IEEE Conf. on Decision and Control, Melbourne, Australia, December 2017 arXiv:1707.05399 ?[ pdf , other ]? cs.AR cs.ET doi 10.1109/ISPASS.2018.00018 Performance Implications of NoCs on 3D-Stacked Memories: Insights from the Hybrid Memory Cube Authors: Ramyad Hadidi , Bahar Asgari , Jeffrey Young , Burhan Ahmad Mudassar , Kartikay Garg , Tushar Krishna , Hyesoon Kim Abstract : Memories that exploit three-dimensional (3D)-stacking technology, which integrate memory and logic dies in a single stack, are becoming popular. These memories, such as Hybrid Memory Cube (HMC), utilize a network-on-chip (NoC) design for connecting their internal structural organizations. This novel usage of NoC, in addition to aiding processing-in-memory capabilities, enables numerous benefits su… ▽ More Memories that exploit three-dimensional (3D)-stacking technology, which integrate memory and logic dies in a single stack, are becoming popular. These memories, such as Hybrid Memory Cube (HMC), utilize a network-on-chip (NoC) design for connecting their internal structural organizations. This novel usage of NoC, in addition to aiding processing-in-memory capabilities, enables numerous benefits such as high bandwidth and memory-level parallelism. However, the implications of NoCs on the characteristics of 3D-stacked memories in terms of memory access latency and bandwidth have not been fully explored. This paper addresses this knowledge gap by (i) characterizing an HMC prototype on the AC-510 accelerator board and revealing its access latency behaviors, and (ii) by investigating the implications of such behaviors on system and software designs. △ Less Submitted 13 February, 2018; v1 submitted 17 July, 2017; originally announced July 2017. Journal ref: 2018 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS) arXiv:1612.09030 ?[ pdf , other ]? cs.LG cs.AI cs.CV Meta-Unsupervised-Learning: A supervised approach to unsupervised learning Authors: Vikas K. Garg , Adam Tauman Kalai Abstract : We introduce a new paradigm to investigate unsupervised learning, reducing unsupervised learning to supervised learning. Specifically, we mitigate the subjectivity in unsupervised decision-making by leveraging knowledge acquired from prior, possibly heterogeneous, supervised learning tasks. We demonstrate the versatility of our framework via comprehensive expositions and detailed experiments on se… ▽ More We introduce a new paradigm to investigate unsupervised learning, reducing unsupervised learning to supervised learning. Specifically, we mitigate the subjectivity in unsupervised decision-making by leveraging knowledge acquired from prior, possibly heterogeneous, supervised learning tasks. We demonstrate the versatility of our framework via comprehensive expositions and detailed experiments on several unsupervised problems such as (a) clustering, (b) outlier detection, and (c) similarity prediction under a common umbrella of meta-unsupervised-learning. We also provide rigorous PAC-agnostic bounds to establish the theoretical foundations of our framework, and show that our framing of meta-clustering circumvents Kleinberg's impossibility theorem for clustering. △ Less Submitted 3 January, 2017; v1 submitted 28 December, 2016; originally announced December 2016. Comments: 22 pages arXiv:1602.06488 ?[ pdf ]? cs.DC IOTSim: a Cloud based Simulator for Analysing IoT Applications Authors: Xuezhi Zeng , Saurabh Kumar Garg , Peter Strazdins , Prem Jayaraman , Dimitrios Georgakopoulos , Rajiv Ranjan Abstract : A disruptive technology that is influencing not only computing paradigm but every other business is the rise of big data. Internet of Things (IoT) applications are considered to be a major source of big data. Such IoT applications are in general supported through clouds where data is stored and processed by big data processing systems. In order to improve the efficiency of cloud infrastructure so… ▽ More A disruptive technology that is influencing not only computing paradigm but every other business is the rise of big data. Internet of Things (IoT) applications are considered to be a major source of big data. Such IoT applications are in general supported through clouds where data is stored and processed by big data processing systems. In order to improve the efficiency of cloud infrastructure so that they can efficiently support IoT big data applications, it is important to understand how these applications and the corresponding big data processing systems will perform in cloud computing environments. However, given the scalability and complex requirements of big data processing systems, an empirical evaluation on actual cloud infrastructure can hinder the development of timely and cost effective IoT solutions. Therefore, a simulator supporting IoT applications in cloud environment is highly demanded, but such work is still in its infancy. To fill this gap, we have designed and implemented IOTSim which supports and enables simulation of IoT big data processing using MapReduce model in cloud computing environment. A real case study validates the efficacy of the simulator. △ Less Submitted 20 February, 2016; originally announced February 2016. arXiv:1509.08086 ?[ pdf , other ]? cs.AI math.OC doi 10.12732/ijpam.v103i2.19 Optimal Release Time Decision from Fuzzy Mathematical Programming Perspective Authors: Arvind Kumar , Adarsh Anand , Pankaj Kumar Garg , Mohini Agarwal Abstract : Demand for high software reliability requires rigorous testing followed by requirement of robust modeling techniques for software quality prediction. On one side, firms have to steadily manage the reliability by testing it vigorously, the optimal release time determination is their biggest concern. In past many models have been developed and much research has been devoted towards assessment of rel… ▽ More Demand for high software reliability requires rigorous testing followed by requirement of robust modeling techniques for software quality prediction. On one side, firms have to steadily manage the reliability by testing it vigorously, the optimal release time determination is their biggest concern. In past many models have been developed and much research has been devoted towards assessment of release time of software. However, majority of the work deals in crisp study. This paper addresses the problem of release time prediction using fuzzy Logic. Here we have formulated a Fuzzy release time problem considering the cost of testing under the impact of warranty period. Results show that fuzzy model has good adaptability. △ Less Submitted 27 September, 2015; originally announced September 2015. Comments: 10 Pages. arXiv admin note: substantial overlap with text by other authors http://archive.org/stream/Software_Reliability_Assessment_with_OR_Applications/Software_Reliability_Assessment_with_OR_Applications_djvu.txt MSC Class: 90C29 ? 90C70 ? 90C90 Journal ref: International Journal of Pure and Applied Mathematics, Volume 103 No. 2 2015, 359-376 arXiv:1506.07609 ?[ pdf , other ]? cs.LG stat.ML CRAFT: ClusteR-specific Assorted Feature selecTion Authors: Vikas K. Garg , Cynthia Rudin , Tommi Jaakkola Abstract : We present a framework for clustering with cluster-specific feature selection. The framework, CRAFT, is derived from asymptotic log posterior formulations of nonparametric MAP-based clustering models. CRAFT handles assorted data, i.e., both numeric and categorical data, and the underlying objective functions are intuitively appealing. The resulting algorithm is simple to implement and scales nicel… ▽ More We present a framework for clustering with cluster-specific feature selection. The framework, CRAFT, is derived from asymptotic log posterior formulations of nonparametric MAP-based clustering models. CRAFT handles assorted data, i.e., both numeric and categorical data, and the underlying objective functions are intuitively appealing. The resulting algorithm is simple to implement and scales nicely, requires minimal parameter tuning, obviates the need to specify the number of clusters a priori, and compares favorably with other methods on real datasets. △ Less Submitted 25 June, 2015; originally announced June 2015. arXiv:1504.04871 ?[ pdf , ps , other ]? cs.CV DEEP-CARVING: Discovering Visual Attributes by Carving Deep Neural Nets Authors: Sukrit Shankar , Vikas K. Garg , Roberto Cipolla Abstract : Most of the approaches for discovering visual attributes in images demand significant supervision, which is cumbersome to obtain. In this paper, we aim to discover visual attributes in a weakly supervised setting that is commonly encountered with contemporary image search engines. Deep Convolutional Neural Networks (CNNs) have enjoyed remarkable success in vision applications recently. However, in… ▽ More Most of the approaches for discovering visual attributes in images demand significant supervision, which is cumbersome to obtain. In this paper, we aim to discover visual attributes in a weakly supervised setting that is commonly encountered with contemporary image search engines. Deep Convolutional Neural Networks (CNNs) have enjoyed remarkable success in vision applications recently. However, in a weakly supervised scenario, widely used CNN training procedures do not learn a robust model for predicting multiple attribute labels simultaneously. The primary reason is that the attributes highly co-occur within the training data. To ameliorate this limitation, we propose Deep-Carving, a novel training procedure with CNNs, that helps the net efficiently carve itself for the task of multiple attribute prediction. During training, the responses of the feature maps are exploited in an ingenious way to provide the net with multiple pseudo-labels (for training images) for subsequent iterations. The process is repeated periodically after a fixed number of iterations, and enables the net carve itself iteratively for efficiently disentangling features. Additionally, we contribute a noun-adjective pairing inspired Natural Scenes Attributes Dataset to the research community, CAMIT - NSAD, containing a number of co-occurring attributes within a noun category. We describe, in detail, salient aspects of this dataset. Our experiments on CAMIT-NSAD and the SUN Attributes Dataset, with weak supervision, clearly demonstrate that the Deep-Carved CNNs consistently achieve considerable improvement in the precision of attribute prediction over popular baseline methods. △ Less Submitted 19 April, 2015; originally announced April 2015. Comments: 10 pages, 8 figures, CVPR 2015 arXiv:1410.1209 ?[ pdf , ps , other ]? cs.DC Necessary and Sufficient Conditions on Partial Orders for Modeling Concurrent Computations Authors: Himanshu Chauhan , Vijay K. Garg Abstract : Partial orders are used extensively for modeling and analyzing concurrent computations. In this paper, we define two properties of partially ordered sets: width-extensibility and interleaving-consistency, and show that a partial order can be a valid state based model: (1) of some synchronous concurrent computation iff it is width-extensible, and (2) of some asynchronous concurrent computation iff… ▽ More Partial orders are used extensively for modeling and analyzing concurrent computations. In this paper, we define two properties of partially ordered sets: width-extensibility and interleaving-consistency, and show that a partial order can be a valid state based model: (1) of some synchronous concurrent computation iff it is width-extensible, and (2) of some asynchronous concurrent computation iff it is width-extensible and interleaving-consistent. We also show a duality between the event based and state based models of concurrent computations, and give algorithms to convert models between the two domains. When applied to the problem of checkpointing, our theory leads to a better understanding of some existing results and algorithms in the field. It also leads to efficient detection algorithms for predicates whose evaluation requires knowledge of states from all the processes in the system. △ Less Submitted 5 October, 2014; originally announced October 2014. arXiv:1408.0818 ?[ pdf , ps , other ]? cs.DC cs.PL ActiveMonitor: Non-blocking Monitor Executions for Increased Parallelism Authors: Weil-Lun Hung , Himanshu Chauhan , Vijay K. Garg Abstract : We present a set of novel ideas on design and implementation of monitor objects for multi-threaded programs. Our approach has two main goals: (a) increase parallelism in monitor objects and thus provide performance gains (shorter runtimes) for multi-threaded programs, and (b) introduce constructs that allow programmers to easily write monitor-based multi-threaded programs that can achieve these pe… ▽ More We present a set of novel ideas on design and implementation of monitor objects for multi-threaded programs. Our approach has two main goals: (a) increase parallelism in monitor objects and thus provide performance gains (shorter runtimes) for multi-threaded programs, and (b) introduce constructs that allow programmers to easily write monitor-based multi-threaded programs that can achieve these performance gains. We describe the concepts of our framework, called ActiveMonitor, and its prototype implementation using futures. We evaluate its performance in terms of runtimes of multi-threaded programs on linked-list, bounded-buffer, and other fundamental problems implemented in Java. We compare the runtimes of our implementation against implementations using Java's reentrant locks, recently proposed automatic signaling framework AutoSynch, and some other techniques from the literature. The results of of the evaluation indicate that monitors based on our framework provide significant gains in runtime performance in comparison to traditional monitors implemented using Java's reentrant locks. △ Less Submitted 4 August, 2014; originally announced August 2014. arXiv:1304.4326 ?[ pdf , ps , other ]? cs.DC Distributed Abstraction Algorithm for Online Predicate Detection Authors: Himanshu Chauhan , Vijay K. Garg , Aravind Natarajan , Neeraj Mittal Abstract : Analyzing a distributed computation is a hard problem in general due to the combinatorial explosion in the size of the state-space with the number of processes in the system. By abstracting the computation, unnecessary explorations can be avoided. Computation slicing is an approach for abstracting dis- tributed computations with respect to a given predicate. We focus on regular predicates, a famil… ▽ More Analyzing a distributed computation is a hard problem in general due to the combinatorial explosion in the size of the state-space with the number of processes in the system. By abstracting the computation, unnecessary explorations can be avoided. Computation slicing is an approach for abstracting dis- tributed computations with respect to a given predicate. We focus on regular predicates, a family of predicates that covers a large number of commonly used predicates for runtime verification. The existing algorithms for computation slicing are centralized in nature in which a single process is responsible for computing the slice in either offline or online manner. In this paper, we present a distributed online algorithm for computing the slice of a distributed computation with respect to a regular predicate. Our algorithm distributes the work and storage requirements across the system, thus reducing the space and computation complexities per process. In addition, for conjunctive predicates, our algorithm also reduces the message load per process. △ Less Submitted 4 June, 2013; v1 submitted 15 April, 2013; originally announced April 2013. arXiv:1303.5891 ?[ pdf , ps , other ]? cs.DC Fault Tolerance in Distributed Systems using Fused State Machines Authors: Bharath Balasubramanian , Vijay K. Garg Abstract : Replication is a standard technique for fault tolerance in distributed systems modeled as deterministic finite state machines (DFSMs or machines). To correct f crash or f/2 Byzantine faults among n different machines, replication requires nf additional backup machines. We present a solution called fusion that requires just f additional backup machines. First, we build a framework for fault toleran… ▽ More Replication is a standard technique for fault tolerance in distributed systems modeled as deterministic finite state machines (DFSMs or machines). To correct f crash or f/2 Byzantine faults among n different machines, replication requires nf additional backup machines. We present a solution called fusion that requires just f additional backup machines. First, we build a framework for fault tolerance in DFSMs based on the notion of Hamming distances. We introduce the concept of an (f,m)-fusion, which is a set of m backup machines that can correct f crash faults or f/2 Byzantine faults among a given set of machines. Second, we present an algorithm to generate an (f,f)-fusion for a given set of machines. We ensure that our backups are efficient in terms of the size of their state and event sets. Our evaluation of fusion on the widely used MCNC'91 benchmarks for DFSMs show that the average state space savings in fusion (over replication) is 38% (range 0-99%). To demonstrate the practical use of fusion, we describe its potential application to the MapReduce framework. Using a simple case study, we compare replication and fusion as applied to this framework. While a pure replication-based solution requires 1.8 million map tasks, our fusion-based solution requires only 1.4 million map tasks with minimal overhead during normal operation or recovery. Hence, fusion results in considerable savings in state space and other resources such as the power needed to run the backup tasks. △ Less Submitted 23 March, 2013; originally announced March 2013. Comments: This is under review with the Distributed Computing journal arXiv:1303.0276 ?[ pdf , ps , other ]? cs.DC cs.PL AutoSynch: An Automatic-Signal Monitor Based on Predicate Tagging Authors: Wei-Lun Hung , Vijay K. Garg Abstract : Most programming languages use monitors with explicit signals for synchronization in shared-memory programs. Requiring program- mers to signal threads explicitly results in many concurrency bugs due to missed notifications, or notifications on wrong condition variables. In this paper, we describe an implementation of an au- tomatic signaling monitor in Java called AutoSynch that eliminates such co… ▽ More Most programming languages use monitors with explicit signals for synchronization in shared-memory programs. Requiring program- mers to signal threads explicitly results in many concurrency bugs due to missed notifications, or notifications on wrong condition variables. In this paper, we describe an implementation of an au- tomatic signaling monitor in Java called AutoSynch that eliminates such concurrency bugs by removing the burden of signaling from the programmer. We show that the belief that automatic signaling monitors are prohibitively expensive is wrong. For most problems, programs based on AutoSynch are almost as fast as those based on explicit signaling. For some, AutoSynch is even faster than explicit signaling because it never uses signalAll, whereas the programmers end up using signalAll with the explicit signal mechanism. AutoSynch achieves efficiency in synchronization based on three novel ideas. We introduce an operation called globalization that enables the predicate evaluation in every thread, thereby reducing context switches during the execution of the program. Secondly, AutoSynch avoids signalAll by using a property called relay invari- ance that guarantees that whenever possible there is always at least one thread whose condition is true which has been signaled. Finally, AutoSynch uses a technique called predicate tagging to efficiently determine a thread that should be signaled. To evaluate the effi- ciency of AutoSynch, we have implemented many different well- known synchronization problems such as the producers/consumers problem, the readers/writers problems, and the dining philosophers problem. The results show that AutoSynch is almost as efficient as the explicit-signal monitor and even more efficient for some cases. △ Less Submitted 1 March, 2013; originally announced March 2013. Comments: 10 pages, 15 figures arXiv:1302.2543 ?[ pdf , other ]? cs.DC Byzantine Vector Consensus in Complete Graphs Authors: Nitin H. Vaidya , Vijay K. Garg Abstract : Consider a network of n processes each of which has a d-dimensional vector of reals as its input. Each process can communicate directly with all the processes in the system; thus the communication network is a complete graph. All the communication channels are reliable and FIFO (first-in-first-out). The problem of Byzantine vector consensus (BVC) requires agreement on a d-dimensional vector that i… ▽ More Consider a network of n processes each of which has a d-dimensional vector of reals as its input. Each process can communicate directly with all the processes in the system; thus the communication network is a complete graph. All the communication channels are reliable and FIFO (first-in-first-out). The problem of Byzantine vector consensus (BVC) requires agreement on a d-dimensional vector that is in the convex hull of the d-dimensional input vectors at the non-faulty processes. We obtain the following results for Byzantine vector consensus in complete graphs while tolerating up to f Byzantine failures: We prove that in a synchronous system, n >= max(3f+1, (d+1)f+1) is necessary and sufficient for achieving Byzantine vector consensus. In an asynchronous system, it is known that exact consensus is impossible in presence of faulty processes. For an asynchronous system, we prove that n >= (d+2)f+1 is necessary and sufficient to achieve approximate Byzantine vector consensus. Our sufficiency proofs are constructive. We show sufficiency by providing explicit algorithms that solve exact BVC in synchronous systems, and approximate BVC in asynchronous systems. We also obtain tight bounds on the number of processes for achieving BVC using algorithms that are restricted to a simpler communication pattern. △ Less Submitted 11 February, 2013; originally announced February 2013. arXiv:1201.4522 ?[ pdf ]? cs.DC cs.NI doi 10.1109/CSC.2011.6138522 SLA-Oriented Resource Provisioning for Cloud Computing: Challenges, Architecture, and Solutions Authors: Rajkumar Buyya , Saurabh Kumar Garg , Rodrigo N. Calheiros Abstract : Cloud computing systems promise to offer subscription-oriented, enterprise-quality computing services to users worldwide. With the increased demand for delivering services to a large number of users, they need to offer differentiated services to users and meet their quality expectations. Existing resource management systems in data centers are yet to support Service Level Agreement (SLA)-oriented… ▽ More Cloud computing systems promise to offer subscription-oriented, enterprise-quality computing services to users worldwide. With the increased demand for delivering services to a large number of users, they need to offer differentiated services to users and meet their quality expectations. Existing resource management systems in data centers are yet to support Service Level Agreement (SLA)-oriented resource allocation, and thus need to be enhanced to realize cloud computing and utility computing. In addition, no work has been done to collectively incorporate customer-driven service management, computational risk management, and autonomic resource management into a market-based resource management system to target the rapidly changing enterprise requirements of Cloud computing. This paper presents vision, challenges, and architectural elements of SLA-oriented resource management. The proposed architecture supports integration of marketbased provisioning policies and virtualisation technologies for flexible allocation of resources to applications. The performance results obtained from our working prototype system shows the feasibility and effectiveness of SLA-based resource provisioning in Clouds. △ Less Submitted 21 January, 2012; originally announced January 2012. Comments: 10 pages, 7 figures, Conference Keynote Paper: 2011 IEEE International Conference on Cloud and Service Computing (CSC 2011, IEEE Press, USA), Hong Kong, China, December 12-14, 2011 ACM Class: C.1.4 Journal ref: Proceedings of the 2011 IEEE International Conference on Cloud and Service Computing (CSC 2011, IEEE Press, USA), Hong Kong, China, December 12-14, 2011 arXiv:1112.2058 ?[ pdf ]? cs.NI Symmetrical Dispersion Compensation For High Speed Optical Links Authors: Ojuswini Arora , Dr. Amit kumar Garg , Savita Punia Abstract : In this paper, the performance of high speed optical fiber based network is analysed by using dispersion compensating module (DCM). The optimal operating condition of the DCM is obtained by considering dispersion management configurations for the symmetrical system i.e Pre-compensation & Post-compensation. The dispersion compensating fiber (DCF) is tested for a single span, single channel system o… ▽ More In this paper, the performance of high speed optical fiber based network is analysed by using dispersion compensating module (DCM). The optimal operating condition of the DCM is obtained by considering dispersion management configurations for the symmetrical system i.e Pre-compensation & Post-compensation. The dispersion compensating fiber (DCF) is tested for a single span, single channel system operating at a speed of 10 Gb/s with a transmitting wavelength of 1550 nm, over 120 km single mode fibre by using the compensating fiber for 24 km,30km and 35Km. So far, most of the investigations for single mode fiber (SMF) transmission at high amplifier spacings in the order of 90 km to 120 km is focused on conventional Non Return to Zero(NRZ) format. The simulation results are validated by analysing the Q-factor and Bit error rate (BER) in the numerical simulator OptSim. △ Less Submitted 9 December, 2011; originally announced December 2011. Comments: 6 pages, 6 figures, IJCSI journal Journal ref: IJCSI International Journal of Computer Science Issues, Vol. 8, Issue 6, No 1, November 2011 ISSN (Online): 1694-0814 www.IJCSI.org arXiv:1110.5972 ?[ pdf , other ]? cs.DC doi 10.1007/978-3-642-24650-0_34 Provisioning Spot Market Cloud Resources to Create Cost-effective Virtual Clusters Authors: William Voorsluys , Saurabh Kumar Garg , Rajkumar Buyya Abstract : Infrastructure-as-a-Service providers are offering their unused resources in the form of variable-priced virtual machines (VMs), known as "spot instances", at prices significantly lower than their standard fixed-priced resources. To lease spot instances, users specify a maximum price they are willing to pay per hour and VMs will run only when the current price is lower than the user's bid. This pa… ▽ More Infrastructure-as-a-Service providers are offering their unused resources in the form of variable-priced virtual machines (VMs), known as "spot instances", at prices significantly lower than their standard fixed-priced resources. To lease spot instances, users specify a maximum price they are willing to pay per hour and VMs will run only when the current price is lower than the user's bid. This paper proposes a resource allocation policy that addresses the problem of running deadline-constrained compute-intensive jobs on a pool of composed solely of spot instances, while exploiting variations in price and performance to run applications in a fast and economical way. Our policy relies on job runtime estimations to decide what are the best types of VMs to run each job and when jobs should run. Several estimation methods are evaluated and compared, using trace-based simulations, which take real price variation traces obtained from Amazon Web Services as input, as well as an application trace from the Parallel Workload Archive. Results demonstrate the effectiveness of running computational jobs on spot instances, at a fraction (up to 60% lower) of the price that would normally cost on fixed priced resources. △ Less Submitted 26 October, 2011; originally announced October 2011. Comments: 14 pages, 4 figures, 11th International Conference on Algorithms and Architectures for Parallel Processing (ICA3PP-11); Lecture Notes in Computer Science, Vol. 7016, 2011 arXiv:0909.1146 ?[ pdf , other ]? cs.DC Energy-Efficient Scheduling of HPC Applications in Cloud Computing Environments Authors: Saurabh Kumar Garg , Chee Shin Yeo , Arun Anandasivam , Rajkumar Buyya Abstract : The use of High Performance Computing (HPC) in commercial and consumer IT applications is becoming popular. They need the ability to gain rapid and scalable access to high-end computing capabilities. Cloud computing promises to deliver such a computing infrastructure using data centers so that HPC users can access applications and data from a Cloud anywhere in the world on demand and pay based o… ▽ More The use of High Performance Computing (HPC) in commercial and consumer IT applications is becoming popular. They need the ability to gain rapid and scalable access to high-end computing capabilities. Cloud computing promises to deliver such a computing infrastructure using data centers so that HPC users can access applications and data from a Cloud anywhere in the world on demand and pay based on what they use. However, the growing demand drastically increases the energy consumption of data centers, which has become a critical issue. High energy consumption not only translates to high energy cost, which will reduce the profit margin of Cloud providers, but also high carbon emissions which is not environmentally sustainable. Hence, energy-efficient solutions are required that can address the high increase in the energy consumption from the perspective of not only Cloud provider but also from the environment. To address this issue we propose near-optimal scheduling policies that exploits heterogeneity across multiple data centers for a Cloud provider. We consider a number of energy efficiency factors such as energy cost, carbon emission rate, workload, and CPU power efficiency which changes across different data center depending on their location, architectural design, and management system. Our carbon/energy based scheduling policies are able to achieve on average up to 30% of energy savings in comparison to profit based scheduling policies leading to higher profit and less carbon emissions. △ Less Submitted 7 September, 2009; originally announced September 2009. arXiv:0808.3689 ?[ pdf , ps , other ]? cs.IT doi 10.1109/TWC.2009.071448 Optimal Power Allocation for Fading Channels in Cognitive Radio Networks: Ergodic Capacity and Outage Capacity Authors: Xin Kang , Ying-Chang Liang , Arumugam Nallanathan , Hari Krishna Garg , Rui Zhang Abstract : A cognitive radio network (CRN) is formed by either allowing the secondary users (SUs) in a secondary communication network (SCN) to opportunistically operate in the frequency bands originally allocated to a primary communication network (PCN) or by allowing SCN to coexist with the primary users (PUs) in PCN as long as the interference caused by SCN to each PU is properly regulated. In this pape… ▽ More A cognitive radio network (CRN) is formed by either allowing the secondary users (SUs) in a secondary communication network (SCN) to opportunistically operate in the frequency bands originally allocated to a primary communication network (PCN) or by allowing SCN to coexist with the primary users (PUs) in PCN as long as the interference caused by SCN to each PU is properly regulated. In this paper, we consider the latter case, known as spectrum sharing, and study the optimal power allocation strategies to achieve the ergodic capacity and the outage capacity of the SU fading channel under different types of power constraints and fading channel models. In particular, besides the interference power constraint at PU, the transmit power constraint of SU is also considered. Since the transmit power and the interference power can be limited either by a peak or an average constraint, various combinations of power constraints are studied. It is shown that there is a capacity gain for SU under the average over the peak transmit/interference power constraint. It is also shown that fading for the channel between SU transmitter and PU receiver is usually a beneficial factor for enhancing the SU channel capacities. △ Less Submitted 28 August, 2008; v1 submitted 27 August, 2008; originally announced August 2008. Comments: 26 pages, 9 figures, to appear in IEEE Transactions on Wireless Communications arXiv:cs/0610107 ?[ pdf , ps , other ]? cs.IT Interference Channels with Common Information Authors: Jinhua Jiang , Yan Xin , Hari Krishna Garg Abstract : In this paper, we consider the discrete memoryless interference channel with common information, in which two senders need deliver not only private messages but also certain common messages to their corresponding receivers. We derive an achievable rate region for such a channel by exploiting a random coding strategy, namely cascaded superposition coding. We reveal that the derived achievable rat… ▽ More In this paper, we consider the discrete memoryless interference channel with common information, in which two senders need deliver not only private messages but also certain common messages to their corresponding receivers. We derive an achievable rate region for such a channel by exploiting a random coding strategy, namely cascaded superposition coding. We reveal that the derived achievable rate region generalizes some important existing results for the interference channels with or without common information. Furthermore, we specialize to a class of deterministic interference channels with common information, and show that the derived achievable rate region is indeed the capacity region for this class of channels. △ Less Submitted 18 October, 2006; originally announced October 2006. Comments: 23 pages, 5 figures, submitted to Trans. Inform. Theory arXiv:cs/0303010 ?[ pdf , ps , other ]? cs.DC cs.SE Techniques and Applications of Computation Slicing Authors: Neeraj Mittal , Vijay K. Garg Abstract : Writing correct distributed programs is hard. In spite of extensive testing and debugging, software faults persist even in commercial grade software. Many distributed systems, especially those employed in safety-critical environments, should be able to operate properly even in the presence of software faults. Monitoring the execution of a distributed system, and, on detecting a fault, initiating… ▽ More Writing correct distributed programs is hard. In spite of extensive testing and debugging, software faults persist even in commercial grade software. Many distributed systems, especially those employed in safety-critical environments, should be able to operate properly even in the presence of software faults. Monitoring the execution of a distributed system, and, on detecting a fault, initiating the appropriate corrective action is an important way to tolerate such faults. This gives rise to the predicate detection problem which requires finding a consistent cut of a given computation that satisfies a given global predicate, if it exists. Detecting a predicate in a computation is, however, an NP-complete problem. To ameliorate the associated combinatorial explosion problem, we introduce the notion of computation slice. Formally, the slice of a computation with respect to a predicate is a (sub)computation with the least number of consistent cuts that contains all consistent cuts of the computation satisfying the predicate. To detect a predicate, rather than searching the state-space of the computation, it is much more efficient to search the state-space of the slice. We prove that the slice exists and is uniquely defined for all predicates. We present efficient slicing algorithms for several useful classes of predicates. We develop efficient heuristic algorithms for computing an approximate slice for predicates for which computing the slice is otherwise provably intractable. Our experimental results show that slicing can lead to an exponential improvement over existing techniques for predicate detection in terms of time and space. △ Less Submitted 15 March, 2003; originally announced March 2003. Comments: 50 pages, 14 figures ACM Class: C.2.4; D.4.5; D.2.2 .
From:
监测目标主题     
(1)  
(1)  
(1)  
系统抽取主题     
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)  
(1)