2015 technical reports

Hermes: Dynamic Partitioning for Distributed Social Network Graph Databases

Daniel Nicoara, Shahin Kamali, Khuzaima Daudjee and Lei Chen

Social networks are large graphs that require multiple graph database servers to store and manage them. Each database server hosts a graph partition with the objectives of balancing server loads, reducing remote traversals (edge-cuts), and adapting the partitioning to changes in the structure of the graph in the face of changing workloads. To achieve these objectives, a dynamic repartitioning algorithm is required to modify an existing partitioning to maintain good quality partitions while not imposing a significant overhead to the system. In this paper, we introduce a lightweight repartitioner, which dynamically modifies partitioning using a small amount of resources. In contrast to the existing repartitioning algorithms, our lightweight repartitioner is efficient, making it suitable for use in a real system. We integrated our lightweight repartitioner into Hermes, which we designed as an extension of the open source Neo4j graph database system, to support workloads over partitioned graph data distributed over multiple servers.

Using real-world social network data, we show that Hermes leverages the lightweight repartitioner to maintain high quality partitions and provides a two to three times performance improvement over the de-facto standard random hash-based partitioning.

The SPOT* System for Flexible Personal
Heating and Cooling

Alimohammad Rabbani and S. Keshav

Evaluating Call Graph Construction for JVM-hosted Language Implementations

Xiaoni Lai, Zhaoyi Luo, Karim Ali, Ondřej Lhoták, Julian Dolby, and Frank Tip

An increasing number of programming languages compile to the Java Virtual Machine (JVM), and program analysis frameworks such as WALA and SOOT support a broad range of program analysis algorithms by analyzing bytecode. While this approach works well when applied to bytecode produced from Java code, its efficacy when applied to other bytecode has not been studied until now.

We present qualitative and quantitative analysis of the soundness and precision of call graphs constructed from JVM bytecodes produced for Python, Ruby, Clojure, Groovy, Scala, and OCaml applications. We show that, for Python, Ruby, Clojure, and Groovy, the call graphs are unsound due to use of reflection, invokedynamic instructions, and run-time code generation, and imprecise due to how function calls are translated.

For Scala and OCaml, all unsoundness comes from rare, complex uses of reflection and proxies, and the translation of first-class features in Scala incurs a significant loss of precision.

Minyang Han and Khuzaima Daudjee

The bulk synchronous parallel (BSP) model used by synchronous graph processing systems allows algorithms to be easily implemented and reasoned about. However, BSP can suffer from poor performance due to stale messages and frequent global synchronization barriers. Asynchronous computation models have been proposed to alleviate these overheads but existing asynchronous systems that implement such models have limited scalability or retain frequent global barriers, and do not always support graph mutations or algorithms with multiple computation phases. We propose barrierless asynchronous parallel (BAP), a new computation model that reduces both message staleness and global synchronization. This enables BAP to overcome the limitations of existing asynchronous models while retaining support for graph mutations and algorithms with multiple computation phases. We present GiraphUC, which implements our BAP model in the open source distributed graph processing system Giraph, and evaluate our system at scale with large real-world graphs on 64 EC2 machines. We show that GiraphUC provides across-the-board performance improvements of up to $5\times$ faster over synchronous systems and up to an order of magnitude faster than asynchronous systems. Our results demonstrate that the BAP model provides efficient and transparent asynchronous execution of algorithms that are programmed synchronously.

The Development of Normative Autonomous Agents: an Approach

Marx Viana¹, Paulo Alencar², Donald Cowan², Carlos J. P. de Lucena¹

Open multi-agent systems (MASs) act as societies in which autonomous and heterogeneous agents can work towards similar or different goals. In order to cope with the heterogeneity, autonomy and diversity of interests among the different agents in the society, open MASs establish a set of behavioural norms that is used as a mechanism to ensure a state of co-operation among agents.  Such norms regulate the behaviour of the agents by defining obligations, permissions and prohibitions. Fulfillment of a norm may be encouraged through a reward while violation of a norm may be discouraged through punishment. Although norms are promising mechanisms to regulate an agent’s behaviour, we should note that each agent is an autonomous entity that is free to fulfill or violate each associated norm. Thus, agents can use different strategies when deciding to achieve their goals including whether to comply with their associated norms. Agents might choose to achieve their goals while ignoring their norms, thus overlooking the rewards or punishments they may receive. In contrast agents may choose to comply with all the norms although some of their goals may not be achieved. In this context, this paper proposes a framework for simulation of normative agents providing a basis for understanding the impacts of norms on agents.

