arXiv:2007.04816  [pdf, other]  cs.SE 
doi
10.1145/3382494.3410685
Effect of Technical and Social Factors on Pull Request Quality for the NPM Ecosystem

Authors: Tapajit Dey, Audris Mockus

Abstract: Pull request (PR) based development, which is a norm for the social coding platforms, entails the challenge of evaluating the contributions of, often unfamiliar, developers from across the open source ecosystem and, conversely, submitting a contribution to a project with unfamiliar maintainers. Previous studies suggest that the decision of accepting or rejecting a PR may be influenced by a diverging set of technical and social factors, but often focus on relatively few projects, do not consider ecosystem-wide measures, or the possible non-monotonic relationships between the predictors and PR acceptance probability. We aim to shed light on this important decision making process by testing which measures significantly affect the probability of PR acceptance on a significant fraction of a large ecosystem, rank them by their relative importance in predicting PR acceptance, and determine the shape of the functions that map each predictor to PR acceptance. We proposed seven hypotheses regarding which technical and social factors might affect PR acceptance and created 17 measures based on them. Our dataset consisted of 470,925 PRs from 3349 popular NPM packages and 79,128 GitHub users who created those. We tested which of the measures affect PR acceptance and ranked the significant measures by their importance in a predictive model. Our predictive model had and AUC of 0.94, and 15 of the 17 measures were found to matter, including five novel ecosystem-wide measures. Measures describing the number of PRs submitted to a repository and what fraction of those get accepted, and signals about the PR review phase were most significant. We also discovered that only four predictors have a linear influence on the PR acceptance probability while others showed a more complicated response. △ Less

Submitted 20 July, 2020; v1 submitted 8 July, 2020; originally announced July 2020.

Comments: arXiv admin note: text overlap with arXiv:2003.01153. Preprint of the paper accepted in ESEM,2020 conference

ACM Class: D.2.7

arXiv:2006.13129  [pdf, other]  cs.SE
A Catalogue of Game-Specific Anti-Patterns

Authors: Vartika Agrahari, Sridhar Chimalakonda

Abstract: With the ever-increasing use of games, game developers are expected to write efficient code supporting several qualities such as security, maintainability, and performance. However, lack of time and continuous need to update the features of games may result in bad practices that may affect the functional and non-functional requirements of the game. These bad practices are often termed as Anti-patterns, which can cause technical debt, poor program comprehension, and can lead to several issues during software maintenance. While there exists empirical research on games, we are not aware of any work on understanding and cataloguing anti-patterns in games. Thus, we propose a catalogue of game-specific anti-patterns by mining commits, pull requests, and issues from 229 popular GitHub game repositories. We use regular expressions to create an initial dataset of open-source games and did thematic analysis on text records for cataloguing game-specific anti-patterns. We applied LDA (Latent Dirichlet Allocation) to validate further and refine the categories. We present a catalogue of 11 anti-patterns with a total of 20 subcategories involved in it and provide examples for them. We believe this catalogue would help game developers in making educated decisions during game development that can result in enhanced quality of games. △ Less

Submitted 23 June, 2020; originally announced June 2020.

arXiv:2005.10176  [pdf, ps, other]  cs.SE cs.LG
Representation of Developer Expertise in Open Source Software

Authors: Tapajit Dey, Andrey Karnauch, Audris Mockus

Abstract: With tens of millions of projects and developers, the OSS ecosystem is both vibrant and intimidating. On one hand, it hosts the source code for the most critical infrastructures and has the most brilliant developers as contributors, while on the other hand, poor quality or even malicious software, and novice developers abound. External contributions are critical to OSS projects, but the chances their contributions are accepted or even considered depend on the trust between maintainers and contributors. Such trust is built over repeated interactions and coding platforms provide signals of project or developer quality via measures of activity (commits), and social relationships (followers/stars) to facilitate trust. These signals, however, do not represent the specific expertise of a developer. We, therefore, aim to address this gap by defining the skill space for APIs, developers, and projects that reflects what developers know (and projects need) more precisely than could be obtained via aggregate activity counts, and more generally than pointing to individual files developers have changed in the past. Specifically, we use the World of Code infrastructure to extract the complete set of APIs in the files changed by all open source developers. We use that data to represent APIs, developers, and projects in the skill space, and evaluate if the alignment measures in the skill space can predict whether or not the developers use new APIs, join new projects, or get their pull requests accepted. We also check if the developers' representation in the skill space aligns with their self-reported expertise. Our results suggest that the proposed embedding in the skill space achieves our aims and may serve not only as a signal to increase trust (and efficiency) of open source ecosystems, but may also allow more detailed investigations of other phenomena related to developer proficiency and learning. △ Less

Submitted 20 May, 2020; originally announced May 2020.

arXiv:2004.10657  [pdf, other]  cs.PL cs.LG stat.ML 
doi
10.1145/3385412.3385997
Typilus: Neural Type Hints

Authors: Miltiadis Allamanis, Earl T. Barr, Soline Ducousso, Zheng Gao

Abstract: Type inference over partial contexts in dynamically typed languages is challenging. In this work, we present a graph neural network model that predicts types by probabilistically reasoning over a program's structure, names, and patterns. The network uses deep similarity learning to learn a TypeSpace -- a continuous relaxation of the discrete space of types -- and how to embed the type properties of a symbol (i.e. identifier) into it. Importantly, our model can employ one-shot learning to predict an open vocabulary of types, including rare and user-defined ones. We realise our approach in Typilus for Python that combines the TypeSpace with an optional type checker. We show that Typilus accurately predicts types. Typilus confidently predicts types for 70% of all annotatable symbols; when it predicts a type, that type optionally type checks 95% of the time. Typilus can also find incorrect type annotations; two important and popular open source libraries, fairseq and allennlp, accepted our pull requests that fixed the annotation errors Typilus discovered. △ Less

Submitted 6 April, 2020; originally announced April 2020.

Comments: Accepted to PLDI 2020

arXiv:2004.08846  [pdf, other]  cs.SE
BuGL -- A Cross-Language Dataset for Bug Localization

Authors: Sandeep Muvva, A Eashaan Rao, Sridhar Chimalakonda

Abstract: Bug Localization is the process of locating potential error-prone files or methods from a given bug report and source code. There is extensive research on bug localization in the literature that focuses on applying information retrieval techniques or machine learning/deep learning approaches or both, to detect location of bugs. The common premise for all approaches is the availability of a good dataset, which in this case, is the standard benchmark dataset that comprises of 6 Java projects and in some cases, more than 6 Java projects. The existing dataset do not comprise projects of other programming languages, despite of the need to investigate specific and cross project bug localization. To the best of our knowledge, we are not aware of any dataset that addresses this concern. In this paper, we present BuGL, a large-scale cross-language dataset. BuGL constitutes of more than 10,000 bug reports drawn from open-source projects written in four programming languages, namely C, C++, Java, and Python. The dataset consists of information which includes Bug Reports and Pull-Requests. BuGL aims to unfold new research opportunities in the area of bug localization. △ Less

Submitted 19 April, 2020; originally announced April 2020.

Comments: 5 Pages, 3 Figures, 2 Tables

arXiv:2003.11772  [pdf, other]  cs.SE 
doi
10.1145/3379597.3387460
Empirical Study of Restarted and Flaky Builds on Travis CI

Authors: Thomas Durieux, Claire Le Goues, Michael Hilton, Rui Abreu

Abstract: Continuous Integration (CI) is a development practice where developers frequently integrate code into a common codebase. After the code is integrated, the CI server runs a test suite and other tools to produce a set of reports (e.g., output of linters and tests). If the result of a CI test run is unexpected, developers have the option to manually restart the build, re-running the same test suite on the same code; this can reveal build flakiness, if the restarted build outcome differs from the original build. In this study, we analyze restarted builds, flaky builds, and their impact on the development workflow. We observe that developers restart at least 1.72% of builds, amounting to 56,522 restarted builds in our Travis CI dataset. We observe that more mature and more complex projects are more likely to include restarted builds. The restarted builds are mostly builds that are initially failing due to a test, network problem, or a Travis CI limitations such as execution timeout. Finally, we observe that restarted builds have a major impact on development workflow. Indeed, in 54.42% of the restarted builds, the developers analyze and restart a build within an hour of the initial failure. This suggests that developers wait for CI results, interrupting their workflow to address the issue. Restarted builds also slow down the merging of pull requests by a factor of three, bringing median merging time from 16h to 48h. △ Less

Submitted 26 March, 2020; originally announced March 2020.

