- talks - lists.cs.princeton.edu

Distinguished Colloquium Speaker Eva Tardos Monday Nov 19 4:30pm
by Nicole E. Wagenblast 19 Nov '12

19 Nov '12

How to Design Simple Efficient Mechanisms that are also Composable Eva Tardos , Cornell University Monday, November 19, 2012 , 4:30 PM - 5:30 P M Computer Science 105 E-commerce applications require simple, and well-designed systems, and systems that work well even if users participate in multiple mechanisms (and the value of each player overall is a complex function of their outcomes). Traditional mechanism design has considered such mechanisms only in isolation, and the mechanisms it proposes tend to be complex and impractical. In contrast, players typically participate in various mechanisms, mechanisms that are run by different principals (e.g. different sellers on eBay or different ad-exchange platforms) and coordinating them to run a single combined mechanism is infeasible or impractical. Even the simple and elegant Vickrey auction loses some of its appeal when not in isolation: when the overall value of each player is a complex function of their outcomes, the global mechanism is no longer truthful. In this talk we initiate the study of efficient mechanism design with guaranteed good properties even when players participate in multiple different mechanisms either simultaneously or sequentially. Over the last decade, computer scientists and game theorists have developed good understanding of the impact of strategic user behavior on system performance in environments that include selfish traffic routing, service location, and bandwidth sharing. We will consider simple mechanisms from this perspective. We define smooth mechanisms (that can be thought of as mechanisms that generate approximately market clearing prices), and show that smooth mechanisms are approximately efficient, and the efficiency guarantees for smooth mechanisms (when studied in isolation) carry over to the same or approximately the same guarantees for a market composed of such mechanisms. Joint work with Vasilis Syrgkanis. Eva Tardos is a Jacob Gould Schurman Professor of Computer Science at Cornell University, is Senior Associate Dean of Computing and Information Science, and was department chair 2006-2010. She received her PhD from Eotvos University in Budapest. She has been elected to the National Academy of Engineering and the American Academy of Arts and Sciences, and is the recipient of some fellowships and awards, including the Packard Fellowship, the Fulkerson Prize and the Dantzig prize. She was editor in chief of SIAM Journal of Computing 2003-09, and is editor of several other journals, including the Journal of the ACM, and Combinatorica. Her research interest is algorithms and algorithmic game theory, the subarea theory of designing systems and algorithms for selfish users.

1 2

Colloquium Speaker Ken Birman, Tues Nov. 13, 4:30pm
by Nicole E. Wagenblast 13 Nov '12

13 Nov '12

What are the Right Roles for Formal Methods in High Assurance Cloud Computing? Ken Birman , Cornell University Tuesday, November 13, 2012- 4:30pm Computer Science 105 The developer of a high assurance system must justify the fitness of the system for the intended use. In "small" scenarios, this problem is well understood: it entails rigorously specifying properties the system must achieve, designing protocols and correctness proofs, and then implementing and testing the needed code. In scaled-out settings, complex architectures are often unavoidable and this methodology can no longer be used. This talk focuses on how the resulting problems play out in the context of Isis2 (isis2.codeplex.com), a new system I've been building that supports a wide range of high-assurance properties for applications that will be hosted on cloud computing datacenters, and hence might need to run at very ambitious scale. We'll see that while it is possible to create systems of these kinds, existing formal methods are ill-suited to reasoning about the resulting solutions, suggesting that additional work will be needed to bridge between the mathematical and scientific foundations of high assurance of the kinds we teach in academic settings and the real-world instances of such problems that we may face in the near future. Ken Birman is the N. Rama Rao Professor of Computer Science at Cornell University, where he has headed a research effort in the area of high assurance distributed computing for thirty years. Ken is best known for inventing the virtual synchrony computing model and building the Isis Toolkit, which was ultimately used to build the system that operated the New York Stock Exchange for more than a decade, and the systems that continue to operate the French Air Traffic Control system and the US Navy AEGIS today. He also pioneered in the use of gossip protocols for system monitoring, management and control; several of his solutions are used today in the platforms that operate today's largest cloud computing infrastructures, notably at Amazon, IBM and Microsoft. A Fellow of the ACM since 1999, Ken won the 2009 IEEE Kanai Award for his research in distributed systems. He is currently developing online instructional materials for a short course on building high assurance cloud computing systems using his Isis2 platform.

