Cheap talk,cooperation, and trust in global software engineering

In our studies of global software engineering (GSE) teams, we found that informal, non-work-related conversations are positively associated with trust. Seeking to use novel analytical techniques to more carefully investigate this phenomenon, we described these non-work-related conversations by adapting the economics literature concept of “cheap talk,” and studied it using Evolutionary Game Theory (EGT). More specifically, we modified the classic Stag-hunt game and analyzed the dynamics in a fixed population setting (an abstraction of a GSE team). Doing so, we were able to demonstrate how cheap talk over the Internet (e-cheap talk) was powerful enough to facilitate the emergence of trust and improve the probability of cooperation where the punishment for uncooperative behavior is comparable to the cost of the cheap talk. To validate the results of our theoretical approach, we conducted two empirical case studies that analyzed the logged IRC development discussions of Apache Lucene (http://lucene.apache. org/) and Chromium OS (http://www.chromium.org/chromium-os) using both quantitative and qualitative methods. The results provide general support to the theoretical propositions. We discuss our findings and the theoretical and practical implications to GSE collaborations and research.     

Multi-ML: Programming Multi-BSP Algorithms in ML

bsp is a bridging model between abstract execution and concrete parallel systems. Structure and abstraction brought by bsp allow to have portable parallel programs with scalable performance predictions, without dealing with low-level details of architectures. In the past, we designed bsml for programming bsp algorithms in ml. However, the simplicity of the bsp model does not fit the complexity of today’s hierarchical architectures such as clusters of machines with multiple multi-core processors. The multi-bsp model is an extension of the bsp model which brings a tree-based view of nested components of hierarchical architectures. To program multi-bsp algorithms in ml, we propose the multi-ml language as an extension of bsml where a specific kind of recursion is used to go through a hierarchy of computing nodes. We define a formal semantics of the language and present preliminary experiments which show performance improvements with respect to bsml.     

Interprocedural Array Region Analyses

Many program optimizations require exact knowledge of the sets of array elements that are referenced in or that flow between statements or procedures. Some examples are array privatization, generation of communications in distributed memory machines, or compile-time optimization of cache behavior in hierarchical memory machines. Exact array region analysis is introduced in this article. These regions exactly represent the effects of statements and procedures upon array variables. To represent the flow of these data, we also introduce two new types of array region analyses: in and out regions. The intraprocedural propagation is presented, as well as a general linear framework for interprocedural analyses, which handles array reshapes. The intra- and inter-procedural propagation of array regions is implemented in pips, the interprocedural parallelizer of fortran programs developed at École des mines de Paris.     

Ecosystem on the Web: non-linear mining and forecasting of co-evolving online activities

Given a large collection of co-evolving online activities, such as searches for the keywords “Xbox”, “PlayStation” and “Wii”, how can we find patterns and rules? Are these keywords related? If so, are they competing against each other? Can we forecast the volume of user activity for the coming month? We conjecture that online activities compete for user attention in the same way that species in an ecosystem compete for food. We present EcoWeb, (i.e., Ecosystem on the Web), which is an intuitive model designed as a non-linear dynamical system for mining large-scale co-evolving online activities. Our second contribution is a novel, parameter-free, and scalable fitting algorithm, EcoWeb-Fit, that estimates the parameters of EcoWeb. Extensive experiments on real data show that EcoWeb is effective, in that it can capture long-range dynamics and meaningful patterns such as seasonalities, and practical, in that it can provide accurate long-range forecasts. EcoWeb consistently outperforms existing methods in terms of both accuracy and execution speed.     

Improved Approximation Algorithms for Label Cover Problems

In this paper we consider both the maximization variant Max Rep and the minimization variant Min Rep of the famous Label Cover problem. So far the best approximation ratios known for these two problems were \(O(\sqrt{n})\) and indeed some authors suggested the possibility that this ratio is the best approximation factor for these two problems. We show, in fact, that there are a O(n ^1/3)-approximation algorithm for Max Rep and a O(n ^1/3log?^2/3 n)-approximation algorithm for Min Rep. In addition, we also exhibit a randomized reduction from Densest k-Subgraph to Max Rep, showing that any approximation factor for Max Rep implies the same factor (up to a constant) for Densest k-Subgraph.     

BSP-Why: A Tool for Deductive Verification of BSP Algorithms with Subgroup Synchronisation

We present bsp-why, a tool for deductive verification of bsp  algorithms with subgroup synchronisation. From bsp  programs, bsp-why generates sequential codes for the back-end condition generator why and thus benefits from its large range of existing provers. By enabling subgroups, the user can prove the correctness of programs that run on hierarchical machines—e.g. clusters of multi-cores. In general, bsp-why is able to generate proof obligations of mpi programs that only use collective operations. Our case studies are distributed state-space construction algorithms, the basis of model-checking.     

Approximating the Sparsest k-Subgraph in Chordal Graphs

Given a simple undirected graph G = (V, E) and an integer k < |V|, the Sparsest k-Subgraph problem asks for a set of k vertices which induces the minimum number of edges. As a generalization of the classical independent set problem, Sparsest k-Subgraph is ????-hard and even not approximable unless ?????? in general graphs. Thus, we investigate Sparsest k-Subgraph in graph classes where independent set is polynomial-time solvable, such as subclasses of perfect graphs. Our two main results are the ????-hardness of Sparsest k-Subgraph on chordal graphs, and a greedy 2-approximation algorithm. Finally, we also show how to derive a P T A S for Sparsest k-Subgraph on proper interval graphs.     

A Unified User Management System

ABSTRACT

As open source software has gained in popularity throughout the last decades, free operating systems (OSs) such as Linux (Torvalds) and BSD derivatives (i.e., FreeBSD, 2012; NetBSD, 2012 NetBSD Foundation. (2012). The NetBSD project. Available from http://netbsd.org (http://netbsd.org)  [Google Scholar]; OpenBSD, 2012 OpenBSD. (2012). OpenBSD. OpenBSD. Available from http://netbsd.org (http://netbsd.org)  [Google Scholar]) have become more common, not only on datacenters but also on desktop and laptop computers. It is not rare to find computer labs or company offices composed of personal computers that boot more than one operating system. By being able to choose among available OSs, a company's or organization's information technology manager has the freedom to select the right OS for the company's needs, and the decision can be based on technical or financial criteria. This freedom of choice, however, comes with a cost. The administrative complexity of heterogeneous networks is much higher compared to single OS networks, and if the network is large enough so that protocols such as LDAP (Zeilenga, 2006 Zeilenga, K. 2006. Lightweight directory access protocol (LDAP): Technical specification road map et. alTech. rep., RFC 4510, June [Google Scholar]) or Kerberos (Kohl & Neuman, 1993 Kohl, J. and Neuman, C. 1993. The Kerberos network authentication service (v5) Tech. rep., RFC 1510, September[Crossref] , [Google Scholar]) need to be adopted, then the administration burden may become unbearable. Even though some tools exist that make user management of heterogeneous networks more feasible (Tournier, 2006 Tournier, J. (2006). smbldap-tools – summary [Gna!]. In Welcome to Gna! http://gna.org/projects/smbldap-tools (http://gna.org/projects/smbldap-tools)  [Google Scholar]; Chu & Symas Corp., 2005 Chu, H. and Symas Corp. (2005) http://www.openldap.org/devel/cvsweb.cgi/~checkout~/contrib/slapd-modules/smbk5pwd/README (http://www.openldap.org/devel/cvsweb.cgi/~checkout~/contrib/slapd-modules/smbk5pwd/README)  [Google Scholar]), it is not uncommon to use more than one back end for storing user credentials due to OS incompatibilities. In such configurations, the hardest problem to address is credential and account expiration synchronization among the different back ends. This paper demonstrates a platform that tries to mitigate the problem of synchronization by adding an additional, modular, easy to expand layer which is responsible for synchronizing any number of underlying back ends in a secure fashion.     

Verification as a parameterized testing (experiments with the SCP4 supercompiler)

Let a program-predicate t testing another program p with respect to a given postcondition be given. Concrete tests d (data of the program p) are input data for t. Let us consider the program t when values of its argument d are unknown. Then a proof of the fact that the prediate t is true for all input data of the program p is verification of p with respect to the given postcondition. In this paper, we describe experiments on automatic verification of a number of cache coherence protocols with the SCP4 supercompiler (an optimizer of programs written in the REFAL-5 functional language).     

On quasi-interpretations of grammar forms

The notions of a grammar form and its interpretations were introduced to describe families of structurally related grammars. Basically, a grammar formG is a (context-free) grammar serving as a master grammar and the interpretation operator defines a family of grammars, each structurally related toG. In this paper, a new operator yielding a family of grammars, is introduced as a variant of . There are two major results. The first is that and commute. The second is that for each grammar formG, the collection of all families of grammars ,G′ in , is finite. Expressed otherwise, the second result is that for each grammar formG there is only a bounded number of grammar forms in (G) no two of which are strongly equivalent.     

On Participation Constrained Team Formation

The task assignment on the Internet has been widely applied to many areas, e.g., online labor market, online paper review and social activity organization. In this paper, we are concerned with the task assignment problem related to the online labor market, termed as ClusterHire. We improve the definition of the ClusterHire problem, and propose an efficient and effective algorithm, entitled Influence. In addition, we place a participation constraint on ClusterHire. It constrains the load of each expert in order to keep all members from overworking. For the participation-constrained ClusterHire problem, we devise two algorithms, named ProjectFirst and Era. The former generates a participationconstrained team by adding experts to an initial team, and the latter generates a participation-constrained team by removing the experts with the minimum influence from the universe of experts. The experimental evaluations indicate that 1) Influence performs better than the state-of-the-art algorithms in terms of effectiveness and time efficiency; 2) ProjectFirst performs better than Era in terms of time efficiency, yet Era performs better than ProjectFirst in terms of effectiveness.     