Journal ref: 17th International Conference on Mining Software Repositories (MSR '20), October 5--6, 2020, Seoul, Republic of Korea

arXiv:2003.01153  [pdf, other]  cs.SE
Which Pull Requests Get Accepted and Why? A study of popular NPM Packages

Authors: Tapajit Dey, Audris Mockus

Abstract: Background: Pull Request (PR) Integrators often face challenges in terms of multiple concurrent PRs, so the ability to gauge which of the PRs will get accepted can help them balance their workload. PR creators would benefit from knowing if certain characteristics of their PRs may increase the chances of acceptance. Aim: We modeled the probability that a PR will be accepted within a month after creation using a Random Forest model utilizing 50 predictors representing properties of the author, PR, and the project to which PR is submitted. Method: 483,988 PRs from 4218 popular NPM packages were analysed and we selected a subset of 14 predictors sufficient for a tuned Random Forest model to reach high accuracy. Result: An AUC-ROC value of 0.95 was achieved predicting PR acceptance. The model excluding PR properties that change after submission gave an AUC-ROC value of 0.89. We tested the utility of our model in practical scenarios by training it with historical data for the NPM package \textit{bootstrap} and predicting if the PRs submitted in future will be accepted. This gave us an AUC-ROC value of 0.94 with all 14 predictors, and 0.77 excluding PR properties that change after its creation. Conclusion: PR integrators can use our model for a highly accurate assessment of the quality of the open PRs and PR creators may benefit from the model by understanding which characteristics of their PRs may be undesirable from the integrators' perspective. The model can be implemented as a tool, which we plan to do as a future work. △ Less

Submitted 2 March, 2020; originally announced March 2020.

arXiv:2002.02056  [pdf]  cs.SE
Design of the Inspection Process Using the GitHub Flow in Project Based Learning for Software Engineering and Its Practice

Authors: Yutsuki Miyashita, Yuki Yamada, Hiroaki Hashiura, Atsuo Hazeyama

Abstract: Project based learning (PBL) for software development (we call it software development PBL) has garnered attention as a practical educational method. A number of studies have reported on the introduction of social coding tools such as GitHub, in software development PBL. In education, it is important to give feedback (advice, error corrections, and so on) to learners, especially in software development PBL because almost all learners tackle practical software development from the viewpoint of technical and managerial aspects for the first time. This study regards inspection that is conducted in general software development activities as an opportunity to provide feedback and proposes the inspection process using the pull request on GitHub. By applying the proposed process to an actual software development PBL, we enable giving feedback to the accurate locations of artifacts the learners created. △ Less

Submitted 5 February, 2020; originally announced February 2020.

arXiv:2001.09630  [pdf, other]  cs.SE 
doi
10.1007/s10664-020-09807-w
Ammonia: An Approach for Deriving Project-specific Bug Patterns

Authors: Yoshiki Higo, Shinpei Hayashi, Hideaki Hata, Meiyappan Nagappan

Abstract: Finding and fixing buggy code is an important and cost-intensive maintenance task, and static analysis (SA) is one of the methods developers use to perform it. SA tools warn developers about potential bugs by scanning their source code for commonly occurring bug patterns, thus giving those developers opportunities to fix the warnings (potential bugs) before they release the software. Typically, SA tools scan for general bug patterns that are common to any software project (such as null pointer dereference), and not for project specific patterns. However, past research has pointed to this lack of customizability as a severe limiting issue in SA. Accordingly, in this paper, we propose an approach called Ammonia, which is based on statically analyzing changes across the development history of a project, as a means to identify project-specific bug patterns. Furthermore, the bug patterns identified by our tool do not relate to just one developer or one specific commit, they reflect the project as a whole and compliment the warnings from other SA tools that identify general bug patterns. Herein, we report on the application of our implemented tool and approach to four Java projects: Ant, Camel, POI, and Wicket. The results obtained show that our tool could detect 19 project specific bug patterns across those four projects. Next, through manual analysis, we determined that six of those change patterns were actual bugs and submitted pull requests based on those bug patterns. As a result, five of the pull requests were merged. △ Less

Submitted 14 March, 2020; v1 submitted 27 January, 2020; originally announced January 2020.

Comments: 28 pages, Empirical Software Engineering

arXiv:2001.07808  [pdf, other]  cs.SE
A Comprehensive Study of Bloated Dependencies in the Maven Ecosystem

Authors: César Soto-Valero, Nicolas Harrand, Martin Monperrus, Benoit Baudry

Abstract: Build automation tools and package managers have a profound influence on software development. They facilitate the reuse of third-party libraries, support a clear separation between the application's code and its external dependencies, and automate several software development tasks. However, the wide adoption of these tools introduces new challenges related to dependency management. In this paper, we propose an original study of one such challenge: the emergence of bloated dependencies. Bloated dependencies are libraries that the build tool packages with the application's compiled code but that are actually not necessary to build and run the application. This phenomenon artificially grows the size of the built binary and increases maintenance effort. We propose a tool, called DepClean, to analyze the presence of bloated dependencies in Maven artifacts. We analyze 9,639 Java artifacts hosted on Maven Central, which include a total of 723,444 dependency relationships. Our key result is that 75.1% of the analyzed dependency relationships are bloated. In other words, it is feasible to reduce the number of dependencies of Maven artifacts up to 1/4 of its current count. We also perform a qualitative study with 30 notable open-source projects. Our results indicate that developers pay attention to their dependencies and are willing to remove bloated dependencies: 18/21 answered pull requests were accepted and merged by developers, removing 131 dependencies in total. △ Less

Submitted 21 January, 2020; originally announced January 2020.

Comments: Manuscript submitted to Empirical Software Engineering (EMSE)

arXiv:1912.09652  [pdf, other]  cs.SE cs.LG
CORE: Automating Review Recommendation for Code Changes

Authors: JingKai Siow, Cuiyun Gao, Lingling Fan, Sen Chen, Yang Liu

Abstract: Code review is a common process that is used by developers, in which a reviewer provides useful comments or points out defects in the submitted source code changes via pull request. Code review has been widely used for both industry and open-source projects due to its capacity in early defect identification, project maintenance, and code improvement. With rapid updates on project developments, code review becomes a non-trivial and labor-intensive task for reviewers. Thus, an automated code review engine can be beneficial and useful for project development in practice. Although there exist prior studies on automating the code review process by adopting static analysis tools or deep learning techniques, they often require external sources such as partial or full source code for accurate review suggestion. In this paper, we aim at automating the code review process only based on code changes and the corresponding reviews but with better performance. The hinge of accurate code review suggestion is to learn good representations for both code changes and reviews. To achieve this with limited source, we design a multi-level embedding (i.e., word embedding and character embedding) approach to represent the semantics provided by code changes and reviews. The embeddings are then well trained through a proposed attentional deep learning model, as a whole named CORE. We evaluate the effectiveness of CORE on code changes and reviews collected from 19 popular Java projects hosted on Github. Experimental results show that our model CORE can achieve significantly better performance than the state-of-the-art model (DeepMem), with an increase of 131.03% in terms of Recall@10 and 150.69% in terms of Mean Reciprocal Rank. Qualitative general word analysis among project developers also demonstrates the performance of CORE in automating code review. △ Less

Submitted 20 December, 2019; originally announced December 2019.

Comments: Accepted by 27th IEEE International Conference on Software Analysis, Evolution and Reengineering (SANER)

arXiv:1912.08722  [pdf, other]  cs.NI cs.LG
Waiting but not Aging: Optimizing Information Freshness Under the Pull Model

Authors: Fengjiao Li, Yu Sang, Zhongdong Liu, Bin Li, Huasen Wu, Bo Ji

Abstract: The Age-of-Information (AoI) has recently been proposed as an important metric for investigating the timeliness performance in information-update systems. In this paper, we study the AoI minimization problem under a new Pull model with replication schemes, where a user proactively sends a replicated request to multiple servers to "pull" the information of interest. Interestingly, we find that under this new Pull model, replication schemes capture a novel tradeoff between different values of the AoI across the servers (due to the random updating processes) and different response times across the servers, which can be exploited to minimize the expected AoI at the user's side. Specifically, assuming Poisson updating process for the servers and exponentially distributed response time, we derive a closed-form formula for computing the expected AoI and obtain the optimal number of responses to wait for to minimize the expected AoI. Then, we extend our analysis to the setting where the user aims to maximize the AoI-based utility, which represents the user's satisfaction level with respect to freshness of the received information. Furthermore, we consider a more realistic scenario where the user has no prior knowledge of the system. In this case, we reformulate the utility maximization problem as a stochastic Multi-Armed Bandit problem with side observations and leverage a special linear structure of side observations to design learning algorithms with improved performance guarantees. Finally, we conduct extensive simulations to elucidate our theoretical results and compare the performance of different algorithms. Our findings reveal that under the Pull model, waiting does not necessarily lead to aging; waiting wisely can significantly reduce the AoI and improve the AoI-based utility in most scenarios. △ Less

Submitted 20 July, 2020; v1 submitted 17 December, 2019; originally announced December 2019.

Comments: 14 pages. arXiv admin note: substantial text overlap with arXiv:1704.04848

arXiv:1911.03051  [pdf, other]  cs.DC cs.NI
Quality of Service (QoS) Modelling in Federated Cloud Computing

Authors: Kun Ma, Antoine Bagula, Olasupo Ajayi

Abstract: Building around the idea of a large scale server infrastructure with a potentially large number of tailored resources, which are capable of interacting to facilitate the deployment, adaptation, and support of services, cloud computing needs to frequently reschedule and manage various application tasks in order to accommodate the requests of a wide range and number of users. One of the challenges of cloud computing is to support and manage Quality-of-Service (QoS) by designing efficient techniques for the allocation of tasks between users and the cloud virtual resources, as well as assigning virtual resources to the cloud physical resources. The migration of virtual resources across physical resources is another challenge that requires considerable attention; especially in federated cloud computing environments wherein, providers might be willing to offer their unused resources as a service to the federation (cooperative allocation) and pull back these resources for their own use when they are needed (competitive allocation). This paper revisits the issue of QoS in cloud computing by formulating and presenting i) a multi-QoS task allocation model for the assignment of tasks to virtual machines and ii) a virtual machine migration model for a federated cloud computing environment by considering cases where resource providers are operating in cooperative or competitive mode. A new differential evolution (DE) based binding policy for task allocation and a novel virtual machine model are proposed as solutions for the problem of QoS support in federated cloud environments. The experimental results show that the proposed solutions improved the quality of service in the cloud computing environment and reveal the relative advantages of operating a mixed cooperation and competition model in a federated cloud environment. △ Less

Submitted 8 November, 2019; originally announced November 2019.

Comments: 21 pages, 9 figures, 9 tables

arXiv:1910.00188  [pdf, other]  cs.SE 
doi
10.1145/3350768.3350788
Beyond Textual Issues: Understanding the Usage and Impact of GitHub Reactions

Authors: Hudson Borges, Rodrigo Brito, Marco Tulio Valente

Abstract: Recently, GitHub introduced a new social feature, named reactions, which are "pictorial characters" similar to emoji symbols widely used nowadays in text-based communications. Particularly, GitHub users can use a pre-defined set of such symbols to react to issues and pull requests. However, little is known about the real usage and impact of GitHub reactions. In this paper, we analyze the reactions provided by developers to more than 2.5 million issues and 9.7 million issue comments, in order to answer an extensive list of nine research questions about the usage and adoption of reactions. We show that reactions are being increasingly used by open source developers. Moreover, we also found that issues with reactions usually take more time to be handled and have longer discussions. △ Less

Submitted 30 September, 2019; originally announced October 2019.

Comments: 10 pages

Journal ref: SBES 2019, Proceedings of the XXXIII Brazilian Symposium on Software Engineering, Pages 397-406

arXiv:1909.06987  [pdf, other]  cs.SE
Automatic Generation of Pull Request Descriptions

Authors: Zhongxin Liu, Xin Xia, Christoph Treude, David Lo, Shanping Li

Abstract: Enabled by the pull-based development model, developers can easily contribute to a project through pull requests (PRs). When creating a PR, developers can add a free-form description to describe what changes are made in this PR and/or why. Such a description is helpful for reviewers and other developers to gain a quick understanding of the PR without touching the details and may reduce the possibility of the PR being ignored or rejected. However, developers sometimes neglect to write descriptions for PRs. For example, in our collected dataset with over 333K PRs, more than 34% of the PR descriptions are empty. To alleviate this problem, we propose an approach to automatically generate PR descriptions based on the commit messages and the added source code comments in the PRs. We regard this problem as a text summarization problem and solve it using a novel sequence-to-sequence model. To cope with out-of-vocabulary words in software artifacts and bridge the gap between the training loss function of the sequence-to-sequence model and the evaluation metric ROUGE, which has been shown to correspond to human evaluation, we integrate the pointer generator and directly optimize for ROUGE using reinforcement learning and a special loss function. We build a dataset with over 41K PRs and evaluate our approach on this dataset through ROUGE and a human evaluation. Our evaluation results show that our approach outperforms two baselines by significant margins. △ Less

Submitted 16 September, 2019; originally announced September 2019.

Comments: to appear as full paper at the 34th IEEE/ACM International Conference on Automated Software Engineering (ASE2019)

arXiv:1908.09321  [pdf, other]  cs.SE
Does Code Quality Affect Pull Request Acceptance? An empirical study

Authors: Valentina Lenarduzzi, Vili Nikkola, Nyyti Saarimäki, Davide Taibi

Abstract: Background. Pull requests are a common practice for contributing and reviewing contributions, and are employed both in open-source and industrial contexts. One of the main goals of code reviews is to find defects in the code, allowing project maintainers to easily integrate external contributions into a project and discuss the code contributions. Objective. The goal of this paper is to understand whether code quality is actually considered when pull requests are accepted. Specifically, we aim at understanding whether code quality issues such as code smells, antipatterns, and coding style violations in the pull request code affect the chance of its acceptance when reviewed by a maintainer of the project. Method. We conducted a case study among 28 Java open-source projects, analyzing the presence of 4.7 M code quality issues in 36 K pull requests. We analyzed further correlations by applying Logistic Regression and seven machine learning techniques (Decision Tree, Random Forest, Extremely Randomized Trees, AdaBoost, Gradient Boosting, XGBoost). Results. Unexpectedly, code quality turned out not to affect the acceptance of a pull request at all. As suggested by other works, other factors such as the reputation of the maintainer and the importance of the feature delivered might be more important than code quality in terms of pull request acceptance. Conclusions. Researchers already investigated the influence of the developers' reputation and the pull request acceptance. This is the first work investigating if quality of the code in pull requests affects the acceptance of the pull request or not. We recommend that researchers further investigate this topic to understand if different measures or different tools could provide some useful measures. △ Less

Submitted 25 August, 2019; originally announced August 2019.

arXiv:1908.02320  [pdf, other]  cs.SE
Do as I Do, Not as I Say: Do Contribution Guidelines Match the GitHub Contribution Process?

Authors: Omar Elazhary, Margaret-Anne Storey, Neil Ernst, Andy Zaidman

