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

  • 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.