Pervasive Computing Research at Michigan

People

	Mona Attariyan		Jason Flinn
	Brett Higgins		Kaushik Veeraraghavan

Former members

• Manish Anand, graduated 2007, Nokia Research
• Ed Nightingale, graduated 2007, Microsoft Research
• Ya-Yunn Su, graduated 2008, NEC Labs, America
• Dan Peek, graduated 2009, Facebook
• Puspesh Kumar (Summer 2006: Sprockets/BlueFS)

  Current Projects

  To see a list of the publications below sorted by date, click here.

  Respec: Operating System Support for Deterministic Multiprocessor Replay

  Overview

  This joint project with Peter Chen and Satish Naryanasamy aims to develop new tools and methodologies to help write more secure and reliable concurrent programs for multicore and manycore machines. Our intitial research efforts have focused on deterministic replay, which records and reproduces the execution of a hardware or software system. While it is well known how to replay uniprocessor systems, replaying shared memory multiprocessor systems at low overhead on commodity hardware is still an open problem. Respec targets {\em online} replay in which the recorded and replayed processes execute concurrently. Respec uses two strategies to reduce overhead while still ensuring correctness: speculative logging and externally deterministic replay. Speculative logging optimistically logs less information about shared memory dependencies than is needed to guarantee deterministic replay, then recovers and retries if the replayed process diverges from the recorded process. Externally deterministic replay relaxes the degree to which the two executions must match by requiring only their system output and final program states match.

  Respec: Efficient Online Multiprocessor Replay via Speculation and External Determinism
  Dongyoon Lee, Benjamin Wester, Kaushik Veeraraghavan, Satish Narayanasamy, Peter M. Chen, and Jason Flinn
  to appear in the Proceedings of the Fifteenth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), Pittsbugh, PA, March 2010.
  Abstract, PDF.

  Speculator: Generic support for speculative execution in the Linux kernel

  Overview

  Speculator provides Linux kernel support for speculative execution. It allows multiple processes to share speculative state by tracking causal dependencies propagated through inter-process communication. It guarantees correct execution by preventing speculative processes from externalizing output, e.g., sending a network message or writing to the screen, until the speculations on which that output depends have proven to be correct.

  Speculator improves the performance of distributed file systems by masking I/O latency and increasing I/O throughput. Rather than block during a remote operation, a file system predicts the operation's result, then uses Speculator to checkpoint the state of the calling process and speculatively continue its execution based on the predicted result. If the prediction is correct, the checkpoint is discarded; if it is incorrect, the calling process is restored to the checkpoint, and the operation is retried. We have modified the client, server, and network protocol of two distributed file systems to use Speculator. For PostMark and Andrew-style benchmarks, speculative execution results in a factor of 2 performance improvement for NFS over local-area networks and an order of magnitude improvement over wide-area networks. For the same benchmarks, Speculator enables the Blue File System (see below) to provide the consistency of single-copy file semantics and the safety of synchronous I/O, yet still outperform current distributed file systems with weaker consistency and safety.

  We have more recently applied the principles behind Speculator to provide guarantees equivalent to those provided by synchronous I/O on local file system. We are currently investigating the applicability of OS-level speculative execution to other domains, including configuration management, fault tolerance, and security.

  Publications

  Speculative Execution in a Distributed File System
  Edmund B. Nightingale, Peter M. Chen, and Jason Flinn
  Proceedings of the 20th ACM Symposium on Operating Systems Principles (SOSP), Brighton, United Kingdom, October 2005. Award paper.
  Abstract, Postscript, PDF, Talk slides.
  Note: the following revised version appeared in ACM Transactions on Computer Systems, Volume 24, Number 4, November 2006, PDF.

  Rethink the Sync
  Edmund B. Nightingale, Kaushik Veeraraghavan, Peter M. Chen, and Jason Flinn
  Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation (OSDI), Seattle, WA, November 2006. Best paper award.
  Abstract, Postscript, PDF, Talk slides.

  Parallelizing Security Checks on Commodity Hardware
  Edmund B. Nightingale, Daniel Peek, Peter M. Chen, and Jason Flinn
  Proceedings of the Thirteenth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), Seattle, WA, March 2008.
  Abstract, Postscript, PDF, talk slides.

  Rethink the Sync (extended version of OSDI '06 publication)
  Edmund B. Nightingale, Kaushik Veeraraghavan, Peter M. Chen, and Jason Flinn
  ACM Transactions on Computer Systems, Volume 26, Number 3, September 2008.
  Abstract, PDF.

  Tolerating latency in replicated state machines through client speculation
  Benjamin Wester, James Cowling, Edmund B. Nightingale, Peter M. Chen, Jason Flinn, and Barbara Liskov
  to appear in the Proceedings of the 6th USENIX Symposium on Network Systems Design and Implementation (NSDI), Boston, MA, April 2009.
  Abstract, Postscript, PDF.

  AutoBash: Tools for Automating Configuration Management

  AutoBash: Improving configuration management with operating system causality analysis
  Ya-Yunn Su, Mona Attariyan, and Jason Flinn
  Proceedings of the 21st ACM Symposium on Operating Systems Principles (SOSP), Stevenson, WA, October 2007.
  Abstract, Postscript, PDF.

  Using Causality to Diagnose Configuration Bugs
  Mona Attariyan and Jason Flinn
  Proceedings of the USENIX Annual Technical Conference, Boston, MA, June 2008.
  Abstract, Postscript, PDF.

  Automatically Generating Predicates and Solutions for Configuration Troubleshooting
  Ya-Yunn Su and Jason Flinn
  to appear in the Proceedings of the USENIX Annual Technical Conference, San Diego, CA, June 2009.
  Abstract, Postscript, PDF.

  BlueFS: A distributed file system for pervasive computing

  Overview

  BlueFS is a distributed storage solution that targets consumer electronics devices in the digital home. Our goal is to seamlessly link together all of a user's content (photos, music, documents, etc.) and all of their devices (computers, DVRs, cameras, MP3 players, and the like). BlueFS supports extensibility to allow users to inject type-specific functionality into the file-system itself to improve handling of new types of data and clients.

  Our work with BlueFS is also investigating how to build energy-efficient distributed file systems for pervasive computing. By making energy conservation a first-class design goal from the outset, we will enable pervasive computers to maintain connectivity without compromising battery lifetime. This will allow pervasive computing devices to be incorporated into everyday activities.

  Publications

  Energy-Efficiency and Storage Flexibility in the Blue File System
  Edmund B. Nightingale and Jason Flinn
  Proceedings of the 6th USENIX Symposium on Operating Systems Design and Implementation (OSDI), San Francisco, CA, December 2004.
  Abstract, Postscript, PDF, Talk slides.

  Drive-Thru: Fast, Accurate Evaluation of Storage Power Management
  Daniel Peek and Jason Flinn
  Proceedings of the USENIX Annual Technical Conference, Anaheim, CA, April 2005.
  Abstract, Postscript, PDF, Talk slides.

  EnsemBlue: Integrating Distributed Storage and Consumer Electronics
  Daniel Peek and Jason Flinn
  Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation (OSDI), Seattle, WA, November 2006,
  Abstract, Postscript, PDF, Talk slides.

  Cobalt: Separating content distribution from authorization in distributed file systems
  Kaushik Veeraraghavan, Andrew Myrick, and Jason Flinn
  Proceedings of the 5th USENIX Conference on File and Storage Technologies (FAST), San Jose, CA, February 2007.
  Abstract, Postscript, PDF, Talk slides.

  Consumer Electronics Meets Distributed Storage
  Daniel Peek and Jason Flinn
  IEEE Computer, Vol. 40, No. 2, Invisible Computing Column, February 2007.

  Sprockets: Safe extensions for distributed file systems
  Daniel Peek, Edmund B. Nightingale, Brett D. Higgins, Puspesh Kumar, and Jason Flinn
  Proceedings of the 2007 USENIX Annual Technical Conference Santa Clara, CA, June 2007.
  Abstract, Postscript, PDF.

  quFiles: a new abstraction for mobile data management
  Kaushik Veeraraghavan, Edmund B. Nightingale, Jason Flinn, and Brian D. Noble
  Proceedings of the Ninth Workshop on Mobile Computing Systems and Applications (HotMobile), Napa, CA, February 2008.
  Abstract, PDF, Talk slides.

  Trapper Keeper: Using Virtualization to Add Type-Awareness to File Systems
  Daniel Peek and Jason Flinn
  Technical Report CSE-TR-550-09, Computer Science and Engineering Division, University of Michigan, May 2009.
  Abstract, PDF.

  quFiles: The Right File at the Right Time
  Kaushik Veeraraghavan, Jason Flinn, Edmund B. Nightingale, and Brian Noble
  to appear in the Proceedings of the 8th USENIX Conference on File and Storage Technologies (FAST), San Jose, CA, February 2010.
  Abstract, PDF.

  Self-tuning power management

  Overview

  Current timeout-based power management strategies often substantially degrades performance and may even increase overall energy usage when used with latency-sensitive applications. We are developing self-tuning power management algorithms that adapt to the access patterns and intent of applications, the characteristics of individual hardware components, and the energy usage of the computing platform. Our preliminary work implementing self-tuning power management for wireless networks shows considerable promise: we are able to substantially improve upon the performance and energy conservation provided by current 802.11b power management strategies.

  Publications

  Self-Tuning Wireless Network Power Management
  Manish Anand, Edmund B. Nightingale, and Jason Flinn
  Proceedings of the 9th Annual International Conference on Mobile Computing and Networking (MOBICOM '03), San Diego, CA, September 2003.
  Abstract, Postscript, PDF, Talk slides.

  Self-Tuning Wireless Network Power Management (extended version of MOBICOM '03 publication)
  Manish Anand, Edmund B. Nightingale, and Jason Flinn
  Wireless Networks, Vol. 11, No. 4, July 2005.
  Abstract, Postscript, PDF.

  Ghosts in the Machine: Interfaces for Better Power Management
  Manish Anand, Edmund B. Nightingale, and Jason Flinn
  Proceedings of the 2nd Annual International Conference on Mobile Systems, Applications, and Services (MobiSys '04), Boston, MA, June 2004. Best paper award.
  Abstract, Postscript, PDF, Talk slides.

  PAN-on-Demand: Building Self-Organizing PANs for Better Power Management
  Manish Anand and Jason Flinn
  Technical Report CSE-TR-524-06, Computer Science and Engineering Division, University of Michigan.
  Abstract, Postscript, PDF.

  PAN-on-Demand: Leveraging Multiple Radios to Build Self-Organizing Energy-Efficient PANs
  Manish Anand and Jason Flinn
  to appear in the Proceedings of the Fifth Annual International Conference on Mobile and Ubiquitous Systems: Computing, Networking, and Services, Dublin, Ireland, July 2008 (this is an improved version of the tech report above).
  Abstract, PDF.

  Slingshot: support for mobile services

  It is extremely difficult to execute demanding applications in pervasive computing environments. Size and weight restrictions make mobile clients resource-poor; they have less powerful processors, less storage capacity, and poorer network connectivity than corresponding desktop and server devices. Often, their resource capacity is insufficient to run demanding, interactive applications such as speech recognition, language translation, and augmented reality. Remote execution offers a solution: clients can partition such applications and execute the most demanding portions on remote servers located in the fixed infrastructure. This allows applications to simultaneously benefit from the mobility of small devices and the greater processing power of larger, fixed devices.

  We are building a system, called Slingshot, that dynamically discovers servers in the pervasive infrastructure and opportunistically uses them to augment the capacities of resource-impoverished clients. Slingshot monitors the resources offered by servers and estimates application needs. It then dynamically partitions applications running on a client and executes components remotely to achieve better performance, superior quality, and reduced usage of battery energy. Slingshot supports latency-sensitive applications that require sub-second response time by migrating server components to follow the movement of mobiler clients.

  Slingshot: Deploying Stateful Services in Wireless Hotspots
  Ya-Yunn Su and Jason Flinn
  Proceedings of the 3rd Annual Conference on Mobile Systems, Applications, and Services (MobiSys '05), Seattle, WA, June 2005.
  Abstract, Postscript, PDF, Talk slides.

  Portable Storage Support for Cyber Foraging
  Ya-Yunn Su and Jason Flinn
  Proceedings of the International Workshop on Software Support for Portable Storage, San Francisco, CA, March 2005.
  Abstract, Postscript, PDF.

  Other Publications

  Intentional networking

  The Case for Intentional Networking
  Jason Flinn, T. J. Giuli, Brett Higgins, Brian Noble, Azarias Reda, and David Watson
  Proceedings of the Tenth Workshop on Mobile Computing Systems and Applications (HotMobile), Santa Cruz, CA, February 2009.
  Abstract, Postscript, PDF,

  Mobile security

  In-Cloud Security Services for Mobile Devices
  Jon Oberheide, Kaushik Veraraghavan, Evan Cooke, Jason Flinn, and Farnam Jahanian
  to appear in the Proceedings of the First Workshop on Virtualization and Mobile Computing, Breckinridge, CO, June 2008.

  Data staging

  Data Staging on Untrusted Surrogates
  Jason Flinn, Shafeeq Sinnamohideen, Niraj Tolia, and M. Satyanarayanan
  Proceedings of the 2nd USENIX Conference on File and Storage Technology, San Francisco, CA, March/April 2003.
  Abstract, Postscript, PDF, Talk slides

  The Case for Cyber Foraging
  Rajesh Balan, Jason Flinn, M. Satyanarayanan, Shafeeq Sinnamohideen, and Hen-I Yang
  In the 10th ACM SIGOPS European Workshop, Saint-Emilion, France, September 2002.
  Abstract, Postscript, PDF

  Dynamic application partitioning in pervasive computing

  Balancing Performance, Energy, and Quality in Pervasive Computing
  Jason Flinn, SoYoung Park, and M. Satyanarayanan
  Proceedings of the 22nd International Conference on Distributed Computing Systems, Vienna, Austria, July 2002.
  Abstract, Postscript, PDF, Talk slides (.ppt.gz)

  Self-Tuned Remote Execution for Pervasive Computing
  Jason Flinn, Dushyanth, Narayanan, and M. Satyanarayanan
  Proceedings of the 8th Workshop on Hot Topics in Operating Systems (HotOS-VIII), Schloss Elmau, Germany, May 2001.
  Abstract, Postscript, PDF

  Reducing the energy usage of mobile computers

  Managing Battery Lifetime with Energy-Aware Adaptation
  Jason Flinn and M. Satyanarayanan
  ACM Transactions on Computer Systems (TOCS), Vol. 22, No. 2, May 2004.
  Abstract, PDF

  Extending Mobile Computer Battery Life through Energy-Aware Adaptation
  Jason Flinn
  Ph.D. dissertation, TR# CMU-CS-01-171, Carnegie Mellon University, December 2001.
  Abstract, Postscript, PDF, Talk slides (.ppt.gz)

  Reducing the Energy Usage of Office Applications
  Jason Flinn, Eyal de Lara, M. Satyanarayanan, Dan S. Wallach, and Willy Zwaenepoel
  Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms (Middleware 2001), Heidelberg, Germany, November 2001.
  Abstract, Postscript, PDF, Talk slides (.ppt)

  Using History to Improve Mobile Application Adaptation
  Dushyanth Narayanan, Jason Flinn, and M. Satyanarayanan
  Proceedings of the 3rd IEEE Workshop on Mobile Computing Systems and Applications, Monterey, CA, December 2000.
  Abstract, PDF

  Quantifying the Energy Consumption of a Pocket Computer and a Java Virtual Machine
  Keith I. Farkas, Jason Flinn, Godmar Back, Dirk Grunwald, and Jennifer Anderson
  Proceedings of the International Conference on Measurement and Modeling of Computer Systems (ACM SIGMETRICS), Santa Clara, CA, June 2000.
  Abstract, Postscript, PDF

  Power and Energy Characterization of the Itsy Pocket Computer (Version 1.5)
  Jason Flinn, Keith I. Farkas, and Jennifer Anderson
  Compaq Western Research Laboratory
  Technical Note TN-56, February 2000.
  Abstract, Postscript, PDF

  Energy-Aware Adaptation for Mobile Applications
  Jason Flinn and M. Satyanarayanan
  Proceedings of the 17th ACM Symposium on Operating Systems Principles (SOSP), Kiawah Island Resort, SC, December 1999.
  Abstract, Postscript, PDF, Talk slides (.ppt.gz)

  PowerScope: A Tool for Profiling the Energy Usage of Mobile Applications
  Jason Flinn and M. Satyanarayanan
  Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications, New Orleans, Louisiana, February 1999.
  Abstract, Postscript, PDF, Talk slides (old version of PowerPoint), Talk slides (pptx format)

  Application-aware adaptation

  Agile Application-Aware Adaptation for Mobility
  Brian D. Noble, M. Satyanarayanan, Dushyanth Narayanan, J. Eric Tilton, Jason Flinn, and Kevin R. Walker
  Proceedings of the 16th ACM Symposium on Operating Systems Principles (SOSP), Saint-Malo, France, October 1997.
  Abstract, Postscript, PDF

Miscellaneous topics

Visual Proxy: Exploiting OS Customizations without Application Source Code
M. Satyanarayanan, Jason Flinn, and Kevin R. Walker
Operating Systems Review, Volume 33, Number 3, July 1999.
Abstract, Postscript, PDF

Source Code

Version 1.1.1 of RPC3 - yet another RPC package.

Version 2.1.0 of BlueFS - a distributed file system that targets small, pervasive computers. This version includes support for persistent queries and partial support for consumer electronic devices. This version does not include any ensemble support, nor does it include full support for CEDs. Thus, it represents a stable but intermediate point between the OSDI 2004 and 2006 papers.

Version 1.0.0 of STPM - self-tuning power management for network and storage devices (includes ghost hints). This was the version we used for the OSDI 2004 paper. Works only on Linux 2.4 kernels.

A Linux 2.6 port of STPM provided by Cihan Kömeçoglu - cihan [at] enderunix.org.

We received several requests for the durability/ordering tests used in "Rethink the Sync" above. So here they are.

Source code for the data staging project is available on the Intel Research Pittsburgh web site. Data stating is released under a BSD-style license.

Source code for PowerScope is also available under a GPL.