Talk

Today, the network infrastructure of Internet Service Providers (ISPs) undergoes constant evolution. Whenever new requirements arise (e.g., the deployment of a new point-of-presence, or a change in the business relationships with a neighboring ISP), network operators need to modify the BGP configuration of their network. Due to the complexity of BGP, and the lack of methodologies and tools, maintaining service availability during reconfigurations that involve BGP is a challenge for network operators.

In this talk, we address the problem of deploying a new BGP configuration in a running ISP with no impact on the data-plane traffic. First, we show that the current best practices to reconfigure BGP (eBGP and iBGP) do not provide guarantees with respect to packet loss. In particular, we show that long-lasting routing and forwarding anomalies can occur even when the initial and the final BGP configurations are anomaly-free. Then, we study the problem of finding an operational ordering of the reconfiguration steps which guarantees no packet loss. Unfortunately, such an operational ordering, when it exists, is computationally hard to find. Finally, to enable disruption-free reconfigurations, we propose a framework which extends current carrier-grade routers to run two BGP control-planes in parallel. We present a prototype implementation and show its effectiveness through a case study.

According to a doctrine known as connectionism, brain function and dysfunction depend primarily on patterns of connectivity between neurons. Connectionism has been explored theoretically with mathematical models of neural networks since the 1940s. It has proved difficult to test these models through activity measurements alone. For conclusive empirical tests, information about neural connectivity is also necessary, and could be provided by new imaging methods based on serial electron microscopy. The bottleneck in using these new methods is now shifting to the data analysis problem of extracting neural connectivity from the images. New multibeam scanning electron microscopes will soon generate a petabyte of image data from a cubic millimeter of brain tissue every two weeks. From such images, it should be possible to map every connection between neurons in the volume---in principle. Unfortunately, it could take up to a million years for a single person to carry out this feat manually. Clearly, our capacity to acquire "big data" from the brain has far outpaced our ability to analyze it. My lab has been developing computational technologies to deal with this data deluge. These include image analysis by artificial intelligence (AI) based on machine learning, and methods of "crowdsourcing" image analysis to human intelligence. Our technologies have been implemented in eyewire.org, an online community that mobilizes laypersons to help map neural connections of the retina by interacting with AI.

Ten years ago, few software developers worked on distributed systems. Today, developers often run code on clusters, relying on large open-source software stacks to manage resources. These systems are challenging to configure and debug. Fortunately, developments in program analysis have given us new tools for managing the complexity of modern software. This talk will show how static analysis can help users configure their systems. I present a technique that builds an explicit table mapping a program's possible error messages to the options that might cause them. As a result, users can get immediate feedback on how to resolve configuration errors.

Ariel Rabkin is a fifth (and final)-year PhD candidate in the RAD Lab at UC Berkeley, working with Randy Katz. He is formerly from Cornell University, AB 2006, MEng 2007). He is interested in software quality and software intelligibility. He expects to graduate in May 2012. His dissertation is about applying program analysis to system management, including automatically describing program configuration options and diagnosing configuration errors. He is a contributor to several open source projects, including Hadoop, the Chukwa log collection framework, and the JChord program analysis toolset.

We consider the problem of tracking a sum of values in a distributed environment where the input values arrive from k distributed streams. It is required that an estimate of the sum is maintained by a coordinator node that is within a prescribed relative error tolerance, at any time with high probability. The goal is to achieve such objective with small total communication with the coordinator node, in order to minimize the use of network bandwidth that may be a scarce resource. This is a basic distributed computation problem that is of interest for various applications including data aggregation and iterative solving of various computational problems.

Specifically, we consider a setting where the input values are selected and assigned to sites by an adversary but the arrival order of the input items is random. We show a randomized protocol with a sub-linear total communication with respect to the number of updates and its matching lower bound. This result stands in between the previously known results that for monotonic partial sums (all value updates either positive or negative), the expected total communication is logarithmic in the number of updates, and that for general worst-case inputs, the total required communication is linear in the number of updates. Finally, we also discuss applications of the sum tracking module for tracking the second frequency moment and for solving a Bayesian linear regression.

Zhenmin Liu is a PhD candidate in the theory of computation group at Harvard, working with Michael Mitzenmacher. His research focuses on stochastic processes, optimization, and algorithm design, as well as their applications to distributed computation and big data analytics.

There is an ever increasing gap between how the “common man” would describe the Internet and how a network researcher would. This is not surprising, as the “packet with a label identifying the receiver” model seems to be an ill fitting abstraction for popular services provided by companies such as Google, Facebook, YouTube, or Twitter.

These services are primarily about information dissemination and a suitable network service abstraction should really do more than deliver individual packets with minimal latency. We argue that we should adopt an information-centric system model instead of the current service oriented one. Instead of dealing with information exchange between specific services on a case by case bases, we should instead consider a global information storage and dissemination network on which individual applications and services are built.

In this talk I will discuss our vision the future architecture and give a brief overview on our progress so far.

Yan Shvartzshnaider is a PhD Candidate in the school of Engineering and Information Technologies in the University of Sydney and a graduate researcher in National ICT Australia (NICTA), Networking Group in ATP lab. His research focus is on large scale networking systems, in particular, developing a fully distributed information-centric networking abstraction.

Operators of distributed systems often find themselves needing to answer forensic questions, to perform a variety of managerial tasks including fault detection, system debugging, accountability enforcement, and attack analysis. In this talk, we present Secure Provenance, a novel approach that provides the fundamental functionality required for answering such forensic questions -- the capability to "explain'' the existence (or change) of a certain distributed system state at a given time in a potentially adversarial environment.

