- talks - lists.cs.princeton.edu

Colloquium speaker Tim Roughgarden Wed Feb 8, 4:30pm
by Nicole E. Wagenblast 03 Feb '12

03 Feb '12

Porting the Computer Science Toolbox to Game Theory and Economics Tim Roughgarden , Stanford University Wednesday, February 8, 2012 , 4:30 PM - 5:30 PM Computer Science Small Auditorium (Room 105) Theoretical computer science has brought new ideas and techniques to game and economic theory. A primary signature of the computer science approach is {em approximation} --- the idea of building credibility for a proposed solution by proving that its performance is always within a small factor of an ideal (and typically unimplementable) solution. We explain two of our recent contributions in this area, one motivated by networks and one by auctions. We first discuss the "price of anarchy": how well does decentralized (or "selfish") behavior approximates centralized optimization? This concept has been analyzed in many applications, including network routing, resource allocation, network formation, health care, and even models of basketball. We highlight a new theory of robust price of anarchy bounds, which apply even to systems that are not in equilibrium. Second, we consider auction design: for example, what selling procedure should be used to maximize the revenue of a seller? On the analysis side, we highlight a new framework that explicitly connects average-case (i.e., Bayesian) analysis, the dominant paradigm in economics, with the worst-case analysis approach common in computer science. On the design side, we provide a distribution-independent auction that performs, for a wide class of input distributions, almost as well as the distribution-specific optimal auction. Tim Roughgarden received his Ph.D. from Cornell University in 2002 and joined the Stanford CS department in 2004, where he is currently an associate professor. His research interests are in theoretical computer science, especially its interfaces with game theory and networks. He wrote the book "Selfish Routing and the Price of Anarchy" (MIT Press, 2005) and co-edited the book "Algorithmic Game Theory", with Nisan, Tardos, and Vazirani (Cambridge, 2007). His significant awards include the 2002 ACM Doctoral Dissertation Award (Honorable Mention), the 2003 Tucker Prize, the 2003 INFORMS Optimization Prize for Young Researchers, speaking at the 2006 International Congress of Mathematicians, a 2007 PECASE Award, the 2008 Shapley Lectureship of the Game Theory Society, and the 2009 ACM Grace Murray Hopper Award. He's currently developing a free online course on the design and analysis of algorithms, which has over 50,000 students.

1 0

11am Tue Feb 7 talk on distributed streaming algorithms
by Jennifer Rexford 01 Feb '12

01 Feb '12

Speaker: Zhenming Liu, Harvard Title: Continuous Distributed Counting for Non-monotonic Streams Date/time: 11am-noon, Tuesday February 7 Location: room 302 in the CS building Abstract: 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. Bio: 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.

1 0

11am Wed Jan 18 talk on information-centric networking
by Jennifer Rexford 14 Jan '12

14 Jan '12

Speaker: Yan Shvartzshnaider, NICTA Title: A Case for a Global Information Network Date/time: 11am-noon Wed Jan 18 Location: CS 302 Abstract 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. Bio: 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.

1 0

S Narayana general exam
by Melissa M. Lawson 12 Jan '12

12 Jan '12

