dedis@yale

Determinator an operating system for deterministic parallel computing

Background

Determinator is an experimental multiprocessor, distributed OS that creates an environment in which anything an application computes is exactly repeatable. It consists of a microkernel and a set of user-space runtime libraries and applications. The microkernel provides a minimal API and execution environment, supporting a hierarchy of “shared-nothing” address spaces that can execute in parallel, but enforcing the guarantee that these spaces evolve and interact deterministically. Atop this minimal environment, Determinator's user-space runtime library uses distributed systems techniques to emulate familiar shared-state abstractions such as Unix processes, global file systems, and shared memory multithreading.

A subset of Determinator comprises PIOS (“Parallel Instructional Operating System”), a teaching OS derived from and providing a course framework similar to JOS, where students fill in missing pieces of a reference skeleton. Determinator/PIOS represents a complete redesign and rewrite of the core components of JOS. To our knowledge PIOS is the first instructional OS to include and emphasize increasingly important parallel/multicore and distributed OS programming practices in an undergraduate-level OS course. It was used to teach CS422: Operating Systems at Yale in Spring 2010, and is freely available for use and adaptation by others.

Determinator will also provide a starting point for a certified OS kernel project in collaboration with the FLINT research group.

A multithreaded process built from one space per thread, with a master space managing synchronization and memory reconciliation
 

Conference Publications

Workshop Publications

  • Lazy Tree Mapping: Generalizing and Scaling Deterministic Parallelism, Yu Zhang and Bryan Ford. APSys '13, July 30, 2013. Abstract PDF
  • Icebergs in the Clouds: the Other Risks of Cloud Computing, Bryan Ford. HotCloud '12, June 12, 2012. Abstract PDF Slides: OpenOffice PDF
  • Plugging Side-Channel Leaks with Timing Information Flow Control, Bryan Ford. HotCloud '12, June 13, 2012. Abstract PDF Slides: OpenOffice PDF
  • A Virtual Memory Foundation for Scalable Deterministic Parallelism, Yu Zhang and Bryan Ford. APsys '11. Abstract PDF.
  • CertiKOS: A Certified Kernel for Secure Cloud Computing, Liang Gu, Alexander Vaynberg, Bryan Ford, Zhong Shao, and David Costanzo. APsys '11. Abstract PDF.
  • Deterministic OpenMP for Race-Free Parallelism, Amittai Aviram and Bryan Ford. HotPar '11. Abstract PDF. Slides: OpenOffice PDF.
  • Workspace Consistency: A Programming Model for Shared Memory Parallelism, Amittai Aviram, Bryan Ford, and Yu Zhang. WoDet '11. Abstract PDF.
  • Determinating Timing Channels in Compute Clouds, Amittai Aviram, Sen Hu, Bryan Ford, and Ramakrishna Gummadi. CCSW '10. Abstract, PDF PS. Slides: OpenOffice PDF.

Source Code on GitHub

Lectures

PhD Theses

Drafts and Technical Reports

  • Warding off timing attacks in Deterland, Weiyi Wu, Ennan Zhai, Daniel Jackowitz, David Isaac Wolinsky, Liang Gu, and Bryan Ford, April 2015. Preprint: Abstract PDF
  • Auditing the Structural Reliability of the Clouds, Ennan Zhai, David Isaac Wolinsky, Hongda Xiao, Hongqiang Liu, Xueyuan Su, and Bryan Ford. YALEU/DCS/TR-1479, July 2013. PDF
  • Determinating Mandelbrot: Adding Provider-Enforced Determinism to the Cloud, John Wood. Yale CS 490 project, May 2011. PDF (Yale-internal project page)
 

Acknowledgements

This research is sponsored by the National Science Foundation under grants CNS-1017206, CNS-1065451, and CNS-1149936, and by DARPA under CRASH award FA8750-10-2-0254. Our work has also used and benefitted from the testbed resources provided by Emulab and DETERlab.