We show that it is both possible and practical to efficiently and scalably maintain and query provenance in a distributed fashion, where provenance maintenance and querying are modeled as recursive continuous queries over distributed relations. We then propose enhancements to the provenance model that allow operators to reliably query provenance information in adversarial environments. Our extensions incorporate tamper-evident properties which provide the guarantee that operators can eventually detect the presence of compromised nodes that lie or falsely implicate correct nodes. Finally, we present ongoing efforts that consider privacy protection of sensitive information in provenance maintenance and querying, and discuss our work in the context of our longer term vision towards provably secure distributed systems.

Although there is a rich literature on methods for allowing the variance in a univariate regression model to vary with predictors, time and other factors, relatively little has been done in the multivariate case. A number of multivariate heteroscedastic time series models have been proposed within the econometrics literature, but are typically limited by lack of clear margins, computational intractability, and curse of dimensionality. In this talk, we first introduce and explore a new class of time series models for covariance matrices based on a constructive definition exploiting inverse Wishart distribution theory. The construction yields a stationary, first-order autoregressive (AR) process on the cone of positive semi-definite matrices.

We then turn our focus to more general predictor spaces and scaling to high-dimensional datasets. Our proposed Bayesian nonparametric covariance regression framework harnesses a latent factor model representation. In particular, the predictor-dependent factor loadings are characterized as a sparse combination of a collection of unknown dictionary functions (e.g, Gaussian process random functions). The induced predictor-dependent covariance is then a regularized quadratic function of these dictionary elements. Our proposed framework leads to a highly-flexible, but computationally tractable formulation with simple conjugate posterior updates that can readily handle missing data. Theoretical properties are discussed and the methods are illustrated through an application to the Google Flu Trends data and the task of word classification based on single-trial MEG data.

Joint work with David Dunson and Mike West.

To enable fast software development, Facebook has widely used the PHP programming language. Although easy to learn and quick to develop with, PHP is known for incurring significant performance penalty. To address this, the HipHop compiler team at Facebook has been working on multiple fronts. In this talk, I’ll first give an overview of the tools we have built and currently deploy in our production environment. After that, I’ll present the HipHop Virtual Machine, which is a new effort we’re pursuing to improve the performance of PHP via just-in-time (JIT) compilation techniques.

Dr. Guilherme Ottoni (*08) is currently a Software Engineer at Facebook, where he’s a member of the HipHop Compiler team. Before joining Facebook, Dr. Ottoni was a Staff Research Scientist at Intel Labs, where he lead a number of projects in the areas of dynamic binary translation, automatic parallelization, and microprocessor simulation. In a prior life, Dr. Ottoni co-organized the Brazilian Olympiad in Informatics and coached the Brazilian teams at several International Olympiads in Informatics. Dr. Ottoni received his B.S.E. from FURG, M.S. from UNICAMP, and Ph.D. from Princeton. He has published more than 30 papers and has several issued and pending patents.

RSVP at facebook.com/princetonphdtechtalk

Peer-assisted content distribution has become more prevalent in recent years to match the increase of high-quality media on the Internet. Peer-assisted systems promise to improve download performance and scalability by harnessing bandwidth at peers in addition to the resources of server-class hosts. However, existing systems are ill-suited for high-performance distribution: today's systems focus on distribution of only a single file, and are inefficient for distributing large content libraries.

In this talk I will introduce a new approach to content distribution that achieves high performance based on managed swarms. Managed swarms address download performance across multiple concurrent swarms by viewing content distribution as a global optimization problem. A logically centralized coordinator orchestrates downloads by measuring the behavior of swarms and calculating an efficient allocation of resources to achieve a global performance goal. I will discuss the role of the coordinator for managing swarms, then I will describe two new algorithms based on managed swarms that maximize system-wide throughput in realistic deployment scenarios. Extensive simulations and deployments show that managed swarms provide a scalable, efficient solution for distributing content libraries, and that they significantly outperform centralized distribution services and existing swarming protocols.

Ryan S. Peterson is completing his Ph.D. at Cornell University, where he has been working on content distribution under the advisement of Emin Gun Sirer. He has also worked on distributed systems for publish-subscribe, reliable storage, and content discovery. Prior to Cornell, Ryan earned a B.S.E. degree from Princeton University. Ryan is the 2009 recipient of the Google Fellowship in Distributed Systems, and he will be joining Google next month.

Mobility, in all of its forms, results in networks with varying degrees of connectivity. Providing communication services in such networks relies on solutions that treat these disconnections as an expected part of the system, instead of as an exception to be handled out of band. However, handling disconnectivity breaks most architectures for more stable and connected networks. Instead of a standard layered approach to communication services, communication in such intermittently connected networks depends on three key components: contacts, or knowing who we meet, context, knowing what is in our neighborhood, and content, knowing how to find and deliver data. In this talk, I will present some of our current research on support for communication in intermittently connected networks, vehicular networks and mobile social networks, as well as the target applications and deployment testbeds.

Robin Kravets is an Associate Professor at the University of Illinois at Urbana-Champaign and the head of the Mobius group at UIUC, which researches communication issues in all types of networks that are challenged by mobility, including wireless LANs, ad hoc networks, sensor network, delay and disruption tolerant networks, vehicular networks, mobile social networks and personal area networks. Her research focuses on solutions that enable effective power management, connectivity management, data transport, congestion management, location management, routing and security. For more information, visit http://mobius.cs.illinois.edu.