Srinivas Narayana will present his research seminar/general exam on Thursday Jan 19 at 10AM in Room 402. The members of his committee are: Jen Rexford (advisor), Mung Chiang, and Moses Charikar. Everyone is invited to attend his talk and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. ---------------------------- Abstract: The end-to-end performance of user-facing online services (e.g., Facebook, Amazon) is critical to their operation, as small increases in user-perceived latencies can have significant impact on revenue. Such services typically run out of a number of geographically distributed data centers, each connected by multiple ISPs to the Internet, and a geographically distributed set of mapping nodes directing user requests to data centers (e.g., based on proximity). Together, request-mapping (i.e., assigning user requests to data centers) and response-routing decisions (i.e., choosing an ISP to send responses) determine the wide-area paths traversed by user traffic--which are a significant contributor to end-to-end service latency. Yet in today's systems, request-mapping and response-routing decisions are made almost independently with coarse-grained, if any, coordination--due to concerns of administrative separation and operational scale. In this work, we investigate the benefits of coordinating request-mapping and response-routing decisions, through an optimization framework. We identify how suboptimal performance or costs can result if (1) the mapping and routing systems have incompatible objectives, or (2) if they are not sharing their decisions, and even if (3) mapping and routing systems have compatible objectives, share decisions, and optimize on top of each other. To overcome these difficulties, we show how to perform jointly optimized mapping and routing decisions while retaining their administrative separation. In particular, we construct a provably optimal distributed algorithm implemented through local computations at mapping nodes and data center edge routers, with a lightweight exchange of decisions. Evaluations of our solution using traffic traces from an operational content distribution network shows that our system converges quickly in practice, and offers much better performance and lower costs than today's solutions. and reading list: (1) The Design Philosophy of the DARPA Internet Protocols D. D. Clark (2) End-to-end arguments in system design J.H. Saltzer, D.P. Reed and D.D. Clark (3) DONAR: Decentralized server selection for cloud services P. Wendell, J. W. Jiang, M. J. Freedman, and J. Rexford (4) Characterizing roles of front-end servers in end-to-end performance of dynamic content distribution Y. Chen, S. Jain, V. K. Adhikari, and Z. L. Zhang (5) Optimizing cost and performance for multi-homing D. K. Goldenberg, L. Qiu, H. Xie, Y. R. Yang, and Y. Zhang (6) Optimizing cost and performance in online service provider networks Z. Zhang, M. Zhang, A. Greenberg, Y. C. Hu, R. Mahajan, and B. Christian (7) Cooperative content distribution and traffic engineering in an ISP network J. W. Jiang, R. Zhang-Shen, J. Rexford and M. Chiang (8) Traffic engineering vs. Content distribution: A game theoretic perspective D. DiPalantino and R. Johari (9) A Tutorial on Decomposition Methods for Network Utility Maximization D. P. Palomar and M. Chiang (10) Democratizing content publication with Coral M. J. Freedman, E. Freudenthal and D. Mazieres (11) iPlane: An information plane for distributed services H. V. Madhyastha, T. Isdal, M. Piatek, C. Dixon, T. Anderson, A. Krishnamurthy and A. Venkataramani (12) Computer networks: a systems approach Larry L. Peterson and Bruce S. Davie

1 0

J Dodds general exam
by Melissa M. Lawson 11 Jan '12

11 Jan '12

Joey Dodds will present his research seminar/general exam on Tuesday January 17 at 1PM in Room 402. The members of his committee are: Andrew Appel (advisor), David Walker, and Zeev Dvir. Everyone is invited to attend his talk and those faculty members wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. ------------------------------ Title: Machine-Checked Proofs of Conditional Information Flow Abstract: Previous work proposed a compositional framework for stating and automatically verifying complex conditional information flow policies using a relational Hoare logic. The framework allows developers and verifiers to work directly with the source code using source-level code contracts. In this work, we extend that approach so that the algorithm for verifying code compliance to an information flow contract emits formal certificates of correctness that are checked in the Coq proof assistant. This framework is implemented in the context of SPARK -- a subset of Ada that has been used in a number of industrial contexts for implementing certified safety and security critical systems. This work puts in place a crucial element of our larger vision for end-to-end security assurance -- namely, the ability to leverage a formally verified compiler to provide a tool chain that enables us to prove that deployed executable code conforms to complex information flow policies stated as source-level contracts. The Coq code consists of a definition for the core SPARK language, operational semantics for the language, definitions for the form of certificates, and soundness proofs of the certificates with respect to the operational semantics. We will discuss these definitions and proofs, along with the challenges of formalizing a paper proof. Certificates for analyses such as ours can often blow up to an unmanageable size. We have taken steps towards mitigating this contract explosion including beginning an implementation of the analysis in Coq. We can prove that evidence always exists, guaranteeing that any precondition generated by the function is correct with respect to the operational semantics of the language without requiring the transmission of a large contract. Text books: A. W. Appel. Modern Compiler Implementation in ML. Cambridge University Press, 1998 * B. Pierce. Types and Programming Languages. 2002. Papers * A. W. Appel. VeriSmall: Veriﬁed Smallfoot Shape Analysis. In First International Conf. on Certiﬁed Programs and Proofs Dec. 2011 * G. Necula. Proof-Carrying Code. In POPL'97: Proceedings of the 24th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 1997. * T. Amtoft, S. Bandhakavi, and A. Banerjee. A logic for information flow in object-oriented programs. In POPL 2006. ACM Press, 2006. * T. Amtoft, J. Hatcliff, and E. Rodrıguez. Precise and automated contract-based reasoning for verification and certification of information flow properties -of programs with arrays. In ESOP’10, volume 6012 of LNCS, pages 43–63, March 2010. * X. Leroy. A formally verified compiler back-end. In Journal of Automated Reasoning, 2009 * A. Sabelfeld, A. C. Myers. Language-Based Information-Flow Security. In IEEE Journal on Selected Areas in Communications, 2003 * Boettcher, C., DeLong, R., Rushby, J., and Sifre, W. 2008. The mils component integration approach to secure information sharing. In 27th IEEE/AIAA Digital Avionics Systems Conference 2008.