An extended AVHRR 8‐km NDVI dataset compatible with MODIS and SPOT vegetation NDVI data

Daily daytime Advanced Very High Resolution Radiometer (AVHRR) 4‐km global area coverage data have been processed to produce a Normalized Difference Vegetation Index (NDVI) 8‐km equal‐area dataset from July 1981 through December 2004 for all continents except Antarctica. New features of this dataset include bimonthly composites, NOAA‐9 descending node data from August 1994 to January 1995, volcanic stratospheric aerosol correction for 1982–1984 and 1991–1993, NDVI normalization using empirical mode decomposition/reconstruction to minimize varying solar zenith angle effects introduced by orbital drift, inclusion of data from NOAA‐16 for 2000–2003 and NOAA‐17 for 2003–2004, and a similar dynamic range with the MODIS NDVI. Two NDVI compositing intervals have been produced: a bimonthly global dataset and a 10‐day Africa‐only dataset. Post‐processing review corrected the majority of dropped scan lines, navigation errors, data drop outs, edge‐of‐orbit composite discontinuities, and other artefacts in the composite NDVI data. All data are available from the University of Maryland Global Land Cover Facility (http://glcf.umiacs.umd.edu/data/gimms/).     

Toward the complexity of the existence of wonderfully stable partitions and strictly core stable coalition structures in enemy-oriented hedonic games

We study the computational complexity of the existence and the verification problem for wonderfully stable partitions (WSPE and WSPV) and of the existence problem for strictly core stable coalition structures (SCSCS) in enemy-oriented hedonic games. In this note, we show that WSPV is NP-complete and both WSPE and SCSCS are DP-hard, where DP is the second level of the boolean hierarchy, and we discuss an approach for classifying the latter two problems in terms of their complexity.     

Degree-Constrained Graph Orientation: Maximum Satisfaction and Minimum Violation

A degree-constrained graph orientation of an undirected graph G is an assignment of a direction to each edge in G such that the outdegree of every vertex in the resulting directed graph satisfies a specified lower and/or upper bound. Such graph orientations have been studied for a long time and various characterizations of their existence are known. In this paper, we consider four related optimization problems introduced in reference (Asahiro et al. LNCS 7422, 332–343 (2012)): For any fixed non-negative integer W, the problems MAX W-LIGHT, MIN W-LIGHT, MAX W-HEAVY, and MIN W-HEAVY take as input an undirected graph G and ask for an orientation of G that maximizes or minimizes the number of vertices with outdegree at most W or at least W. As shown in Asahiro et al. LNCS 7422, 332–343 (2012)).     