Abstract: Developer contribution guidelines are used in social coding sites like GitHub to explain and shape the process a project expects contributors to follow. They set standards for all participants and "save time and hassle caused by improperly created pull requests or issues that have to be rejected and resubmitted" (GitHub). Yet, we lack a systematic understanding of the content of a typical contribution guideline, as well as the extent to which these guidelines are followed in practice. Additionally, understanding how guidelines may impact projects that use Continuous Integration as part of the contribution process is of particular interest. To address this knowledge gap, we conducted a mixed-methods study of 53 GitHub projects with explicit contribution guidelines and coded the guidelines to extract key themes. We then created a process model using GitHub activity data (e.g., commit, new issue, new pull request) to compare the actual activity with the prescribed contribution guidelines. We show that approximately 68% of these projects diverge significantly from the expected process. △ Less

Submitted 6 August, 2019; originally announced August 2019.

Comments: Submitted to ICSME'19. 5 pages. 1 figure

arXiv:1907.06538  [pdf, other]  cs.SE cs.CY
Patterns of Effort Contribution and Demand and User Classification based on Participation Patterns in NPM Ecosystem

Authors: Tapajit Dey, Yuxing Ma, Audris Mockus

Abstract: Background: Open source requires participation of volunteer and commercial developers (users) in order to deliver functional high-quality components. Developers both contribute effort in the form of patches and demand effort from the component maintainers to resolve issues reported against it. Aim: Identify and characterize patterns of effort contribution and demand throughout the open source supply chain and investigate if and how these patterns vary with developer activity; identify different groups of developers; and predict developers' company affiliation based on their participation patterns. Method: 1,376,946 issues and pull-requests created for 4433 NPM packages with over 10,000 monthly downloads and full (public) commit activity data of the 272,142 issue creators is obtained and analyzed and dependencies on NPM packages are identified. Fuzzy c-means clustering algorithm is used to find the groups among the users based on their effort contribution and demand patterns, and Random Forest is used as the predictive modeling technique to identify their company affiliations. Result: Users contribute and demand effort primarily from packages that they depend on directly with only a tiny fraction of contributions and demand going to transitive dependencies. A significant portion of demand goes into packages outside the users' respective supply chains (constructed based on publicly visible version control data). Three and two different groups of users are observed based on the effort demand and effort contribution patterns respectively. The Random Forest model used for identifying the company affiliation of the users gives a AUC-ROC value of 0.68. Conclusion: Our results give new insights into effort demand and supply at different parts of the supply chain of the NPM ecosystem and its users and suggests the need to increase visibility further upstream. △ Less

Submitted 15 July, 2019; originally announced July 2019.

Comments: 10 pages, 5 Tables, 2 Figures, Accepted in The 15th International Conference on Predictive Models and Data Analytics in Software Engineering 2019

arXiv:1906.11017  [pdf, ps, other]  cs.SE 
doi
10.1007/978-3-030-22750-0_32
A project-based course on software development for (engineering) research

Authors: Kyle E. Niemeyer

Abstract: This paper describes the motivation and design of a 10-week graduate course that teaches practices for developing research software; although offered by an engineering program, the content applies broadly to any field of scientific research where software may be developed. Topics taught in the course include local and remote version control, licensing and copyright, structuring Python modules, testing and test coverage, continuous integration, packaging and distribution, open science, software citation, and reproducibility basics, among others. Lectures are supplemented by in-class activities and discussions, and all course material is shared openly via GitHub. Coursework is heavily based on a single, term-long project where students individually develop a software package targeted at their own research topic; all contributions must be submitted as pull requests and reviewed/merged by other students. The course was initially offered in Spring 2018 with 17 students enrolled, and will be taught again in Spring 2019. △ Less

Submitted 13 June, 2019; originally announced June 2019.

Comments: 7 pages, accepted at ICCS 2019

Journal ref: Lecture Notes in Computer Science (LNCS) 11540:401-407, Proceedings of the International Conference on Computational Science (ICCS 2019)

arXiv:1905.07113  [pdf, other]  cs.DB
High Throughput Push Based Storage Manager

Authors: Ye Zhu

Abstract: The storage manager, as a key component of the database system, is responsible for organizing, reading, and delivering data to the execution engine for processing. According to the data serving mechanism, existing storage managers are either pull-based, incurring high latency, or push-based, leading to a high number of I/O requests when the CPU is busy. To improve these shortcomings, this thesis proposes a push-based prefetching strategy in a column-wise storage manager. The proposed strategy implements an efficient cache layer to store shared data among queries to reduce the number of I/O requests. The capacity of the cache is maintained by a time access-aware eviction mechanism. Our strategy enables the storage manager to coordinate multiple queries by merging their requests and dynamically generate an optimal read order that maximizes the overall I/O throughput. We evaluated our storage manager both over a disk-based redundant array of independent disks (RAID) and an NVM Express (NVMe) solid-state drive (SSD). With the high read performance of the SSD, we successfully minimized the total read time and number of I/O accesses. △ Less

Submitted 17 May, 2019; originally announced May 2019.

arXiv:1905.04482  [pdf, other]  cs.SE
GE852: A Dataset of 852 Game Engines

Authors: Chaitanya S. Lakkundi, Vartika Agrahari, Sridhar Chimalakonda

Abstract: Game engines provide a platform for developers to build games with an interface tailored to handle the complexity during game development. To reduce effort and improve quality of game development, there is a strong need to understand and analyze the quality of game engines and their various aspects such as API usability, code quality, code reuse and so on. To the best our knowledge, we are not aware of any dataset that caters to game engines in the literature. To this end, we present GE852, a dataset of 852 game engine repositories mined from GitHub in two languages, namely Java and C++. The dataset contains metadata of all the mined repositories including commits, pull requests, issues and so on. We believe that our dataset can lay foundation for empirical investigation in the area of game engines. △ Less

Submitted 11 May, 2019; originally announced May 2019.

Comments: 5 pages, 2 figures, 1 table

arXiv:1905.03593  [pdf, other]  cs.SE
A Topological Analysis of Communication Channels for Knowledge Sharing in Contemporary GitHub Projects

Authors: Jirateep Tantisuwankul, Yusuf Sulistyo Nugroho, Raula Gaikovina Kula, Hideaki Hata, Arnon Rungsawang, Pattara Leelaprute, Kenichi Matsumoto

Abstract: With over 28 million developers, success of the GitHub collaborative platform is highlighted through an abundance of communication channels among contemporary software projects. Knowledge is broken into two forms and its sharing (through communication channels) can be described as externalization or combination by the SECI model. Such platforms have revolutionized the way developers work, introducing new channels to share knowledge in the form of pull requests, issues and wikis. It is unclear how these channels capture and share knowledge. In this research, our goal is to analyze these communication channels in GitHub. First, using the SECI model, we are able to map how knowledge is shared through the communication channels. Then in a large-scale topology analysis of seven library package projects (i.e., involving over 70 thousand projects), we extracted insights of the different communication channels within GitHub. Using two research questions, we explored the evolution of the channels and adoption of channels by both popular and unpopular library package projects. Results show that (i) contemporary GitHub Projects tend to adopt multiple communication channels, (ii) communication channels change over time and (iii) communication channels are used to both capture new knowledge (i.e., externalization) and updating existing knowledge (i.e., combination). △ Less

Submitted 8 September, 2019; v1 submitted 9 May, 2019; originally announced May 2019.

Comments: 30 pages

arXiv:1902.04060  [pdf, other]  cs.SE
Replication Can Improve Prior Results: A GitHub Study of Pull Request Acceptance

Authors: Di Chen, Kathyrn Stolee, Tim Menzies

Abstract: Crowdsourcing and data mining can be used to effectively reduce the effort associated with the partial replication and enhancement of qualitative studies. For example, in a primary study, other researchers explored factors influencing the fate of GitHub pull requests using an extensive qualitative analysis of 20 pull requests. Guided by their findings, we mapped some of their qualitative insights onto quantitative questions. To determine how well their findings generalize, we collected much more data (170 additional pull requests from 142 GitHub projects). Using crowdsourcing, that data was augmented with subjective qualitative human opinions about how pull requests extended the original issue. The crowd's answers were then combined with quantitative features and, using data mining, used to build a predictor for whether code would be merged. That predictor was far more accurate that one built from the primary study's qualitative factors (F1=90 vs 68\%), illustrating the value of a mixed-methods approach and replication to improve prior results. To test the generality of this approach, the next step in future work is to conduct other studies that extend qualitative studies with crowdsourcing and data mining. △ Less

Submitted 8 February, 2019; originally announced February 2019.

Comments: 12 pages, submitted to ICPC 2019. arXiv admin note: substantial text overlap with arXiv:1702.08571

arXiv:1901.09102  [pdf, other]  cs.SE cs.CL cs.LG
On Learning Meaningful Code Changes via Neural Machine Translation

Authors: Michele Tufano, Jevgenija Pantiuchina, Cody Watson, Gabriele Bavota, Denys Poshyvanyk

Abstract: Recent years have seen the rise of Deep Learning (DL) techniques applied to source code. Researchers have exploited DL to automate several development and maintenance tasks, such as writing commit messages, generating comments and detecting vulnerabilities among others. One of the long lasting dreams of applying DL to source code is the possibility to automate non-trivial coding activities. While some steps in this direction have been taken (e.g., learning how to fix bugs), there is still a glaring lack of empirical evidence on the types of code changes that can be learned and automatically applied by DL. Our goal is to make this first important step by quantitatively and qualitatively investigating the ability of a Neural Machine Translation (NMT) model to learn how to automatically apply code changes implemented by developers during pull requests. We train and experiment with the NMT model on a set of 236k pairs of code components before and after the implementation of the changes provided in the pull requests. We show that, when applied in a narrow enough context (i.e., small/medium-sized pairs of methods before/after the pull request changes), NMT can automatically replicate the changes implemented by developers during pull requests in up to 36% of the cases. Moreover, our qualitative analysis shows that the model is capable of learning and replicating a wide variety of meaningful code changes, especially refactorings and bug-fixing activities. Our results pave the way for novel research in the area of DL on code, such as the automatic learning and applications of refactoring. △ Less

Submitted 25 January, 2019; originally announced January 2019.

Comments: Accepted to the 41st ACM/IEEE International Conference on Software Engineering (ICSE 2019) - Montreal, QC, Canada, May 25-31, 2019, 12 pages

arXiv:1901.07440  [pdf, other]  cs.SE
9.6 Million Links in Source Code Comments: Purpose, Evolution, and Decay

Authors: Hideaki Hata, Christoph Treude, Raula Gaikovina Kula, Takashi Ishio

Abstract: Links are an essential feature of the World Wide Web, and source code repositories are no exception. However, despite their many undisputed benefits, links can suffer from decay, insufficient versioning, and lack of bidirectional traceability. In this paper, we investigate the role of links contained in source code comments from these perspectives. We conducted a large-scale study of around 9.6 million links to establish their prevalence, and we used a mixed-methods approach to identify the links' targets, purposes, decay, and evolutionary aspects. We found that links are prevalent in source code repositories, that licenses, software homepages, and specifications are common types of link targets, and that links are often included to provide metadata or attribution. Links are rarely updated, but many link targets evolve. Almost 10% of the links included in source code comments are dead. We then submitted a batch of link-fixing pull requests to open source software repositories, resulting in most of our fixes being merged successfully. Our findings indicate that links in source code comments can indeed be fragile, and our work opens up avenues for future work to address these problems. △ Less

Submitted 15 February, 2019; v1 submitted 22 January, 2019; originally announced January 2019.

Comments: 12 pages, ICSE 2019

arXiv:1901.06024  [pdf, other]  cs.SE 
doi
10.1109/SANER.2019.8667991
Bears: An Extensible Java Bug Benchmark for Automatic Program Repair Studies