1 0

Y Wang general exam
by Melissa M. Lawson 06 Jan '12

06 Jan '12

Yida Wang will present his research seminar/general exam on Friday January 13 at 9:30AM in Room 302 (note room). The members of his committee are: Kai Li (advisor), Moses Charikar, and Nicholas Turk-Browne (Psychology, Neuroscience) . Everyone is invited to attend his talk, and those faculty members wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. ------------------------------- Computing and decoding brain full pairwise correlation matrices Human brain imaging such as Functional Magnetic Resonance Imaging (fMRI) has made transformational impacts on neuroscience. However, due to technology limitations in the past, researchers have constrained their analyses by making assumptions that are biased or false, leading to missed opportunities for science discovery, and in the worst case, incorrect inferences.Realizing that the processes in the brain may depend on widely distributed interactions among regions, we propose a novel method of analyzing the brain by its full correlation structure and show the effectiveness of the correlation analysis. The full correlation matrices lead to dramatic increase of data amount by at most extracting 7 orders of magnitude more information. With careful data computing, allocating and appropriate feature selection, we design a parallel tool to get the full correlation matrices in distribution and analyze them efficiently via classification to show the effectiveness of connectivity analysis. The critical voxels picked by our tool well match the existing theory of cognitive neuroscience in terms of location. And based on the selected voxels, experimental results demonstrate that the correlation based classification gets a comparable accuracy as traditional activation based classification within a subject, and is able to attain substantially higher accuracy than activation when analyzing across subjects, which, for the first time, shows the stability of brain correlation structures among different subjects. This work is advised by Prof. Moses Charikar and Prof. Kai Li at Princeton Computer Science Department, and Prof. Nicholas Turk-Browne and Prof. Jonathan Cohen at Princeton Neuroscience Institute. Reading List: Book: Modern Operating Systems, 3rd Edition, Andrew Tanenbaum. Computer Architecture: A Quantitative Approach, 4th Edition, John Hennessy and David Patterson. Paper: Goto, K. and Van De Geijn, R. 2008. Anatomy of high-performance matrix multiplication. ACM Trans. Math. Softw. 34, 3. J. Dean and S. Ghemawat. MapReduce: Simplified Data Processing on Large Clusters, Proc. 6th Symp. Operating System Design and Implementation (OSDI), Usenix Assoc., 2004, pp. 137-150. Matei Zaharia, Mosharaf Chowdhury, Tathagata Das, Ankur Dave, Justin Ma, Murphy McCauley, Michael Franklin, Scott Shenker, and Ion Stoica. Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing. Technical Report UCB/EECS-2011-82, EECS Department, University of California, Berkeley, Jul 2011. Pereira F, Mitchell T M and Botvinick M. Machine learning classifiers and fMRI: A tutorial overview Neuroimage. 2008 Norman, K. A., Polyn, S. M., Detre, G. J. and Haxby, J. V. Beyond mind-reading: multi-voxel pattern analysis of fMRI data. Trends Cogn. Sci. 10, 424-430 (2006). Jacob Y, Rapson A, Kafri M, Baruchi I, Hendler T, Jacob EB. Revealing voxel correlation cliques by functional holography analysis of fMRI. Journal of Neuroscience Methods 2010; 191: 126-137. Smith SM. Overview of fMRI analysis. The British Journal of Radiology, 77 (2004), 167-175. Kriegeskorte N, Goebel R, Bandettini P. Information-based functional brain mapping. Proceedings of the National Academy of Sciences 2006; 103(10): 3863-3868. Haxby JV, Guntupalli JS, Connolly AC, Halchenko YO, Conroy BR, Gobbini MI, Hanke M, Ramadge PJ. A Common, High-Dimensional Model of the Representational Space in Human Ventral Temporal Cortex. Neuron, 72(2), 2011.