1 2

Talk: Renata Teixeira, Broadband Internet Performance: A View From the Gateway, Mon Nov 12, 10am
by Nicole E. Wagenblast 12 Nov '12

12 Nov '12

Broadband Internet Performance: A View From the Gateway Renata Teixeira , University of Paris (LIP6) Monday, November 12, 2012, 10am Computer Science Room 402 Policymakers, ISPs, and users are increasingly interested in studying the performance of Internet access links. This talk will first present our findings on the the accuracy and overhead of state-of-the-art available bandwidth estimation tools to measure residential broadband throughput. Because of many confounding factors in a home network or on end hosts, however, thoroughly understanding access network performance requires deploying measurement infrastructure in users’ homes as gateway devices. This talk will then present the first study of network access link performance measured directly from home gateway devices. In conjunction with the Federal Communication Commission’s study of broadband Internet access in the United States, we study the throughput and latency of network access links using longitudinal measurements from nearly 4,000 gateway devices across 8 ISPs from a deployment of over 4,200 devices. We study the performance users achieve and how various factors ranging from the user’s choice of modem to the ISP’s traffic shaping policies can affect performance. Our study yields many important findings about the characteristics of existing access networks. Our findings also provide insights into the ways that access network performance should be measured and presented to users, which can help inform ongoing broader efforts to benchmark the performance of access networks. The work presented in this talk appeared at: -O. Goga, R. Teixeira, "Speed Measurements of Residential Internet Access", in Proc. of Passive and Active Measurement Conference, March 2012. -S. Sundaresan, W. de Donato, N. Feamster, R. Teixeira, S. Crawford, and A. Pescape, "Broadband Internet Performance: A View From the Gateway", in Proc. of ACM SIGCOMM, August 2011. Renata Teixeira received the B.Sc. degree in computer science and the M.Sc. degree in electrical engineering from Universidade Federal do Rio de Janeiro, Brazil, in 1997 and 1999, respectively, and the Ph.D. degree in computer science from the University of California, San Diego, in 2005. During her Ph.D. studies, she worked on Internet routing at the AT&T Research. She is currently a researcher with the Centre National de la Recherche Scientifique (CNRS) at LIP6, UPMC Sorbonne Universites, Paris, France. She was a visiting scholar at UC Berkeyley/ICSI. Her research interests are in measurement, analysis, and management of data networks. She has authored more than 40 papers in this area. Renata serves in the editorial board of the IEEE/ACM Transactions on Networking and of the ACM SIGCOMM Computer Communication Review. She is also a member of the steering committee of the ACM Internet Measurement Conference and has been active in the program committees of ACM SIGCOMM, ACM IMC, PAM, IEEE INFOCOM, among others.

2 1

Colloquium speaker Molly Steenson, Wednesday Nov, 7 at 4:30pm
by Nicole E. Wagenblast 07 Nov '12

07 Nov '12