Authors: Fernanda Madeiral, Simon Urli, Marcelo Maia, Martin Monperrus

Abstract: Benchmarks of bugs are essential to empirically evaluate automatic program repair tools. In this paper, we present Bears, a project for collecting and storing bugs into an extensible bug benchmark for automatic repair studies in Java. The collection of bugs relies on commit building state from Continuous Integration (CI) to find potential pairs of buggy and patched program versions from open-source projects hosted on GitHub. Each pair of program versions passes through a pipeline where an attempt of reproducing a bug and its patch is performed. The core step of the reproduction pipeline is the execution of the test suite of the program on both program versions. If a test failure is found in the buggy program version candidate and no test failure is found in its patched program version candidate, a bug and its patch were successfully reproduced. The uniqueness of Bears is the usage of CI (builds) to identify buggy and patched program version candidates, which has been widely adopted in the last years in open-source projects. This approach allows us to collect bugs from a diversity of projects beyond mature projects that use bug tracking systems. Moreover, Bears was designed to be publicly available and to be easily extensible by the research community through automatic creation of branches with bugs in a given GitHub repository, which can be used for pull requests in the Bears repository. We present in this paper the approach employed by Bears, and we deliver the version 1.0 of Bears, which contains 251 reproducible bugs collected from 72 projects that use the Travis CI and Maven build environment. △ Less

Submitted 17 January, 2019; originally announced January 2019.

Comments: Proceedings of the 26th IEEE International Conference on Software Analysis, Evolution and Reengineering (SANER '19)

Journal ref: Proceedings of the 26th IEEE International Conference on Software Analysis, Evolution and Reengineering, 2019

arXiv:1901.03302  [pdf, other]  cs.SE
Catalog of Energy Patterns for Mobile Applications

Authors: Luis Cruz, Rui Abreu

Abstract: Software engineers make use of design patterns for reasons that range from performance to code comprehensibility. Several design patterns capturing the body of knowledge of best practices have been proposed in the past, namely creational, structural and behavioral patterns. However, with the advent of mobile devices, it becomes a necessity a catalog of design patterns for energy efficiency. In this work, we inspect commits, issues and pull requests of 1027 Android and 756 iOS apps to identify common practices when improving energy efficiency. This analysis yielded a catalog, available online, with 22 design patterns related to improving the energy efficiency of mobile apps. We argue that this catalog might be of relevance to other domains such as Cyber-Physical Systems and Internet of Things. As a side contribution, an analysis of the differences between Android and iOS devices shows that the Android community is more energy-aware. △ Less

Submitted 10 January, 2019; originally announced January 2019.

Comments: Journal of Empirical Software Engineering

arXiv:1812.11903  [pdf, ps, other]  cs.SI cs.DC
Randomized Rumor Spreading in Ad Hoc Networks with Buffers

Authors: Dariusz R. Kowalski, Christopher Thraves Caro

Abstract: The randomized rumor spreading problem generates a big interest in the area of distributed algorithms due to its simplicity, robustness and wide range of applications. The two most popular communication paradigms used for spreading the rumor are Push and Pull algorithms. The former protocol allows nodes to send the rumor to a randomly selected neighbor at each step, while the latter is based on sending a request and downloading the rumor from a randomly selected neighbor, provided the neighbor has it. Previous analysis of these protocols assumed that every node could process all such push/pull operations within a single step, which could be unrealistic in practical situations. Therefore we propose a new framework for analysis rumor spreading accommodating buffers, in which a node can process only one push/pull message or push request at a time. We develop upper and lower bounds for randomized rumor spreading time in the new framework, and compare the results with analogous in the old framework without buffers. △ Less

Submitted 31 December, 2018; originally announced December 2018.

Comments: Manuscript submitted to DISC 2013

arXiv:1812.06269  [pdf, other]  cs.SE
On the impact of pull request decisions on future contributions

Authors: Damien Legay, Alexandre Decan, Tom Mens

Abstract: The pull-based development process has become prevalent on platforms such as GitHub as a form of distributed software development. Potential contributors can create and submit a set of changes to a software project through pull requests. These changes can be accepted, discussed or rejected by the maintainers of the software project, and can influence further contribution proposals. As such, it is important to examine the practices that encourage contributors to a project to submit pull requests. Specifically, we consider the impact of prior pull requests on the acceptance or rejection of subsequent pull requests. We also consider the potential effect of rejecting or ignoring pull requests on further contributions. In this preliminary research, we study three large projects on \textsf{GitHub}, using pull request data obtained through the \textsf{GitHub} API, and we perform empirical analyses to investigate the above questions. Our results show that continued contribution to a project is correlated with higher pull request acceptance rates and that pull request rejections lead to fewer future contributions. △ Less

Submitted 15 December, 2018; originally announced December 2018.

Comments: 6 pages. Presented at BENEVOL 2018 software evolution seminar, Delft, The Netherlands (11 December 2018). Published in open access CEUR Workshop Proceedings (ceur-ws.org). Researchsupported by the FRQ-FNRS collaborative research project R.60.04.18.F SECOHealth, the Excellence of Science project 30446992 SECO-ASSIST financed by FWO-Vlaanderen and F.R.S.-FNRS, and F.R.S.-FNRS Grant T.0017.18, CEUR Workshop Proceedings 2019

arXiv:1812.04863  [pdf, other]  cs.CY cs.SE
A First Look at Emoji Usage on GitHub: An Empirical Study

Authors: Xuan Lu, Yanbin Cao, Zhenpeng Chen, Xuanzhe Liu

Abstract: Emoji is becoming a ubiquitous language and gaining worldwide popularity in recent years including the field of software engineering (SE). As nonverbal cues, emojis are widely used in user understanding tasks such as sentiment analysis, but few work has been done to study emojis in SE scenarios. This paper presents a large scale empirical study on how GitHub users use emojis in development-related communications. We find that emojis are used by a considerable proportion of GitHub users. In comparison to Internet users, developers show interesting usage characteristics and have their own interpretation of the meanings of emojis. In addition, the usage of emojis reflects a positive and supportive culture of this community. Through a manual annotation task, we find that sentimental usage is a main intention of using emojis in issues, pull requests, and comments, while emojis are mainly used to emphasize important contents in README. These findings not only deepen our understanding about the culture of SE communities, but also provide implications on how to facilitate SE tasks with emojis such as sentiment analysis. △ Less

Submitted 12 December, 2018; originally announced December 2018.

arXiv:1811.08330  [pdf, other]  cs.SE 
doi
10.1007/s10664-019-09692-y
Automatic Test Improvement with DSpot: a Study with Ten Mature Open-Source Projects

Authors: Benjamin Danglot, Oscar Luis Vera-Pérez, Benoit Baudry, Martin Monperrus

Abstract: In the literature, there is a rather clear segregation between manually written tests by developers and automatically generated ones. In this paper, we explore a third solution: to automatically improve existing test cases written by developers. We present the concept, design, and implementation of a system called \dspot, that takes developer-written test cases as input (junit tests in Java) and synthesizes improved versions of them as output. Those test improvements are given back to developers as patches or pull requests, that can be directly integrated in the main branch of the test code base. We have evaluated DSpot in a deep, systematic manner over 40 real-world unit test classes from 10 notable and open-source software projects. We have amplified all test methods from those 40 unit test classes. In 26/40 cases, DSpot is able to automatically improve the test under study, by triggering new behaviors and adding new valuable assertions. Next, for ten projects under consideration, we have proposed a test improvement automatically synthesized by \dspot to the lead developers. In total, 13/19 proposed test improvements were accepted by the developers and merged into the main code base. This shows that DSpot is capable of automatically improving unit-tests in real-world, large-scale Java software. △ Less

Submitted 20 November, 2018; originally announced November 2018.

Journal ref: Empirical Software Engineering, Springer Verlag, 2019

arXiv:1809.10948  [pdf, other]  cs.NI
Pull-based Bloom Filter-based Routing for Information-Centric Networks

Authors: Ali Marandi, Torsten Braun, Kave Salamatian, Nikolaos Thomos

Abstract: In Named Data Networking (NDN), there is a need for routing protocols to populate Forwarding Information Base (FIB) tables so that the Interest messages can be forwarded. To populate FIBs, clients and routers require some routing information. One method to obtain this information is that network nodes exchange routing information by each node advertising the available content objects. Bloom Filter-based Routing approaches like BFR [1], use Bloom Filters (BFs) to advertise all provided content objects, which consumes valuable bandwidth and storage resources. This strategy is inefficient as clients request only a small number of the provided content objects and they do not need the content advertisement information for all provided content objects. In this paper, we propose a novel routing algorithm for NDN called pull-based BFR in which servers only advertise the demanded file names. We compare the performance of pull-based BFR with original BFR and with a flooding-assisted routing protocol. Our experimental evaluations show that pull-based BFR outperforms original BFR in terms of communication overhead needed for content advertisements, average roundtrip delay, memory resources needed for storing content advertisements at clients and routers, and the impact of false positive reports on routing. The comparisons also show that pull-based BFR outperforms flooding-assisted routing in terms of average round-trip delay. △ Less

Submitted 28 September, 2018; originally announced September 2018.

arXiv:1807.04130  [pdf, other]  cs.SE 
doi
10.1145/2970276.2970283
CORRECT: Code Reviewer Recommendation at GitHub for Vendasta Technologies

Authors: Mohammad Masudur Rahman, Chanchal K. Roy, Jesse Redl, Jason A. Collins

Abstract: Peer code review locates common coding standard violations and simple logical errors in the early phases of software development, and thus, reduces overall cost. Unfortunately, at GitHub, identifying an appropriate code reviewer for a pull request is challenging given that reliable information for reviewer identification is often not readily available. In this paper, we propose a code reviewer recommendation tool--CORRECT--that considers not only the relevant cross-project work experience (e.g., external library experience) of a developer but also her experience in certain specialized technologies (e.g., Google App Engine) associated with a pull request for determining her expertise as a potential code reviewer. We design our tool using client-server architecture, and then package the solution as a Google Chrome plug-in. Once the developer initiates a new pull request at GitHub, our tool automatically analyzes the request, mines two relevant histories, and then returns a ranked list of appropriate code reviewers for the request within the browser's context. Demo: https://www.youtube.com/watch?v=rXU1wTD6QQ0 △ Less

Submitted 9 July, 2018; originally announced July 2018.

Comments: The 31st IEEE/ACM International Conference on Automated Software Engineering (ASE 2016), pp. 792--797, Singapore, September 2016. arXiv admin note: substantial text overlap with arXiv:1807.02965

Journal ref: Proc. ASE 2016, pp. 792--797

arXiv:1807.02965  [pdf, other]  cs.SE 
doi
10.1145/2889160.2889244
CORRECT: Code Reviewer Recommendation in GitHub Based on Cross-Project and Technology Experience

Authors: Mohammad Masudur Rahman, Chanchal K. Roy, Jason A. Collins

Abstract: Peer code review locates common coding rule violations and simple logical errors in the early phases of software development, and thus reduces overall cost. However, in GitHub, identifying an appropriate code reviewer for a pull request is a non-trivial task given that reliable information for reviewer identification is often not readily available. In this paper, we propose a code reviewer recommendation technique that considers not only the relevant cross-project work history (e.g., external library experience) but also the experience of a developer in certain specialized technologies associated with a pull request for determining her expertise as a potential code reviewer. We first motivate our technique using an exploratory study with 10 commercial projects and 10 associated libraries external to those projects. Experiments using 17,115 pull requests from 10 commercial projects and six open source projects show that our technique provides 85%--92% recommendation accuracy, about 86% precision and 79%--81% recall in code reviewer recommendation, which are highly promising. Comparison with the state-of-the-art technique also validates the empirical findings and the superiority of our recommendation technique. △ Less

Submitted 9 July, 2018; originally announced July 2018.

Comments: The 38th International Conference on Software Engineering (Companion volume) (ICSE 2016), pp. 222--231, Austin Texas, USA, May 2016

Journal ref: Proc. ICSE-C 2016, pp. 222--231

arXiv:1807.02037  [pdf, other]  cs.LG cs.AI stat.ML
TFLMS: Large Model Support in TensorFlow by Graph Rewriting

Authors: Tung D. Le, Haruki Imai, Yasushi Negishi, Kiyokuni Kawachiya

Abstract: While accelerators such as GPUs have limited memory, deep neural networks are becoming larger and will not fit with the memory limitation of accelerators for training. We propose an approach to tackle this problem by rewriting the computational graph of a neural network, in which swap-out and swap-in operations are inserted to temporarily store intermediate results on CPU memory. In particular, we first revise the concept of a computational graph by defining a concrete semantics for variables in a graph. We then formally show how to derive swap-out and swap-in operations from an existing graph and present rules to optimize the graph. To realize our approach, we developed a module in TensorFlow, named TFLMS. TFLMS is published as a pull request in the TensorFlow repository for contributing to the TensorFlow community. With TFLMS, we were able to train ResNet-50 and 3DUnet with 4.7x and 2x larger batch size, respectively. In particular, we were able to train 3DUNet using images of size of 1923 for image segmentation, which, without TFLMS, had been done only by dividing the images to smaller images, which affects the accuracy. △ Less

Submitted 2 October, 2019; v1 submitted 5 July, 2018; originally announced July 2018.

Comments: A new version of TFLMS was published at ISMM 2019 (https://dl.acm.org/citation.cfm?id=3329984)

arXiv:1807.01853  [pdf, other]  cs.SE 
doi
10.1145/2597073.2597121
An Insight into the Pull Requests of GitHub

Authors: Mohammad Masudur Rahman, Chanchal K. Roy

Abstract: Given the increasing number of unsuccessful pull requests in GitHub projects, insights into the success and failure of these requests are essential for the developers. In this paper, we provide a comparative study between successful and unsuccessful pull requests made to 78 GitHub base projects by 20,142 developers from 103,192 forked projects. In the study, we analyze pull request discussion texts, project specific information (e.g., domain, maturity), and developer specific information (e.g., experience) in order to report useful insights, and use them to contrast between successful and unsuccessful pull requests. We believe our study will help developers overcome the issues with pull requests in GitHub, and project administrators with informed decision making. △ Less

Submitted 5 July, 2018; originally announced July 2018.

Comments: 11th Working Conference on Mining Software Repositories (MSR 2014), pp. 364--367, Hyderabad, India, May 2014

arXiv:1807.01851  [pdf, other]  cs.SE 
doi
10.1109/MSR.2017.39
Impact of Continuous Integration on Code Reviews

Authors: Mohammad Masudur Rahman, Chanchal K. Roy

Abstract: Peer code review and continuous integration often interleave with each other in the modern software quality management. Although several studies investigate how non-technical factors (e.g., reviewer workload), developer participation and even patch size affect the code review process, the impact of continuous integration on code reviews is not yet properly understood. In this paper, we report an exploratory study using 578K automated build entries where we investigate the impact of automated builds on the code reviews. Our investigation suggests that successfully passed builds are more likely to encourage new code review participation in a pull request. Frequently built projects are found to be maintaining a steady level of reviewing activities over the years, which was quite missing from the rarely built projects. Experiments with 26,516 automated build entries reported that our proposed model can identify 64% of the builds that triggered new code reviews later. △ Less

Submitted 5 July, 2018; originally announced July 2018.

Comments: International Conference on Mining Software Repositories (MSR 2017), pp. 499--502, Buenos Aires, Argentina, May, 2017

Journal ref: International Conference on Mining Software Repositories (MSR 2017), pp. 499--502, Buenos Aires, Argentina, May, 2017

arXiv:1806.08457  [pdf, other]  cs.SE
Whom Are You Going to Call?: Determinants of @-Mentions in GitHub Discussions

Authors: David Kavaler, Premkumar Devanbu, Vladimir Filkov

Abstract: Open Source Software (OSS) project success relies on crowd contributions. When an issue arises in pull-request based systems, @-mentions are used to call on people to task; previous studies have shown that @-mentions in discussions are associated with faster issue resolution. In most projects there may be many developers who could technically handle a variety of tasks. But OSS supports dynamic teams distributed across a wide variety of social and geographic backgrounds, as well as levels of involvement. It is, then, important to know whom to call on, i.e., who can be relied or trusted with important task-related duties, and why. In this paper, we sought to understand which observable socio-technical attributes of developers can be used to build good models of them being future @-mentioned in GitHub issues and pull request discussions. We built overall and project-specific predictive models of future @-mentions, in order to capture the determinants of @-mentions in each of two hundred GitHub projects, and to understand if and how those determinants differ between projects. We found that visibility, expertise, and productivity are associated with an increase in @-mentions, while responsiveness is not, in the presence of a number of control variables. Also, we find that though project-specific differences exist, the overall model can be used for cross-project prediction, indicating its GitHub-wide utility. △ Less

Submitted 21 June, 2018; originally announced June 2018.

Comments: 12 pages, 5 figures, 2 tables

ACM Class: D.2.2

arXiv:1806.07619  [pdf, other]  cs.SE 
doi
10.1109/SEAA.2018.00068
A Large-Scale Study on Source Code Reviewer Recommendation

Authors: Jakub Lipcak, Bruno Rossi

Abstract: Context: Software code reviews are an important part of the development process, leading to better software quality and reduced overall costs. However, finding appropriate code reviewers is a complex and time-consuming task. Goals: In this paper, we propose a large-scale study to compare performance of two main source code reviewer recommendation algorithms (RevFinder and a Naive Bayes-based approach) in identifying the best code reviewers for opened pull requests. Method: We mined data from Github and Gerrit repositories, building a large dataset of 51 projects, with more than 293K pull requests analyzed, 180K owners and 157K reviewers. Results: Based on the large analysis, we can state that i) no model can be generalized as best for all projects, ii) the usage of a different repository (Gerrit, GitHub) can have impact on the the recommendation results, iii) exploiting sub-projects information available in Gerrit can improve the recommendation results. △ Less