Adapting to Climate Change - An Open Data Platform for Cumulative Environmental Analysis and Management

Donald Cowan, Paulo Alencar, Fred McGarry and Mark R. Palmer

The frequency of extreme weather events has accelerated, an apparent outcome of progressive climate change. Excess water is a significant consequence of these events and is now the leading cause of insurance claims for infrastructure and property damage. Governments recognize that plans for growth must reflect communities' needs, strengths and opportunities while balancing the cumulative effects of economic growth with environmental concerns. Legislation must incorporate the cumulative effects of economic growth with adaptation to weather events to protect the environment and citizens, while ensuring that products of growth such as buildings and infrastructure are resilient. For such a process to be effective it will be necessary for the private sector to develop and operate cumulative effect decision support software (CEDSS) tools and to work closely with all levels of government including watershed management authorities (WMAs) that supply environmental data. Such co-operation and sharing will require a new Open Data information-sharing platform managed by the private sector. This paper outlines that platform, its operation and possible governance model.

Precise Data Flow Analysis in the Presence of Correlated Method Calls

Marianna Rapoport, Ondřej Lhoták, and Frank Tip

When two methods are invoked on the same object, the dispatch behaviours of these method calls will be correlated. If two correlated method calls are polymorphic (i.e., they dispatch to different method definitions depending on the type of the receiver object), a program’s interprocedural control flow graph will contain infeasible paths. Existing algorithms for data-flow analysis are unable to ignore such infeasible paths, giving rise to loss of precision.

We show how infeasible paths due to correlated calls can be eliminated for Interprocedural Finite Distributive Subset (IFDS) problems, a large class of data-flow analysis problems with broad applications.

Our approach is to transform an IFDS problem into an Interprocedural Distributive Environment (IDE) problem, in which edge functions filter out data flow along infeasible paths. A solution to this IDE problem can be mapped back to the solution space of the original IFDS problem. We formalize the approach, prove it correct, and report on an implementation in the WALA analysis framework.

CrossStitch: An Efficient Transaction Processing Framework for Geo-Distributed Systems

Sharon Choy, Bernard Wong, Xu Cui, and Xiaoyi Liu

Current transaction systems for geo-distributed datastores either have high transaction processing latencies or are unable to support general transactions with dependent operations. In this paper, we introduce CrossStitch, an efficient transaction processing framework that reduces latency by restructuring each transaction into a chain of state transitions, where each state consists of a key operation and computation.

Transaction states are processed sequentially, and the transaction code and data is sent directly to the next hop in the chain. CrossStitch transactions can be organized such that all states in a location are processed before transitioning to a state in a different location. This allows CrossStitch to significantly reduce the number of inter-location crossings compared to transaction systems that retrieve remote data to a single location for processing.

To provide transactional properties while preserving the chain communication pattern, CrossStitch introduces a pipelined commit protocol that executes in parallel with the transaction and does not require any centralized co-ordination. Our evaluation results show that CrossStitch can reduce the latency of geo-distributed transactions when compared to a traditional 2PC-based distributed transaction system. We demonstrate that CrossStitch can reduce the number of round trips by more than half for TPC-C-like transactions.

Tyler Szepesi, Benjamin Cassell, Bernard Wong, Tim Brecht, Xiaoyi Liu

Sajjad Rizvi, Xi Li, Bernard Wong, Xiao Cao, and Benjamin Cassell

The increasing prevalence of oversubscribed networks and fast solid-state storage devices in the datacenter has made the network the new performance bottleneck for many distributed filesystems. As a result, distributed filesystems need to be network-aware in order to make more effective use of available network resources.