"To the first machine that can appreciate the gesture:" Nicholas Negroponte and the MIT Architecture Machine Group Molly Steenson , Assistant Professor, School of Journalism & Mass Communication, University of Wisconsin-Madison PhD Wednesday, November 7, 2012 , 4:30pm Computer Science Small Auditorium (Room 105) Nicholas Negroponte today is best known for founding the MIT Media Lab in 1985. But before the Media Lab, he founded the Architecture Machine Group at MIT in 1968 (Arch Mach for short). As an architect captivated by computers, Negroponte created the lab as a test bed for interactive computers, sensors and programs that sought to change the manner in which computers and humans interacted with each other. He envisioned a world in which everybody would live in immersive, intelligent environments, even dedicating his first book The Architecture Machine “To the first machine that can appreciate the gesture." But what is the nature of that gesture? Arch Mach's structure and funding benefited from the same relationships as MIT’s major engineering and computing labs, collaborating especially closely with the Artificial Intelligence Lab, and its projects echoed the dynamics of Department of Defense funding that occurred in AI. In this talk, I will introduce Arch Mach's projects, projections—and gestures. Molly Wright Steenson is a Ph.D. candidate in Princeton University’s School of Architecture where she researches the history of architecture and information. In January 2013, she will join the faculty of the University of Wisconsin-Madison in the School of Journalism & Mass Communication, where she will focus on digital media studies. Steenson was also a professor at the Interaction Design Institute Ivrea in Italy. As a design researcher, she examines the effect of personal technology on its users, with recent projects in India and China for Microsoft Research and Intel Research and ReD Asscoiates. Prior to her scholarly career, Molly started working with the Web in 1994, producing sites and leading design strategy for Reuters, Netscape, and Razorfish. She holds a Master’s in Environmental Design from the Yale School of Architecture and a B.A. in German from the University of Wisconsin-Madison.

1 1

H Kim preFPO
by Melissa M. Lawson 06 Nov '12

06 Nov '12

Hanjun Kim will present his preFPO on Tuesday November 13 at 8:30 AM in Room 402. The members of his committee are: David August, advisor; David Wentzlaff and Kai Li, readers; JP Singh and Sharad Malik, nonreaders. Everyone is invited to attend his talk. His abstract follows below. ---------------------- ASAP: Automatic Speculative Acyclic Parallelization Speculative Decoupled Software Pipelining (Spec-DSWP) is a promising automatic parallelization technique that speculatively partitions a loop into multiple threads that communicate in a pipelined manner. Speculation can complement conservative static analysis, making automatic parallelization more robust and applicable. Pipelining allows Spec-DSWP to speculate only rarely occurring dependences while respecting the other dependences through communication among threads. Acyclic communication patterns in pipelining make the parallelized programs tolerant of communication latency. However, since Spec-DSWP partitions a loop iteration (a transaction) into multiple sub-transactions across multiple threads according to the pipeline stages, a special runtime system is required that supports multi-threaded transactions (MTX). This dissertation proposes Automatic Speculative Acyclic Parallelization (ASAP) that supports Spec-DSWP on real hardware without any hardware modiﬁcation. ASAP consists of a speculative acyclic parallelizing compiler and an MTX runtime system. The ASAP compiler automatically parallelizes loops using the Spec-DSWP transformation, and the ASAP runtime system correctly executes the speculatively transformed programs. With synergistic combination of speculation, acyclic communication, and runtime system support, ASAP achieves scalable performance for a wide range of applications on various parallel platforms such as multicore machines and clusters without any hardware modiﬁcation.

1 0

Colloquium speaker Michael Walfish Friday, Oct 26
by Nicole E. Wagenblast 26 Oct '12

26 Oct '12