Submitted 20 June, 2018; originally announced June 2018.

Comments: Published at the 44th Euromicro Conference on Software Engineering and Advanced Applications (SEAA 2018)

arXiv:1803.10198  [pdf]  cs.PL cs.SE 
doi
10.22152/programming-journal.org/2018/2/6
Proactive Empirical Assessment of New Language Feature Adoption via Automated Refactoring: The Case of Java 8 Default Methods

Authors: Raffi Khatchadourian, Hidehiko Masuhara

Abstract: Programming languages and platforms improve over time, sometimes resulting in new language features that offer many benefits. However, despite these benefits, developers may not always be willing to adopt them in their projects for various reasons. In this paper, we describe an empirical study where we assess the adoption of a particular new language feature. Studying how developers use (or do not use) new language features is important in programming language research and engineering because it gives designers insight into the usability of the language to create meaning programs in that language. This knowledge, in turn, can drive future innovations in the area. Here, we explore Java 8 default methods, which allow interfaces to contain (instance) method implementations. Default methods can ease interface evolution, make certain ubiquitous design patterns redundant, and improve both modularity and maintainability. A focus of this work is to discover, through a scientific approach and a novel technique, situations where developers found these constructs useful and where they did not, and the reasons for each. Although several studies center around assessing new language features, to the best of our knowledge, this kind of construct has not been previously considered. Despite their benefits, we found that developers did not adopt default methods in all situations. Our study consisted of submitting pull requests introducing the language feature to 19 real-world, open source Java projects without altering original program semantics. This novel assessment technique is proactive in that the adoption was driven by an automatic refactoring approach rather than waiting for developers to discover and integrate the feature themselves. In this way, we set forth best practices and patterns of using the language feature effectively earlier rather than later and are able to possibly guide (near) future language evolution. We foresee this technique to be useful in assessing other new language features, design patterns, and other programming idioms. △ Less

Submitted 27 March, 2018; originally announced March 2018.

Journal ref: The Art, Science, and Engineering of Programming, 2018, Vol. 2, Issue 3, Article 6

arXiv:1803.03806  [pdf, other]  cs.SE
Learning Quick Fixes from Code Repositories

Authors: Reudismam Rolim, Gustavo Soares, Rohit Gheyi, Titus Barik, Loris D'Antoni

Abstract: Code analyzers such as Error Prone and FindBugs detect code patterns symptomatic of bugs, performance issues, or bad style. These tools express patterns as quick fixes that detect and rewrite unwanted code. However, it is difficult to come up with new quick fixes and decide which ones are useful and frequently appear in real code. We propose to rely on the collective wisdom of programmers and learn quick fixes from revision histories in software repositories. We present REVISAR, a tool for discovering common Java edit patterns in code repositories. Given code repositories and their revision histories, REVISAR (i) identifies code edits from revisions and (ii) clusters edits into sets that can be described using an edit pattern. The designers of code analyzers can then inspect the patterns and add the corresponding quick fixes to their tools. We ran REVISAR on nine popular GitHub projects, and it discovered 89 useful edit patterns that appeared in 3 or more projects. Moreover, 64% of the discovered patterns did not appear in existing tools. We then conducted a survey with 164 programmers from 124 projects and found that programmers significantly preferred eight out of the nine of the discovered patterns. Finally, we submitted 16 pull requests applying our patterns to 9 projects and, at the time of the writing, programmers accepted 6 (60%) of them. The results of this work aid toolsmiths in discovering quick fixes and making informed decisions about which quick fixes to prioritize based on patterns programmers actually apply in practice. △ Less

Submitted 7 September, 2018; v1 submitted 10 March, 2018; originally announced March 2018.

Comments: 12 pages

arXiv:1802.06183  [pdf]  cs.DB
Towards Realisation of Heterogeneous Earth-Observation Sensor Database Framework for the Sensor Observation Service based on PostGIS

Authors: Maduako N. Ikechukwu, Francis I. Okeke

Abstract: Environmental monitoring and management systems in most cases deal with models and spatial analytics that involve the integration of in-situ and remote Geosensor observations. In-situ sensor observations and those gathered by remote sensors are usually provided by different databases and services in real-time dynamic services such as the Geo-Web Services. Thus, data have to be pulled from different databases and transferred over the network before they are fused and processed on the service middleware. This process is very massive and unnecessary communication-work load on the service middleware. Massive work load in large raster downloads from flat-file raster data sources each time a request is made and huge integration and geo-processing work load on the service middleware which could actually be better leveraged at the database This paper therefore proposes the realization of heterogeneous sensor database framework based on PostGIS for integration, geo-processing and spatial analysis of remote and in-situ sensor observations at the database level. Also discussed in this paper is how the framework can be integrated in the Sensor Observation Service (SOS) to reduce communication and massive workload on the Geospatial Web Services and as well make query request from the user end a lot more flexible. Keywords: Earth-Observation, Heterogeneous Earth-Observation Sensor Database, PostGIS , Sensor Observation Service. △ Less

Submitted 16 February, 2018; originally announced February 2018.

arXiv:1801.03890  [pdf, other]  cs.NI
HoPP: Robust and Resilient Publish-Subscribe for an Information-Centric Internet of Things

Authors: Cenk Gündoğan, Peter Kietzmann, Thomas C. Schmidt, Matthias Wählisch

