Dept. of Computer Science
http://hdl.handle.net/2142/10755
Connected Domatic Packings in Node-capacitated Graphs
http://hdl.handle.net/2142/48915
Connected Domatic Packings in Node-capacitated Graphs
Ene, Alina
Korula, Nitish J.
Vakilian, Ali
A set of vertices in a graph is a dominating set if every vertex
outside the set has a neighbor in the set. A dominating set is
connected if the subgraph induced by its vertices is connected.
The connected domatic partition problem asks for a partition of
the nodes into connected dominating sets. The connected domatic
number of a graph is the size of a largest connected domatic
partition and it is a well-studied graph parameter with
applications in the design of wireless networks.
%
In this note, we consider the fractional counterpart of the
connected domatic partition problem in \emph{node-capacitated}
graphs. Let $n$ be the number of nodes in the graph and let $k$
be the minimum capacity of a node separator in $G$. Fractionally
we can pack at most $k$ connected dominating sets subject to the
capacities on the nodes, and our algorithms construct packings
whose sizes are proportional to $k$. Some of our main
contributions are the following:
%
\begin{itemize}
\item An algorithm for constructing a fractional connected
domatic packing of size $\Omega\left(k \right)$ for
node-capacitated planar and minor-closed families of graphs.
%
\item An algorithm for constructing a fractional connected
domatic packing of size $\Omega\left(k / \ln{n} \right)$ for
node-capacitated general graphs.
%
\end{itemize}
connected dominating set, approximation algorithms, graph algorithms
Mon, 01 Jul 2013 00:00:00 GMTSocial (Media) Graces: Making Sense of Norms in Ritual Posts
http://hdl.handle.net/2142/48701
Social (Media) Graces: Making Sense of Norms in Ritual Posts
Kim, Jennifer
Karahalios, Karrie G.
Twidale, Michael
Facebook birthday greetings, Norms, Social media
Thu, 27 Mar 2014 00:00:00 GMTocial (Media) Graces: Making Sense of Norms in Ritual Posts
http://hdl.handle.net/2142/48700
ocial (Media) Graces: Making Sense of Norms in Ritual Posts
Kim, Jennifer
Karahalios, Karrie
Twidale, Michael
Facebook birthday greetings, Norms, Social media
Thu, 27 Mar 2014 00:00:00 GMTHow do Developers Use Parallel Libraries?
http://hdl.handle.net/2142/47627
How do Developers Use Parallel Libraries?
Okur, Semih
Dig, Danny
Parallel programming is hard. The industry leaders hope to convert the hard problem of using parallelism into the easier problem of using a parallel library. Yet, we know little about how programmers adopt these libraries in practice. Without such knowledge, other programmers cannot educate themselves about the state of the practice, library designers are unaware of API misusage, researchers make wrong assumptions, and tool vendors do not support common usage of library constructs.
We present the first study that analyzes the usage of parallel libraries in a large scale experiment. We analyzed 655 open-source applications that adopted Microsoft's new parallel libraries -- Task Parallel Library (TPL) and Parallel Language Integrated Query (PLINQ) -- comprising 17.6M lines of code written in C#. These applications are developed by 1609 programmers. Using this data, we answer 8 research question and we uncover some interesting facts. For example, (i) for two of the fundamental parallel constructs, in at least 10% of the cases developers misuse them so that the code runs sequentially instead of concurrently, (ii) developers make their parallel code unnecessarily complex, (iii) applications of different size have different adoption trends. The library designers confirmed that our finding are useful and will influence the future development of the libraries.
parallel programming
concurrent programming
concurrent libraries
empirical study
Thu, 01 Nov 2012 00:00:00 GMTAutomated Decomposition of Build Targets
http://hdl.handle.net/2142/47551
Automated Decomposition of Build Targets
Vakilian, Mohsen
Sauciuc, Raluca
Morgenthaler, J. David
Mirrokni, Vahab
A (build) target specifies the information that is needed to automatically build a software artifact. Managing the dependencies between the targets of a large code base is challenging. This paper focuses on underutilized targets—an important dependency problem that we identified at Google. An underutilized target is one with files not needed by some of its dependents. Underutilized targets result in less modular code, overly large artifacts, slow builds, and unnecessary build and test triggers. To mitigate these problems, programmers decompose underutilized targets into smaller targets. However, manually decomposing a target is tedious and error-prone. Although we prove that finding the best target decomposition is NP-hard, we introduce a greedy algorithm that proposes a decomposition through iterative unification of the strongly connected components of the target. Our tool found 19,994 decomposable targets in a set of 40,000 Java library targets at Google. A decomposable target is one that can be decomposed to at least two targets. Our tool found that decomposing any of the 5,129 decomposable targets would save at least one build or test trigger. The evaluation results show that our tool is (1) efficient because on average, it analyzes a target in two minutes and (2) effective because for each of 1,010 targets, it would save more than 50% of the total execution time of the tests triggered by the target.
refactoring
continuous integration
build system
regression testing
remodularization
Sat, 01 Mar 2014 00:00:00 GMTThe CodingSpectator Data Set of Eclipse Refactoring Messages
http://hdl.handle.net/2142/47414
The CodingSpectator Data Set of Eclipse Refactoring Messages
Vakilian, Mohsen
Johnson, Ralph E.
This data set contains the results of a quantitative analysis on the refactoring messages that CodingSpectator captured during our field study. CodingSpectator collects data about the usage of the Eclipse Integrated Development Environment. A refactoring message is an error message that the Eclipse refactoring tool reports to programmers. The results include the distributions of the messages and the programmers' reactions to the messages.
refactoring
data set
eclipse
integrated development environment
Fri, 28 Feb 2014 00:00:00 GMTVariants of Variants and the Finite Variant Property
http://hdl.handle.net/2142/47117
Variants of Variants and the Finite Variant Property
Cholewa, Andrew
Meseguer, Jose
Escobar, Santiago
Variants and the finite variant property were originally introduced about a decade ago by Hurbert Comon-Lundh and Stephanie Delaune to reason about equational theories that commonly appear in cryptographic protocol
analysis. Since that time, two additional notions of variants have been developed: one by Santiago Escobar, Jose Meseguer, and Ralf Sasse, and one by
Stefan Ciobaca. Though it seems intuitively clear that all three notions capture the same essential idea, their relationships to each other have never been rigorously analyzed. Therefore, we decided to do just that. In the process, we encountered an unexpected subtlety with respect to the finite variant property, the term signature of a theory, and the boundedness property. We also provide
a simple semi-decision procedure for checking if an equational theory has the finite variant property, by analzying terms of the form f (x 1 : s 1 , . . . , x n : s n )
for all function symbols f : s 1 , . . . , s n → s in the signature, where x 1 , . . . , x n are distinct variables.
variants
finite variant property
rewriting
equational rewriting
equational theories
Tue, 11 Feb 2014 00:00:00 GMTUsing Humans as Sensors: An Estimation-theoretic Perspective
http://hdl.handle.net/2142/47115
Using Humans as Sensors: An Estimation-theoretic Perspective
Wang, Dong
Amin, Md Tanvir Al
Li, Shen
Abdelzaher, Tarek
Kaplan, Lance
Gu, Siyu
Pan, Chenji
Liu, Hengchang
Aggarwal, Charu
Ganti, Raghu K.
Wang, Xinlei
Mohapatra, Prasant
Szymanski,Boleslaw
Le, Hieu
The explosive growth in social network content suggests that the largest "sensor network" yet might be human. Extending the participatory sensing model, this paper explores the prospect of utilizing social networks as sensor networks, which gives rise to an interesting reliable sensing problem. In this problem, individuals are represented by sensors (data sources) who occasionally make observations about the physical world. These observations may be true or false, and hence are viewed as binary claims. The reliable sensing problem is to determine the correctness of reported observations. From a networked sensing standpoint, what makes this sensing problem formulation different is that, in the case of human participants, not only is the reliability of sources usually unknown but also the original data provenance may be uncertain. Individuals may report observations made by others as their own. The contribution of this paper lies in developing a model that considers the impact of such information sharing on the analytical foundations of reliable sensing, and embed it into a tool called Apollo that uses Twitter as a "sensor network" for observing events in the physical world. Evaluation, using Twitter-based case-studies, shows good correspondence between observations deemed correct by Apollo and ground truth.
humans as sensors, social sensing, data reliability, uncertain data provenance, maximum likelihood estimation, expectation maximization
Wed, 01 Jan 2014 00:00:00 GMTThe PTRANS Specification Language
http://hdl.handle.net/2142/47101
The PTRANS Specification Language
Mansky, William
The VeriF-OPT project seeks to provide a framework for stating and reasoning about compiler optimizations and transformations on parallel programs in the presence of relaxed memory models. The core of the framework is a domain-specific language for specifying compiler optimizations: PTRANS,
in which program transformations are expressed as rewrites on control flow graphs with temporal logic side conditions. This document describes the syntax of PTRANS and its two semantics: the abstract semantics used to verify specifications, and the executable semantics used to prototype specifications.
compiler optimization
parallel programming
program transformations
temporal logic
Sat, 01 Feb 2014 00:00:00 GMTMatching Logic: A Logic for Structural Reasoning
http://hdl.handle.net/2142/47004
Matching Logic: A Logic for Structural Reasoning
Rosu, Grigore
Matching logic is a first-order logic (FOL) variant
to reason about structure. Its sentences, called patterns, are
constructed using variables, symbols, connectives and quantifiers,
but no dif ference is made between function and predicate symbols.
In models, a pattern evaluates into a power-set domain (the set
of values that match it), in contrast to FOL where functions,
predicates and connectives map into a domain. Matching logic
generalizes several logical frameworks important for program
analysis, such as: propositional logic, algebraic specification,
FOL with equality, and separation logic. Patterns allow for
specifying separation requirements at any level in any program
configuration, not only in the heaps or stores, without any special
logical constructs for that: the very nature of pattern matching
is that if two structures are matched as part of a pattern, then
they can only be spatially separated. Like FOL, matching logic
can also be translated into pure predicate logic with equality, but
it also admits its own sound and complete proof system.
first-order logic, separation logic, matching logic
Mon, 20 Jan 2014 00:00:00 GMT