- talks - lists.cs.princeton.edu

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

11am-noon Mon Dec 12 talk on secure provenance in distributed systems
by Jennifer Rexford 08 Dec '11

08 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

Colloquium Speaker Celine Latulipe Mon Dec 5- 4:30pm
by Nicole E. Wagenblast 05 Dec '11

05 Dec '11

Expressive Interaction and the Evaluation of Creativity Support Celine Latulipe, University of North Carolina at Charlotte Monday, December 5, 2011, 4:30pm Computer Science Small Auditorium (Room 105) Visionaries in Computer Science have long seen the computer as a tool to augment our intellect. However, while it is relatively straightforward to measure the impact of a tool or technique on task efficiency for well-defined tasks, it is much more difficult to measure computers' impact on higher-level cognitive processes, such as creativity. In my own research in Human-Computer Interaction, I create novel interaction techniques, but run up against the problem of trying to evaluate how these tools impact higher-level processes such as creativity, expressiveness and exploration. In this talk, I briefly present a variety of interaction techniques that I have developed, and I then describe a new survey metric, the Creativity Support Index (CSI), that we have developed to help researchers and designers evaluate the level of creativity support provided by these types of systems, tools or interfaces. I will then present some current results using EEG and machine learning to classify the creative experience with more specific, temporal granularity. I present this work within the context of my longer term goal to develop a suite of tools that provide both stronger analytical power and a general framework for evaluating computational support for creative activities, engagement and aesthetic experience. Dr. Celine Latulipe has a PhD in Computer Science from the University of Waterloo in Canada. She is an Assistant Professor of Human-Computer Interaction in the Department of Software and Information Systems in the College of Computing and Informatics at UNC Charlotte. Dr. Latulipe has long been fascinated by two-handed interaction in the real world, and the absence of it in the human-computer interface. She has developed numerous individual and collaborative two-handed interaction techniques and these have blossomed into a more general exploration of creative expression. Dr. Latulipe works on projects with choreographers, dancers, artists and theatre producers to better understand creative work in practice and how technology may play a role in supporting and evaluating creative work practices. Currently, Dr. Latulipe is working on many projects, including the NSF CreativeIT-funded Dance.Draw project, which has received national media attention.

1 2

C Wang preFPO
by Melissa M. Lawson 30 Nov '11

30 Nov '11

Chong Wang will present his preFPO on Wednesday November 7 at 1PM in Room 302 (note room!). The members of his committee are: David Blei, advisor; Rob Schapire and Eric Xing (CMU), readers; Christiane Fellbaum and Andrea LaPaugh, readers. Everyone is invited to attend his talk. His abstract follows below. -------------------------- Title: Hierarchical Bayesian modeling: models and inference algorithms Hierarchical Bayesian models have become a popular tool for analyzing large-scale real-world data, such as text and images. Through these models, people can build useful tools for latent structure discovery, browsing and recommendations. In this talk, I will present several recent advances in the area of hierarchical Bayesian modeling, with an emphasis on topic modeling, Bayesian nonparametrics and approximate posterior inference. Specifically, I will talk about a novel model on recommending scientific articles that provides an interpretable latent structure for both users and items in a recommender system and then present an online variational inference algorithm that scales up to millions of articles on a single machine and also does model selection. Finally, I will summarize with some ongoing work.

1 1