Abstract: This paper revisits NDN deployment in the IoT with a special focus on the interaction of sensors and actuators. Such scenarios require high responsiveness and limited control state at the constrained nodes. We argue that the NDN request-response pattern which prevents data push is vital for IoT networks. We contribute HoP-and-Pull (HoPP), a robust publish-subscribe scheme for typical IoT scenarios that targets IoT networks consisting of hundreds of resource constrained devices at intermittent connectivity. Our approach limits the FIB tables to a minimum and naturally supports mobility, temporary network partitioning, data aggregation and near real-time reactivity. We experimentally evaluate the protocol in a real-world deployment using the IoT-Lab testbed with varying numbers of constrained devices, each wirelessly interconnected via IEEE 802.15.4 LowPANs. Implementations are built on CCN-lite with RIOT and support experiments using various single- and multi-hop scenarios. △ Less

Submitted 11 January, 2018; originally announced January 2018.

arXiv:1710.10421  [pdf]  cs.SE
Topic-based Integrator Matching for Pull Request

Authors: Zhifang Liao, Yanbing Li, Jinsong Wu, Dayu He, Xiaoping Fan, Yan Zhang

Abstract: Pull Request (PR) is the main method for code contributions from the external contributors in GitHub. PR review is an essential part of open source software developments to maintain the quality of software. Matching a new PR for an appropriate integrator will make the PR reviewing more effective. However, PR and integrator matching are now organized manually in GitHub. To make this process more efficient, we propose a Topic-based Integrator Matching Algorithm (TIMA) to predict highly relevant collaborators(the core developers) as the integrator to incoming PRs . TIMA takes full advantage of the textual semantics of PRs. To define the relationships between topics and collaborators, TIMA builds a relation matrix about topic and collaborators. According to the relevance between topics and collaborators, TIMA matches the suitable collaborators as the PR integrator. △ Less

Submitted 28 October, 2017; originally announced October 2017.

arXiv:1709.10324  [pdf, other]  cs.SE
The Health and Wealth of OSS Projects: Evidence from Community Activities and Product Evolution

Authors: Saya Onoue, Raula Gaikovina Kula, Hideaki Hata, Kenichi Matsumoto

Abstract: Background: Understanding the condition of OSS projects is important to analyze features and predict the future of projects. In the field of demography and economics, health and wealth are considered to understand the condition of a country. Aim: In this paper, we apply this framework to OSS projects to understand the communities and the evolution of OSS projects from the perspectives of health and wealth. Method: We define two measures of Workforce (WF) and Gross Product Pull Requests (GPPR). We analyze OSS projects in GitHub and investigate three typical cases. Results: We find that wealthy projects attract and rely on the casual workforce. Less wealthy projects may require additional efforts from their more experienced contributors. Conclusions: This paper presents an approach to assess the relationship between health and wealth of OSS projects. An interactive demo of our analysis is available at goo.gl/Ig6NTR. △ Less

Submitted 29 September, 2017; originally announced September 2017.

Comments: Submitted 2017

arXiv:1709.03777  [pdf]  cs.SI cs.CY 
doi
10.1002/itl2.6
Establishing Personal Trust-based Connections in Distributed Teams

Authors: Fabio Calefato, Filippo Lanubile

Abstract: Trust is a factor that dramatically contributes to the success or failure of distributed software teams. We present a research model showing that social communication between distant developers enables the affective appraisal of trustworthiness even from a distance, thus increasing project performance. To overcome the limitations of self-reported data, typically questionnaires, we focus on software projects following a pull request-based development model and approximate the overall performance of a software project with the history of successful collaborations occurring between developers. △ Less

Submitted 1 October, 2017; v1 submitted 12 September, 2017; originally announced September 2017.

Comments: 6 pages (to appear)

Journal ref: Internet Technology Letters. 2017;e6

arXiv:1708.06860  [pdf, other]  cs.SI
GitHub and Stack Overflow: Analyzing Developer Interests Across Multiple Social Collaborative Platforms

Authors: Roy Ka-Wei Lee, David Lo

Abstract: Increasingly, software developers are using a wide array of social collaborative platforms for software development and learning. In this work, we examined the similarities in developer's interests within and across GitHub and Stack Overflow. Our study finds that developers share common interests in GitHub and Stack Overflow, on average, 39% of the GitHub repositories and Stack Overflow questions that a developer had participated fall in the common interests. Also, developers do share similar interests with other developers who co-participated activities in the two platforms. In particular, developers who co-commit and co-pull-request same GitHub repositories and co-answer same Stack Overflow questions, share more common interests compare to other developers who co-participate in other platform activities. △ Less

Submitted 24 August, 2017; v1 submitted 22 August, 2017; originally announced August 2017.

Comments: Pre-print for 9th International Conference on Social Informatics (SocInfo 2017)

ACM Class: H.2.8

arXiv:1708.02618  [pdf, other]  cs.SE 
doi
10.1007/s1133
An Empirical Comparison of Developer Retention in the RubyGems and npm Software Ecosystems

Authors: Eleni Constantinou, Tom Mens

Abstract: Software ecosystems can be viewed as socio-technical networks consisting of technical components (software packages) and social components (communities of developers) that maintain the technical components. Ecosystems evolve over time through socio-technical changes that may greatly impact the ecosystem's sustainability. Social changes like developer turnover may lead to technical degradation. This motivates the need to identify those factors leading to developer abandonment, in order to automate the process of identifying developers with high abandonment risk. This paper compares such factors for two software package ecosystems, RubyGems and npm. We analyse the evolution of their packages hosted on GitHub, considering development activity in terms of commits, and social interaction with other developers in terms of comments associated to commits, issues or pull requests. We analyse this socio-technical activity for more than 30k and 60k developers for RubyGems and npm respectively. We use survival analysis to identify which factors coincide with a lower survival probability. Our results reveal that developers with a higher probability to abandon an ecosystem: do not engage in discussions with other developers; do not have strong social and technical activity intensity; communicate or commit less frequently; and do not participate to both technical and social activities for long periods of time. Such observations could be used to automate the identification of developers with a high probability of abandoning the ecosystem and, as such, reduce the risks associated to knowledge loss. △ Less

Submitted 8 August, 2017; originally announced August 2017.

Comments: This paper is a preprint of a paper that has been accepted for publication in the Springer's journal Innovations in Systems and Software Engineering

Journal ref: Innovations in Systems and Software Engineering 2017, Volume 13, Issue 2-3, pp 101-115

arXiv:1704.06860  [pdf, ps, other]  cs.DB cs.CR cs.CY cs.HC
Location Privacy in Spatial Crowdsourcing

Authors: Hien To, Cyrus Shahabi

Abstract: Spatial crowdsourcing (SC) is a new platform that engages individuals in collecting and analyzing environmental, social and other spatiotemporal information. With SC, requesters outsource their spatiotemporal tasks to a set of workers, who will perform the tasks by physically traveling to the tasks' locations. This chapter identifies privacy threats toward both workers and requesters during the two main phases of spatial crowdsourcing, tasking and reporting. Tasking is the process of identifying which tasks should be assigned to which workers. This process is handled by a spatial crowdsourcing server (SC-server). The latter phase is reporting, in which workers travel to the tasks' locations, complete the tasks and upload their reports to the SC-server. The challenge is to enable effective and efficient tasking as well as reporting in SC without disclosing the actual locations of workers (at least until they agree to perform a task) and the tasks themselves (at least to workers who are not assigned to those tasks). This chapter aims to provide an overview of the state-of-the-art in protecting users' location privacy in spatial crowdsourcing. We provide a comparative study of a diverse set of solutions in terms of task publishing modes (push vs. pull), problem focuses (tasking and reporting), threats (server, requester and worker), and underlying technical approaches (from pseudonymity, cloaking, and perturbation to exchange-based and encryption-based techniques). The strengths and drawbacks of the techniques are highlighted, leading to a discussion of open problems and future work. △ Less

Submitted 22 April, 2017; originally announced April 2017.

arXiv:1704.04848  [pdf, other]  cs.NI
The Power of Waiting for More than One Response in Minimizing the Age-of-Information

Authors: Yu Sang, Bin Li, Bo Ji

Abstract: The Age-of-Information (AoI) has recently been proposed as an important metric for investigating the timeliness performance in information-update systems. Prior studies on AoI optimization often consider a Push model, which is concerned about when and how to "push" (i.e., generate and transmit) the updated information to the user. In stark contrast, in this paper we introduce a new Pull model, which is more relevant for certain applications (such as the real-time stock quotes service), where a user sends requests to the servers to proactively "pull" the information of interest. Moreover, we propose to employ request replication to reduce the AoI. Interestingly, we find that under this new Pull model, replication schemes capture a novel tradeoff between different levels of information freshness and different response times across the servers, which can be exploited to minimize the expected AoI at the user's side. Specifically, assuming Poisson updating process at the servers and exponentially distributed response time, we derive a closedform formula for computing the expected AoI and obtain the optimal number of responses to wait for to minimize the expected AoI. Finally, we conduct numerical simulations to elucidate our theoretical results. Our findings show that waiting for more than one response can significantly reduce the AoI in most scenarios. △ Less

Submitted 18 August, 2017; v1 submitted 16 April, 2017; originally announced April 2017.

arXiv:1702.08571  [pdf, other]  cs.SE
Replicating and Scaling up Qualitative Analysis using Crowdsourcing: A Github-based Case Study

Authors: Di Chen, Kathryn T. Stolee, Tim Menzies

Abstract: Due to the difficulties in replicating and scaling up qualitative studies, such studies are rarely verified. Accordingly, in this paper, we leverage the advantages of crowdsourcing (low costs, fast speed, scalable workforce) to replicate and scale-up one state-of-the-art qualitative study. That qualitative study explored 20 GitHub pull requests to learn factors that influence the fate of pull requests with respect to approval and merging. As a secondary study, using crowdsourcing at a cost of $200, we studied 250 pull requests from 142 GitHub projects. The prior qualitative findings are mapped into questions for crowds workers. Their answers were converted into binary features to build a predictor which predicts whether code would be merged with median F1 scores of 68%. For the same large group of pull requests, the median F1 scores could achieve 90% by a predictor built with additional features defined by prior quantitative results. Based on this case study, we conclude that there is much benefit in combining different kinds of research methods. While qualitative insights are very useful for finding novel insights, they can be hard to scale or replicate. That said, they can guide and define the goals of scalable secondary studies that use (e.g.) crowdsourcing+data mining. On the other hand, while data mining methods are reproducible and scalable to large data sets, their results may be spectacularly wrong since they lack contextual information. That said, they can be used to test the stability and external validity, of the insights gained from a qualitative analysis. △ Less

Submitted 1 March, 2017; v1 submitted 27 February, 2017; originally announced February 2017.

Comments: Submitted to FSE'17, 12 pages

arXiv:1702.04958  [pdf]  cs.SE 
doi
10.1109/ICGSE.2017.1
A Preliminary Analysis on the Effects of Propensity to Trust in Distributed Software Development

Authors: Fabio Calefato, Filippo Lanubile, Nicole Novielli

Abstract: Establishing trust between developers working at distant sites facilitates team collaboration in distributed software development. While previous research has focused on how to build and spread trust in absence of direct, face-to-face communication, it has overlooked the effects of the propensity to trust, i.e., the trait of personality representing the individual disposition to perceive the others as trustworthy. In this study, we present a preliminary, quantitative analysis on how the propensity to trust affects the success of collaborations in a distributed project, where the success is represented by pull requests whose code changes and contributions are successfully merged into the project's repository. △ Less

Submitted 3 October, 2017; v1 submitted 16 February, 2017; originally announced February 2017.

Comments: 5 pages

Journal ref: Proceedings of the 2017 IEEE 12th International Conference on Global Software Engineering (ICGSE), IEEE, pp.56-60

arXiv:1701.02524  [pdf]  cs.NI 
doi
10.1109/ICC.2012.6363958
A Chunk Caching Location and Searching Scheme in Content Centric Networking

Authors: Yang Li, Tao Lin, Hui Tang, Peng Sun