1 0

J Deng preFPO
by Melissa M. Lawson 03 Jan '12

03 Jan '12

Jia Deng will present his preFPO on Monday January 9 at 1:30 PM in Room 402. The members of his committee are: Fei-Fei Li, advisor; Kai Li and Szymon Rusinkiewicz, readers; David Blei and Adam Finkelstein, nonreaders. Everyone is invited to attend his talk. His abstract follows below. ----------------- Title: Building the forest to see trees: toward large-scale visual recognition Abstract: Visual recognition is inherently a large-scale problem in that humans can recognize tens of thousands of categories. One of the goals of computer vision is to endow machines with this ability. In this talk, I will discuss recent advances toward recognition at this human scale. I will first talk about the acquisition and analysis of large-scale data, in particular, the construction of a large-scale visual ontology and an evaluation of state of the art recognition algorithms on more than 10,000 categories. Then I will present two recent works on large-scale machine learning. The first is on speeding-up training and testing to achieve sub-linear costs with respect to the number of categories. The second is about optimizing accuracy-specificity trade-offs to achieve reliable multi-level categorization. I will demonstrate that, by exploiting the structures among categories, our methods significantly improve the computational efficiency and reliability of recognition over previous work.

1 0

Jimin Song FPO
by Melissa M. Lawson 14 Dec '11

14 Dec '11

Jimin Song will present her FPO on Monday December 19 at 2PM in Room 402. The members of her committee are: Mona Singh, advisor; Olga Troyanskaya and Tom Funkhouser, readers; Bernard Chazelle and Andrea LaPaugh, nonreaders. A copy of her thesis, "Network-based analysis of protein function", is on display in Room 310. Everyone is invited to attend her talk.

1 0

W Kim preFPO
by Melissa M. Lawson 12 Dec '11

12 Dec '11

Wonho Kim will present his preFPO on Friday December 16 at 4PM in Room 402. The members of his committee are: Vivek Pai, advisor; Larry Peterson and Michael Freedman, readers; Jennifer Rexford and David Walker, nonreaders. Everyone is invited to attend his talk. His abstract follows below. ---------------------- Title: Understanding Resource Usage and Performance in Wide-area Distributed Systems Many Internet services employ wide-area frameworks to deliver exponentially growing network traffic to end-users with low response time. These systems typically leverage a large number of servers distributed to the edges of the Internet, which makes the systems difficult to design and manage. In this thesis, we examine resource usage and the performance of remote synchronization in wide-area systems. To support the development of new network services on a global scale, the next generation of federated testbeds are under active development, but very little is known about resource usage in the shared infrastructures. We conduct an extensive study of the usage profiles in PlanetLab that we collected for six years by running CoMon, a PlanetLab monitoring service. We examine various aspects of node-level behavior as well as experiment-centric behavior, and describe their implications for resource management in the federated testbeds. We find that the usage is much different from shared compute clusters, that conventional wisdom does not hold for PlanetLab, and that several properties of PlanetLab as a network testbed are largely responsible for this difference. We also present a latency-sensitive file synchronizer, Lsync, that can be used as synchronization building block for wide-are distributed systems where latency matters. While many distributed systems depend on fast data synchronization for coordinating remote nodes, current data dissemination systems focus on efficiency for open client populations, rather than focusing on completion latency for a known set of nodes. In examining this problem, we find that optimizing for latency produces strategies radically different from existing distribution tools, and can dramatically reduce latency across a wide range of scenarios. Lsync performs novel node selection, scheduling, and adaptive policy switching that dynamically chooses the best synchronization method using information available at runtime. Our evaluation results show that Lsync reduces latency by more than a factor of 14 compared to a widely used synchronization tool, and makes most remote nodes fully synchronized even under frequent file updates.

1 0

11am talk today on secure provenance in distributed systems in room 402
by Jennifer Rexford 12 Dec '11

12 Dec '11

Speaker: Wenchao Zhou, U. Penn Title: Secure Provenance in Distributed Systems Date/time: 11am-noon Monday December 12 Room: 402 Abstract: 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.

1 0