Advanced load application on deformable ring gears in planetary gearboxes

This paper discusses the implementation of deformable ring gears in Multi-Body-Simulation-Models (MBS-Models) of planetary gearboxes using the example of a Wind Turbine (WT). For this purpose an add-on to the MBS-Software Simpack was developed and tested by the project partners Bosch Rexroth and the Institute for Machine Elements and Machine Design at Rwth-Aachen University (Ime).The presented research includes a measurement campaign on a test rig owned by Bosch Rexroth to obtain data for a validation of the newly developed add-on.     

Efficient filtering for the Resource-Cost AllDifferent constraint

This paper studies a family of optimization problems where a set of items, each requiring a possibly different amount of resource, must be assigned to different slots for which the price of the resource can vary. The objective is then to assign items such that the overall resource cost is minimized. Such problems arise commonly in domains such as production scheduling in the presence of fluctuating renewable energy costs or variants of the Travelling Salesman Problem. In Constraint Programming, this can be naturally modeled in two ways: (a) with a sum of element constraints; (b) with a MinimumAssignment constraint. Unfortunately the sum of element constraints obtains a weak filtering and the MinimumAssignment constraint does not scale well on large instances. This work proposes a third approach by introducing the ResourceCostAllDifferent constraint and an associated incremental and scalable filtering algorithm, running in \(\mathcal {O}(n \cdot m)\), where n is the number of unbound variables and m is the maximum domain size of unbound variables. Its goal is to compute the total cost in a scalable manner by dealing with the fact that all assignments must be different. We first evaluate the efficiency of the new filtering on a real industrial problem and then on the Product Matrix Travelling Salesman Problem, a special case of the Asymmetric Travelling Salesman Problem. The study shows experimentally that our approach generally outperforms the decomposition and the MinimumAssignment ones for the problems we considered.     