Abstract: Content Centric Networking (CCN) is a new network infrastructure around content dissemination and retrieval, shift from host addresses to named data. Each CCN router has a cache to store the chunks passed by it. Therefore the caching strategy about chunk placement can greatly affect the whole CCN performance. This paper proposes an implicit coordinate chunk caching location and searching scheme (CLS) in CCN hierarchical infrastructure. In CLS, there is at most one copy of a chunk cached on the path between a server and a leaf router. This copy is pulled down one level towards the leaf router by a request or pushed up one level towards the server by the cache eviction. Thus, it is possible to store more diverse contents in the whole CCN and improve the network performance. Plus, in order to reduce the server workload and file download time, a caching trail of chunk is created to direct the following request where to find the chunk. Extensive test-bed experiments have been performed to evaluate the proposed scheme in terms of a wide range of performance metrics. The results show that the proposed scheme outperforms existing algorithms. △ Less

Submitted 10 January, 2017; originally announced January 2017.

Journal ref: Communications (ICC), 2012 IEEE International Conference on

arXiv:1606.00521  [pdf, other]  cs.SE
Initial and Eventual Software Quality Relating to Continuous Integration in GitHub

Authors: Yue Yu, Bogdan Vasilescu, Huaimin Wang, Vladimir Filkov, Premkumar Devanbu

Abstract: The constant demand for new features and bug fixes are forcing software projects to shorten cycles and deliver updates ever faster, while sustaining software quality. The availability of inexpensive, virtualized, cloud-computing has helped shorten schedules, by enabling continuous integration (CI) on demand. Platforms like GitHub support CI in-the-cloud. In projects using CI, a user submitting a pull request triggers a CI step. Besides speeding up build and test, this fortuitously creates voluminous archives of build and test successes and failures. CI is a relatively new phenomenon, and these archives allow a detailed study of CI. How many problems are exposed? Where do they occur? What factors affect CI failures? Does the "initial quality" as ascertained by CI predict how many bugs will later appear ("eventual quality") in the code? In this paper, we undertake a large-scale, fine resolution study of these records, to better understand CI processes, the nature, and predictors of CI failures, and the relationship of CI failures to the eventual quality of the code. We find that: a) CI failures appear to be concentrated in a few files, just like normal bugs; b) CI failures are not very highly correlated with eventual failures; c) The use of CI in a pull request doesn't necessarily mean the code in that request is of good quality. △ Less

Submitted 1 June, 2016; originally announced June 2016.

arXiv:1604.01450  [pdf, other]  cs.SE cs.SI
Does Technical Debt Lead to the Rejection of Pull Requests?

Authors: Marcelino Campos Oliveira Silva, Marco Tulio Valente, Ricardo Terra

Abstract: Technical Debt is a term used to classify non-optimal solutions during software development. These solutions cause several maintenance problems and hence they should be avoided or at least documented. Although there are a considered number of studies that focus on the identification of Technical Debt, we focus on the identification of Technical Debt in pull requests. Specifically, we conduct an investigation to reveal the different types of Technical Debt that can lead to the rejection of pull requests. From the analysis of 1,722 pull requests, we classify Technical Debt in seven categories namely design, documentation, test, build, project convention, performance, or security debt. Our results indicate that the most common category of Technical Debt is design with 39.34%, followed by test with 23.70% and project convention with 15.64%. We also note that the type of Technical Debt influences on the size of push request discussions, e.g., security and project convention debts instigate more discussion than the other types. △ Less

Submitted 5 April, 2016; originally announced April 2016.

Comments: Accepted at the Brazilian Symposium on Information Systems (SBSI), p. 1-7, 2016

arXiv:1512.01862  [pdf, other]  cs.SE 
doi
10.1109/ICSME.2014.62
Continuous integration in a social-coding world: Empirical evidence from GitHub. **Updated version with corrections**

Authors: Bogdan Vasilescu, Stef van Schuylenburg, Jules Wulms, Alexander Serebrenik, Mark G. J. van den Brand

Abstract: Continuous integration is a software engineering practice of frequently merging all developer working copies with a shared main branch, e.g., several times a day. With the advent of GitHub, a platform well known for its "social coding" features that aid collaboration and sharing, and currently the largest code host in the open source world, collaborative software development has never been more prominent. In GitHub development one can distinguish between two types of developer contributions to a project: direct ones, coming from a typically small group of developers with write access to the main project repository, and indirect ones, coming from developers who fork the main repository, update their copies locally, and submit pull requests for review and merger. In this paper we explore how GitHub developers use continuous integration as well as whether the contribution type (direct versus indirect) and different project characteristics (e.g., main programming language, or project age) are associated with the success of the automatic builds. △ Less

Submitted 6 December, 2015; originally announced December 2015.

Comments: This is an updated and corrected version of our ICSME 2014 paper: http://dx.doi.org/10.1109/ICSME.2014.62

arXiv:1506.00828  [pdf, other]  cs.DC
Rumor Spreading with Bounded In-Degree

Authors: Sebastian Daum, Fabian Kuhn, Yannic Maus

Abstract: In the classic gossip-based model of communication for disseminating information in a network, in each time unit, every node u is allowed to contact a single random neighbor v. If u knows the data (rumor) to be disseminated, it disperses it to v (known as PUSH) and if it does not, it requests it from v (known as PULL). While in the classic gossip model, each node is only allowed to contact a single neighbor in each time unit, each node can possibly be contacted by many neighboring nodes. In the present paper, we consider a restricted model where at each node only one incoming request can be served. As long as only a single piece of information needs to be disseminated, this does not make a difference for push requests. It however has a significant effect on pull requests. In the paper, we therefore concentrate on this weaker pull version, which we call 'restricted pull'. We distinguish two versions of the restricted pull protocol depending on whether the request to be served among a set of pull requests at a given node is chosen adversarially or uniformly at random. As a first result, we prove an exponential separation between the two variants. We show that there are instances where if an adversary picks the request to be served, the restricted pull protocol requires a polynomial number of rounds whereas if the winning request is chosen uniformly at random, the restricted pull protocol only requires a polylogarithmic number of rounds to inform the whole network. Further, as the main technical contribution, we show that if the request to be served is chosen randomly, the slowdown of using restricted pull versus using the classic pull protocol can w.h.p. be upper bounded by O(Δ/δlogn), where Δ and δ are the largest and smallest degree of the network. △ Less

Submitted 22 September, 2015; v1 submitted 2 June, 2015; originally announced June 2015.

arXiv:1505.06856  [pdf, ps, other]  cs.NI cs.IT
WiFlix: Adaptive Video Streaming in Massive MU-MIMO Wireless Networks

Authors: Dilip Bethanabhotla, Giuseppe Caire, Michael J. Neely

Abstract: We consider the problem of simultaneous on-demand streaming of stored video to multiple users in a multi-cell wireless network where multiple unicast streaming sessions are run in parallel and share the same frequency band. Each streaming session is formed by the sequential transmission of video "chunks," such that each chunk arrives into the corresponding user playback buffer within its playback deadline. We formulate the problem as a Network Utility Maximization (NUM) where the objective is to fairly maximize users' video streaming Quality of Experience (QoE) and then derive an iterative control policy using Lyapunov Optimization, which solves the NUM problem up to any level of accuracy and yields an online protocol with control actions at every iteration decomposing into two layers interconnected by the users' request queues : i) a video streaming adaptation layer reminiscent of DASH, implemented at each user node; ii) a transmission scheduling layer where a max-weight scheduler is implemented at each base station. The proposed chunk request scheme is a pull strategy where every user opportunistically requests video chunks from the neighboring base stations and dynamically adapts the quality of its requests based on the current size of the request queue. For the transmission scheduling component, we first describe the general max-weight scheduler and then particularize it to a wireless network where the base stations have multiuser MIMO (MU-MIMO) beamforming capabilities. We exploit the channel hardening effect of large-dimensional MIMO channels (massive MIMO) and devise a low complexity user selection scheme to solve the underlying combinatorial problem of selecting user subsets for downlink beamforming, which can be easily implemented and run independently at each base station. △ Less

Submitted 26 May, 2015; originally announced May 2015.

Comments: 30 pages. arXiv admin note: text overlap with arXiv:1304.8083

arXiv:1403.3080  [pdf, other]  cs.LG math.OC stat.ML
Statistical Decision Making for Optimal Budget Allocation in Crowd Labeling

Authors: Xi Chen, Qihang Lin, Dengyong Zhou

Abstract: In crowd labeling, a large amount of unlabeled data instances are outsourced to a crowd of workers. Workers will be paid for each label they provide, but the labeling requester usually has only a limited amount of the budget. Since data instances have different levels of labeling difficulty and workers have different reliability, it is desirable to have an optimal policy to allocate the budget among all instance-worker pairs such that the overall labeling accuracy is maximized. We consider categorical labeling tasks and formulate the budget allocation problem as a Bayesian Markov decision process (MDP), which simultaneously conducts learning and decision making. Using the dynamic programming (DP) recurrence, one can obtain the optimal allocation policy. However, DP quickly becomes computationally intractable when the size of the problem increases. To solve this challenge, we propose a computationally efficient approximate policy, called optimistic knowledge gradient policy. Our MDP is a quite general framework, which applies to both pull crowdsourcing marketplaces with homogeneous workers and push marketplaces with heterogeneous workers. It can also incorporate the contextual information of instances when they are available. The experiments on both simulated and real data show that the proposed policy achieves a higher labeling accuracy than other existing policies at the same budget level. △ Less

Submitted 24 April, 2014; v1 submitted 12 March, 2014; originally announced March 2014.

Comments: 39 pages

arXiv:1401.6476  [pdf, ps, other]  cs.IT cs.MM cs.NI math.OC
Adaptive Video Streaming in MU-MIMO Networks

Authors: Dilip Bethanabhotla, Giuseppe Caire, Michael J. Neely

Abstract: We consider extensions and improvements on our previous work on dynamic adaptive video streaming in a multi-cell multiuser ``small cell'' wireless network. Previously, we treated the case of single-antenna base stations and, starting from a network utility maximization (NUM) formulation, we devised a ``push'' scheduling policy, where users place requests to sequential video chunks to possibly different base stations with adaptive video quality, and base stations schedule their downlink transmissions in order to stabilize their transmission queues. In this paper we consider a ``pull'' strategy, where every user maintains a request queue, such that users keep track of the video chunks that are effectively delivered. The pull scheme allows to download the chunks in the playback order without skipping or missing them. In addition, motivated by the recent/forthcoming progress in small cell networks (e.g., in wave-2 of the recent IEEE 802.11ac standard), we extend our dynamic streaming approach to the case of base stations capable of multiuser MIMO downlink, i.e., serving multiple users on the same time-frequency slot by spatial multiplexing. By exploiting the ``channel hardening'' effect of high dimensional MIMO channels, we devise a low complexity user selection scheme to solve the underlying max-weighted rate scheduling, which can be easily implemented and runs independently at each base station. Through simulations, we show MIMO gains in terms of video streaming QoE metrics like the pre-buffering and re-buffering times. △ Less

Submitted 24 January, 2014; originally announced January 2014.

Comments: submitted to IEEE Intl. Symposium on Information Theory 2014

arXiv:1401.6132  [pdf]  cs.NI cs.MM
Differenciated Bandwidth Allocation in P2P Layered Streaming

Authors: Abbas Bradai, Toufik Ahmed

Abstract: There is an increasing demand for P2P streaming in particular for layered video. In this category of applications, the stream is composed of hierarchically encoded sub-streams layers namely the base layer and enhancements layers. We consider a scenario where the receiver peer uses the pull-based approach to adjust the video quality level to their capability by subscribing to different number of layers. We note that higher layers received without their corresponding lower layers are considered as useless and cannot be played, consequently the throughput of the system will drastically degrade. To avoid this situation, we propose an economical model based on auction mechanisms to optimize the allocation of sender peers' upload bandwidth. The upstream peers organize auctions to "sell" theirs items (links' bandwidth) according to bids submitted by the downstream peers taking into consideration the peers priorities and the requested layers importance. The ultimate goal is to satisfy the quality level requirement for each peer, while reducing the overall streaming cost. Through theoretical study and performance evaluation we show the effectiveness of our model in terms of users and network's utility. △ Less

