{ "metadata": { "name": "", "signature": "sha256:67dd71593aa7be832238de5f48750cd8a5240e367fd967059075c6dcadc7c61b" }, "nbformat": 3, "nbformat_minor": 0, "worksheets": [ { "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Analysis of Distributed Storage Systems w/ Continuous Time Markov Chains (CTMCs)\n", "\n", "\n", "## Introduction\n", "This lab will walk you through an interesting use of CTMCs in the analysis of data centers. The explosion of data on the internet resulted, naturally, in an explosion of data centers. Massive data centers of constantly failing nodes pose interesting challenges for us EECS ninjas. As a result, distributed storage is a very active area of research these days. Hope you enjoy!\n" ] }, { "cell_type": "code", "collapsed": false, "input": [ "#standard imports, and potentially useful functions\n", "from __future__ import division\n", "import random\n", "import numpy as np\n", "from numpy import zeros\n", "import matplotlib.pyplot as plt\n", "import scipy\n", "from numpy.linalg import svd, norm\n", "\n", "def nullspace(A, atol=1e-13, rtol=0):\n", " A = np.atleast_2d(A)\n", " u, s, vh = svd(A)\n", " tol = max(atol, rtol * s[0])\n", " nnz = (s >= tol).sum()\n", " ns = vh[nnz:].conj().T\n", " return ns\n", "\n", "def nSample(distribution, values, n):\n", " rand = [random.random() for i in range(n)]\n", " rand.sort()\n", " distribution = distribution.copy()\n", " samples = []\n", " samplePos, distPos, cdf = 0, 0, distribution[0]\n", " while samplePos < n:\n", " if rand[samplePos] < cdf:\n", " samplePos += 1\n", " samples.append(values[distPos])\n", " else:\n", " distPos += 1\n", " cdf += distribution[distPos]\n", " return samples\n", "\n", "%matplotlib inline" ], "language": "python", "metadata": {}, "outputs": [], "prompt_number": 2 }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Part 0: Reading\n", "If you haven't already, read Chapter 13.5 of Probability in EECS on CTMCs. The chapter is concise, so don't worry if you can't quite grasp everything on your first pass. This lab will walk you through everything you need to know about CTMCs, but the book will be a good place to start. You may also want to very briefly review Reed-Solomon erasure codes form CS 70. Hopefully this will be a nice review of last week's material :)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Part 1: CTMCs\n", "\n", "There are several differences between Continuous Time Markov Chains and their discrete time counterparts, but a good place to start is by thinking of a CTMC as a DTMC where the transitions between states can happen at any time, and that the transition times are exponentially \n", "distributed. We will explore this more thoroughly through the following example.\n", "\n", "