Prompter

Developers often require knowledge beyond the one they possess, which boils down to asking co-workers for help or consulting additional sources of information, such as Application Programming Interfaces (API) documentation, forums, and Q&A websites. However, it requires time and energy to formulate one’s problem, peruse and process the results. We propose a novel approach that, given a context in the Integrated Development Environment (IDE), automatically retrieves pertinent discussions from Stack Overflow, evaluates their relevance using a multi-faceted ranking model, and, if a given confidence threshold is surpassed, notifies the developer. We have implemented our approach in Prompter, an Eclipse plug-in. Prompter was evaluated in two empirical studies. The first study was aimed at evaluatingPrompter’s ranking model and involved 33 participants. The second study was conducted with 12 participants and aimed at evaluating Prompter’s usefulness when supporting developers during development and maintenance tasks. Since Prompter uses “volatile information” crawled from the web, we also replicated Study I after one year to assess the impact of such a “volatility” on recommenders like Prompter. Our results indicate that (i) Prompter recommendations were positively evaluated in 74 % of the cases on average, (ii) Prompter significantly helps developers to improve the correctness of their tasks by 24 % on average, but also (iii) 78 % of the provided recommendations are “volatile” and can change at one year of distance. While Prompter revealed to be effective, our studies also point out issues when building recommenders based on information available on online forums.     

Patterns and anomalies in <Emphasis Type="Italic">k</Emphasis>-cores of real-world graphs with applications

How do the k-core structures of real-world graphs look like? What are the common patterns and the anomalies? How can we exploit them for applications? A k-core is the maximal subgraph in which all vertices have degree at least k. This concept has been applied to such diverse areas as hierarchical structure analysis, graph visualization, and graph clustering. Here, we explore pervasive patterns related to k-cores and emerging in graphs from diverse domains. Our discoveries are: (1) Mirror Pattern: coreness (i.e., maximum k such that each vertex belongs to the k-core) is strongly correlated with degree. (2) Core-Triangle Pattern: degeneracy (i.e., maximum k such that the k-core exists) obeys a 3-to-1 power-law with respect to the count of triangles. (3) Structured Core Pattern: degeneracy–cores are not cliques but have non-trivial structures such as core–periphery and communities. Our algorithmic contributions show the usefulness of these patterns. (1) Core-A, which measures the deviation from Mirror Pattern, successfully spots anomalies in real-world graphs, (2) Core-D, a single-pass streaming algorithm based on Core-Triangle Pattern, accurately estimates degeneracy up to 12 \(\times \) faster than its competitor. (3) Core-S, inspired by Structured Core Pattern, identifies influential spreaders up to 17 \(\times \) faster than its competitors with comparable accuracy.