Submitted 21 October, 2013; originally announced January 2014.

Comments: International Workshop on Computer Aided Modeling and Design of Communication Links and Networks (CAMAD), Barcelone : Spain (2012)

arXiv:1310.5557  [pdf]  cs.NI
On the Optimal Scheduling in Pull-based Real-Time P2P Streaming Systems: Layered and Non-Layered Streaming

Authors: Abbas Bradai, Toufik Ahmed

Abstract: During the last decade, we witnessed a rapid growth in deployment of pull-based P2P streaming applications. In these applications, each node selects some other nodes as its neighbors and requests streaming data from them. This scheme allows eliminating data redundancy and recovering from data loss, but it pushes the complexity to the receiver node side. In this paper, we theoretically study the scheduling problem in Pull-based P2P video streaming and we model it as an assignment problem. Then, we propose AsSched, new scheduling algorithm for layered streaming, in order to optimize the throughput and the delivery ratio of the system. In second time, we derive an optimal algorithm (NAsSched) for non layered streaming. The results of simulations show that our algorithms significantly outperform classic scheduling strategies especially in stern bandwidth constraints. △ Less

Submitted 21 October, 2013; originally announced October 2013.

Comments: IEEE ICC 2012, Ottawa : Canada (2012)

arXiv:1309.3675  [pdf, ps, other]  cs.DS
Optimizing Maximum Flow Time and Maximum Throughput in Broadcast Scheduling

Authors: Sungjin Im, Maxim Sviridenko

Abstract: We consider the pull-based broadcast scheduling model. In this model, there are n unit-sized pages of information available at the server. Requests arrive over time at the server asking for a specific page. When the server transmits a page, all outstanding requests for the page are simultaneously satisfied, and this is what distinguishes broadcast scheduling from the standard scheduling setting where each job must be processed separately by the server. Broadcast scheduling has received a considerable amount of attention due to the algorithmic challenges that it gives in addition to its applications in multicast systems and wireless and LAN networks. In this paper, we give the following new approximation results for two popular objectives: - For the objective of minimizing the maximum flow time, we give the first PTAS. Previously, it was known that the algorithm First-In-First-Out (FIFO) is a 2-approximation, and it is tight. It has been suggested as an open problem to obtain a better approximation. - For the objective of maximizing the throughput, we give a 0.7759-approximation which improves upon the previous best known 0.75-approximation. Our improved results are enabled by our novel rounding schemes and linear programming which can effectively reduce congestion in schedule which is often the main bottleneck in designing scheduling algorithms based on linear programming. We believe that our algorithmic ideas and techniques could be of potential use for other scheduling problems. △ Less

Submitted 14 September, 2013; originally announced September 2013.

Comments: 31 pages

arXiv:1302.4030  [pdf, ps, other]  cs.NI 
doi
10.1016/j.comcom.2013.12.002
Modeling and Performance Analysis of Pull-Based Live Streaming Schemes in Peer-to-Peer Network

Authors: Jianwei Zhang, Wei Xing, Yongchao Wang, Dongming Lu

Abstract: Recent years mesh-based Peer-to-Peer live streaming has become a promising way for service providers to offer high-quality live video streaming service to Internet users. In this paper, we make a detailed study on modeling and performance analysis of the pull-based P2P streaming systems. We establish the analytical framework for the pull-based streaming schemes in P2P network, give accurate models of the chunk selection and peer selection strategies, and organize them into three categories, i.e., the chunk first scheme, the peer first scheme and the epidemic scheme. Through numerical performance evaluation, the impacts of some important parameters, such as size of neighbor set, reply number, buffer size and so on are investigated. For the peer first and chunk first scheme, we show that the pull-based schemes do not perform as well as the push-based schemes when peers are limited to reply only one request in each time slot. When the reply number increases, the pull-based streaming schemes will reach close to optimal playout probability. As to the pull-based epidemic scheme, we find it has unexpected poor performance, which is significantly different from the push-based epidemic scheme. Therefore we propose a simple, efficient and easily deployed push-pull scheme which can significantly improve the playout probability. △ Less

Submitted 16 February, 2013; originally announced February 2013.

Journal ref: Computer Communications, vol. 40, pp. 22-32, Mar. 2014

arXiv:1202.2092  [pdf, other]  cs.DC cs.DM cs.DS
Discovery through Gossip

Authors: Bernhard Haeupler, Gopal Pandurangan, David Peleg, Rajmohan Rajaraman, Zhifeng Sun

Abstract: We study randomized gossip-based processes in dynamic networks that are motivated by discovery processes in large-scale distributed networks like peer-to-peer or social networks. A well-studied problem in peer-to-peer networks is the resource discovery problem. There, the goal for nodes (hosts with IP addresses) is to discover the IP addresses of all other hosts. In social networks, nodes (people) discover new nodes through exchanging contacts with their neighbors (friends). In both cases the discovery of new nodes changes the underlying network - new edges are added to the network - and the process continues in the changed network. Rigorously analyzing such dynamic (stochastic) processes with a continuously self-changing topology remains a challenging problem with obvious applications. This paper studies and analyzes two natural gossip-based discovery processes. In the push process, each node repeatedly chooses two random neighbors and puts them in contact (i.e., "pushes" their mutual information to each other). In the pull discovery process, each node repeatedly requests or "pulls" a random contact from a random neighbor. Both processes are lightweight, local, and naturally robust due to their randomization. Our main result is an almost-tight analysis of the time taken for these two randomized processes to converge. We show that in any undirected n-node graph both processes take O(n log^2 n) rounds to connect every node to all other nodes with high probability, whereas Omega(n log n) is a lower bound. In the directed case we give an O(n^2 log n) upper bound and an Omega(n^2) lower bound for strongly connected directed graphs. A key technical challenge that we overcome is the analysis of a randomized process that itself results in a constantly changing network which leads to complicated dependencies in every round. △ Less

Submitted 9 February, 2012; originally announced February 2012.

Comments: 19 pages

arXiv:1110.2294  [pdf, ps, other]  astro-ph.IM cs.DB 
doi
10.1007/s10686-011-9263-0
Query Driven Visualization of Astronomical Catalogs

Authors: Hugo Buddelmeijer, Edwin A. Valentijn

Abstract: Interactive visualization of astronomical catalogs requires novel techniques due to the huge volumes and complex structure of the data produced by existing and upcoming astronomical surveys. The creation as well as the disclosure of the catalogs can be handled by data pulling mechanisms. These prevent unnecessary processing and facilitate data sharing by having users request the desired end products. In this work we present query driven visualization as a logical continuation of data pulling. Scientists can request catalogs in a declarative way and set process parameters directly from within the visualization. This results in profound interoperation between software with a high level of abstraction. New messages for the Simple Application Messaging Protocol are proposed to achieve this abstraction. Support for these messages are implemented in the Astro-WISE information system and in a set of demonstrational applications. △ Less

Submitted 11 October, 2011; originally announced October 2011.

Comments: Accepted for publication in topical issue of Experimental Astronomy on Astro-WISE information system

arXiv:1106.2207  [pdf]  cs.OH
Optimisation de la taille de la série: illustration par un cas industriel de sous-traitance mécanique

Authors: Barbara Lyonnet, Maurice Pillet, Magali Pralus

Abstract: Reducing costs of manufactured products is one of the key issues of companies. Bar turning companies (mechanical subcontracting companies) are faced with the following dilemma: use a pull strategy or use a push strategy. Instinctively these companies produce more than demand required by customers. This strategy allows them to respond to requests forecasts and reduce their cost of changeover time. These companies make a bet on sales opportunities and think to realize an additional profit. We have tried to find in this study to provide elements to know the limits of this strategy. Our proposal focuses on developing a model to support the decision taking into account the mix of opportunities, economic constraints and mean constraints. This model features the particular importance of high rates of ownership and the risk of not selling. Réduire les coûts de revient des produits fabriqués est une des problématiques essentielles des entreprises d'aujourd'hui. Les entreprises de décolletage (entreprises de sous-traitance mécanique) sont confrontées au dilemme suivant : produire juste la demande client ou produire plus. Instinctivement ces entreprises, dont les temps de changement de série sont élevés, cherchent à produire plus que la demande exigée par le client. Cette stratégie leur permet de répondre à des demandes prévisionnelles et réduire ainsi le coût de revient des produits. Ces entreprises réalisent un pari sur les opportunités de vente et pensent réaliser un gain supplémentaire en réalisant des stocks. Nous avons cherché dans cette étude à fournir des éléments de décision pour connaître les limites de cette règle de gestion. Notre proposition porte sur le développement d'un modèle d'aide à la décision prenant en considération le mixte entre opportunités commerciales, contraintes économiques et contraintes de moyen. Ce modèle souligne l'importance particulière du taux de possession et du risque de non vente. △ Less

Submitted 11 June, 2011; originally announced June 2011.

Journal ref: Congrès International de Génie Industriel CIGI'09, Tarbes : France (2009)

arXiv:1105.1328  [pdf]  cs.NI
Matchmaking Semantic Based for Information System Interoperability

Authors: I Wayan Simri Wicaksana

Abstract: Unlike the traditional model of information pull, matchmaking is base on a cooperative partnership between information providers and consumers, assisted by an intelligent facilitator (the matchmaker). Refer to some experiments, the matchmaking to be most useful in two different ways: locating information sources or services that appear dynamically and notification of information changes. Effective information and services sharing in distributed such as P2P based environments raises many challenges, including discovery and localization of resources, exchange over heterogeneous sources, and query processing. One traditional approach for dealing with some of the above challenges is to create unified integrated schemas or services to combine the heterogeneous sources. This approach does not scale well when applied in dynamic distributed environments and has many drawbacks related to the large numbers of sources. The main issues in matchmaking are how to represent advertising and request, and how to calculate possibility matching between advertising and request. The advertising and request can represent data or services by using many model of representation. In this paper, we address an approach of matchmaking by considering semantic agreement between sources. △ Less

Submitted 6 May, 2011; originally announced May 2011.

Comments: Gunadarma University; ICEEI2007

arXiv:1003.5631  [pdf]  cs.OH
A Mobile Message Scheduling and Delivery System using m-Learning framework

Authors: Moumita Majumder, Sumit Dhar

Abstract: Wireless data communications in form of Short Message Service (SMS) and Wireless Access Protocols (WAP) browsers have gained global popularity, yet, not much has been done to extend the usage of these devices in electronic learning (e-learning) and information sharing. This project explores the extension of e learning into wireless/ handheld (W/H) computing devices with the help of a mobile learning (m-learning) framework. This framework provides the requirements to develop m-learning application that can be used to share academic and administrative information among people within the university campus. A prototype application has been developed to demonstrate the important functionality of the proposed system in simulated environment. This system is supposed to work both in bulk SMS and interactive SMS delivery mode. Here we have combined both Short Message Service (SMS) and Wireless Access Protocols (WAP) browsers. SMS is used for Short and in time information delivery and WAP is used for detailed information delivery like course content, training material, interactive evolution tests etc. The push model is used for sending personalized multicasting messages to a group of mobile users with a common profile thereby improving the effectiveness and usefulness of the cntent delivered. Again pull mechanism can be applied for sending information as SMS when requested by end user in interactive SMS delivery mode. The main strength of the system is that, the actual SMS delivery application can be hosted on a mobile device, which can operate even when the device is on move. △ Less

Submitted 29 March, 2010; originally announced March 2010.

Journal ref: Journal of Telecommunications,Volume 1, Issue 2, pp30-34, March 2010