In this paper, we introduce Mayflower, a new distributed filesystem that is not only network-aware, it is co-designed from the ground up to work together with a network control plane. In addition to the standard distributed filesystem components, Mayflower has a flow monitor and manager running inside a software-defined networking controller. This tight coupling with the network controller enables Mayflower to make intelligent replica selection and flow scheduling decisions based on both filesystem and network information. It also enables Mayflower to perform global optimizations that are unavailable to conventional distributed filesystems and network control planes. Our evaluation results from both simulations and a prototype implementation show that Mayflower reduces average read completion time by more than 25% compared to current state-of-the-art distributed filesystems with an independent network flow scheduler, and more than 80% compared to HDFS with ECMP.

Tyler Szepesi, Bernard Wond, Fiodar Kazhami, Sajjad Rizvi, and Tim Brecht

A Modular Notation for Monitoring Network Systems

Prashant Raghav and Richard Tefler

Design of next generation network systems with predictable behaviour in all situations poses a significant challenge. Monitoring of events happening at different points in a distributed environment can detect the occurrence of events that indicates significant error conditions. We use Modular Timing Diagrams (MTD) as a specification language to describe these error conditions. MTDs are a component-oriented and compositional notation. We take advantage of these features of MTDs and point out that, in many cases, a global MTD specification describing behaviours  of several system components can be efficiently decomposed into a set of sub-specifications. Each of the sub-specifications describes a local monitor that is specific to the component on which the monitor is intended to run. We illustrate the compositional nature of MTDs in describing several network monitoring conditions related to network security.

Representing Behavioural Models with Rich Control Structures in SMT-LIB

Nancy A. Day and Amirhossein Vakili

We motivate and present a proposal for how to represent extended nite state machine behavioural models with rich hierarchical states and compositional control structures (e.g., the Statecharts family) in SMT-LIB. Our goal with such a representation is to facilitate automated deductive reasoning on such models, which can exploit the structure found in the control structures. We present a novel method that combines deep and shallow encoding techniques to describe models that have both rich control structures and rich datatypes. Our representation permits varying semantics to be chosen for the control structures recognizing the rich variety of semantics that exist for the family of extended nite state machine languages. We hope that discussion of these representation issues will facilitate model sharing for investigation of analysis techniques.

Representing Behavioural Models with Rich Control Structures in SMT-LIB (PDF)

Oleksii Kononenko and Olga Baysal

In a large, long-lived project,  an effective code review process is key to ensuring the long-term  quality  of the  code base.  In this  work, we study  code review practices  of a large, open source project,  and we investigate how the developers themselves  perceive code review quality.   We present a qualitative study  that summarizes  the  results  from a survey of 88 Mozilla core developers.  The results  provide developer insights into how they  define review quality,  what  factors  contribute to  how they  evaluate  submitted code,  and  what  challenges  they  face when  performing  review tasks.   We  found  that the  review quality  is primarily  associated  with  the  thoroughness of the  feedback,  the reviewer’s familiarity  with the code, and the perceived quality  of the code itself.  Also, we found that while different factors  are perceived to contribute to the review quality, reviewers often find it difficult to keep their technical skills up-to-date, manage personal priorities,  and mitigate context  switching.

Feedback-Directed Instrumentation for Deployed JavaScript Applications

Magnus Madsen, Frank Tip, Esben Andreasen, Koushik Sen, Anders Moller

Feedback-Directed Instrumentation for Deployed JavaScript Applications (PDF)

NoSE:  Schema Design for NoSQL Applications

Michael J. Mior, Kenneth Salem, Ashraf Aboulnaga

NoSE:  Schema Design for NoSQL Applications (PDF)

Comparison of Affect-Control Theoretic Agents and Humans in the Prisoner's Dilemma

Joshua D. A. Jung, Jesse Hoey, Jonathan H. Morgan, Tobias Schröder and IngoWolf

Comparison of Affect-Control Theoretic Agents and Humans in the Prisoner's Dilemma (PDF)

Big Open Data for Environmental Information
Systems

Donald Cowan, Paulo Alencar, Fred McGarry, R. MarkPalmer, Trevor Boston, Rigel Rozanski

Big Open Data for Environmental Information Systems (PDF)