Making proof-based verified computation almost practical Michael Walfish , The University of Texas at Austin Computer Science Small Auditorium, Room 105 Friday, October 26, 2012, 3:30pm How can a machine specify a computation to another one and then, without executing the computation, check that the other machine carried it out correctly? And how can this be done without assumptions about the performer (replication, trusted hardware, etc.) or restrictions on the computation? This is the problem of _verified computation_, and it is motivated by the cloud and other third-party computing models. It has long been known that (1) this problem can be solved in theory using probabilistically checkable proofs (PCPs) coupled with cryptographic tools, and (2) the performance of these solutions is wildly impractical (trillions of CPU-years or more to verify simple computations). I will describe a project at UT Austin that challenges the second piece of this folklore. We have developed an interactive protocol that begins with an efficient argument [IKO CCC '07] and incorporates new theoretical work to improve performance by 20+ orders of magnitude. In addition, we have broadened the computational model from Boolean circuits to a general-purpose model. We have fully implemented the system, accelerated it with GPUs, and developed a compiler that transforms computations expressed in a high-level language to executables that implement the protocol entities. The resulting system, while not quite ready for the big leagues, is close enough to practicality to suggest that in the near future, PCPs could be a real tool for building actual systems. Talk will be based on these papers and ongoing work: * http://www.cs.utexas.edu/~mwalfish/papers/ginger-usec12.pdf * http://www.cs.utexas.edu/~mwalfish/papers/pepper-ndss12.pd Michael Walfish is an assistant professor in the Computer Science Department at The University of Texas at Austin. His research interests are in systems, security, and networking. His honors include an Air Force Young Investigator Award, an NSF CAREER Award, a Sloan Research Fellowship, a Teaching Excellence Award from the UT College of Natural Sciences, the Intel Early Career Faculty Honor Program, and the UT Society for Teaching Excellence. He received his B.A. from Harvard and his Ph.D. from MIT, both in Computer Science.

1 2

Talk- Theodore Johnson of ATT Labs Wed. Oct 24
by Nicole E. Wagenblast 19 Oct '12

19 Oct '12

Hi all, Theodore Johnson will be visiting the department from ATT Labs on Wednesday, October 24. He'll be giving a talk about Data Stream Warehousing. The talk will be 12 noon to 1:30 pm, in Room 302. Abstract: Data stream processing is a well-studied area that has led to many commercial offerings. Stream processing systems typically store only a small history of a stream, and provide services such as real-time alerting and visualization, and data reduction for downstream processing. However many applications also require that long term (e.g. 2 year) histories as well as real-time data be provided to analysts. A stream warehouse combines aspects of data stream processing (continual data ingest) with data warehousing (long-term storage and materialized views). I will discuss special issues and opportunities that arise in stream warehousing, and stream warehouse applications within AT&T Labs - Research. Bio: Theodore Johnson received a PhD in Computer Science from New York University in 1990. From 1990 through 1996, he was an Associate Professor at the CISE department of the University of Florida. In 1996, Ted moved to the Database Research group of AT&T Labs - Research and has been there since. Ted has specialized in data steam management systems, being one of the principal authors of the GS Tool (previously, Gigascope) and of the DataDepot stream warehouse. Ted has written two books, Distributed Operating Systems and Algorithms (with Randy Chow) and Exploratory Data Mining and Data Cleaning (with Tamraparni Dasu). -- Ari Rabkin asrabkin(a)gmail.com Princeton Computer Science Department

1 0

CS Colloquia on making PCP practical: Friday 10/26 @ 3:30pm
by Mike Freedman 19 Oct '12

19 Oct '12

[Mike is a systems researcher who, along with students, has been working on this problem with Andrew Blumberg. Andrew is a mathematician who spent 2007-2008 at IAS. So, this talk might be interesting to some folks on varying backgrounds.] --- Making proof-based verified computation almost practical Michael Walfish, The University of Texas at Austin Friday, October 26, 2012, 3:30 PM - 4:30 PM CS Small Auditorium (Room 105) --- How can a machine specify a computation to another one and then, without executing the computation, check that the other machine carried it out correctly? And how can this be done without assumptions about the performer (replication, trusted hardware, etc.) or restrictions on the computation? This is the problem of _verified computation_, and it is motivated by the cloud and other third-party computing models. It has long been known that (1) this problem can be solved in theory using probabilistically checkable proofs (PCPs) coupled with cryptographic tools, and (2) the performance of these solutions is wildly impractical (trillions of CPU-years or more to verify simple computations). I will describe a project at UT Austin that challenges the second piece of this folklore. We have developed an interactive protocol that begins with an efficient argument [IKO CCC '07] and incorporates new theoretical work to improve performance by 20+ orders of magnitude. In addition, we have broadened the computational model from Boolean circuits to a general-purpose model. We have fully implemented the system, accelerated it with GPUs, and developed a compiler that transforms computations expressed in a high-level language to executables that implement the protocol entities. The resulting system, while not quite ready for the big leagues, is close enough to practicality to suggest that in the near future, PCPs could be a real tool for building actual systems. Talk will be based on these papers and ongoing work: http://www.cs.utexas.edu/~mwalfish/papers/ginger-usec12.pdf http://www.cs.utexas.edu/~mwalfish/papers/pepper-ndss12.pd --- Michael Walfish is an assistant professor in the Computer Science Department at The University of Texas at Austin. His research interests are in systems, security, and networking. His honors include an Air Force Young Investigator Award, an NSF CAREER Award, a Sloan Research Fellowship, a Teaching Excellence Award from the UT College of Natural Sciences, the Intel Early Career Faculty Honor Program, and the UT Society for Teaching Excellence. He received his B.A. from Harvard and his Ph.D. from MIT, both in Computer Science.

1 0

M Wawrzoniak preFPO
by Melissa M. Lawson 17 Oct '12

17 Oct '12

Michael Wawrzoniak will present his preFPO on Wednesday October 24 at 10AM in Room 402. The members of his committee are: Larry Peterson, advisor; David Blei, Andrea LaPaugh, Vivek Pai, and Rob Schapire. Everyone is invited to attend his talk. His abstract follows below. ---- The role played by data analysis and machine learning continues to gain significance in many fields, and society as a whole. In particular, statistical learning in the framework of graphical models has become a very successful and popular machine learning method used in many fields. However developing these models requires substantial expertise and applying them to very large distributed and streaming data sets can still be a very challenging problem. In this talk I will propose an architecture which will make a substantial subset of these techniques accessible to users with less expert machine learning knowledge. A framework for high-level description of models in conjugate-exponential family, automatically transforming them to distributed streaming stochastic variational inference procedure, and an evaluation platform will be outlined. The vision of this software stack is to show a possible future path for a shift from data analysis being in the hands the expert elites towards empowering the wider public. ----

1 0

S Sevinc preFPO
by Melissa M. Lawson 15 Oct '12

15 Oct '12

Soner Sevinc will present his preFPO on Monday October 22 at 8:30 AM in Room 402. The members of his committee are: Larry Peterson (advisor), Jennifer Rexford and Andy Bavier, readers; Michael Freedman and David Walker, nonreaders. Everyone is invited to attend his talk. His abstract follows below. -------------------- "Federation Framework Discovering and authorizing resources dispersed across autonomous organizations is a challenge for federations as they scale in number of participant organizations. We first give an analysis of some of today's federations in terms of trust models and argue that complex trust models, that entail indirect trust relations, can be one way to scale federations in the future. We introduce our federation framework, which can be used to realize access control and resource discovery in federations with arbitrary complex trust models. This framework synthesizes three area of previous work; trust management systems, policy languages and resource discovery systems. CERTDIST trust management system performs access control using digital certificates for proof construction. Different from its counterparts such as ABAC or SD3, it can construct proofs for more complex trust relations, by utilizing a DHT to perform key based certificate lookup. In addition, CERTDIST's programmable credentials allow dynamic policies be expressed as digital certificates. Federation Policy Language, FPL, is used to express security and resource allocation policies in federation. FPL primitives interface to underlying CERTDIST functionality, which are used by security architects and resource providers to write policies easily. Our contract based discovery and allocation system, CODAL, performs policy-driven peer discovery and collaborative resource discovery/allocation to address two problems: (1) participants in a federation can be unknown, and (2) their resource information and policies can be private. We evaluate our design in PlanetLab, emulating a realistic federation based on PlanetLab usage logs. Results show that our system is capable of discovering and allocating resources in a large scale federation, fulfilling a request from tens of organizations. We also show allocation policies are successfully enforced by our language, and explore run-time characteristics of the FPL proof construction process, and investigate certificate retrieval in terms of time and incurred system load."

1 0