CaltechAUTHORS
  A Caltech Library Service

The Robustness of Stochastic Switching Networks

Loh, Po-Ling and Zhou, Hongchao and Bruck, Jehoshua (2009) The Robustness of Stochastic Switching Networks. California Institute of Technology , Pasadena, CA. (Unpublished) http://resolver.caltech.edu/CaltechPARADISE:2009.ETR092

[img]
Preview
PDF (January, 2009 [revised 1 May 2009])
See Usage Policy.

163Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechPARADISE:2009.ETR092

Abstract

Many natural systems, including chemical and biological systems, can be modeled using stochastic switching circuits. These circuits consist of stochastic switches, called pswitches, which operate with a fixed probability of being open or closed. We study the effect caused by introducing an error of size ∈ to each pswitch in a stochastic circuit. We analyze two constructions – simple series-parallel and general series-parallel circuits – and prove that simple series-parallel circuits are robust to small error perturbations, while general series-parallel circuits are not. Specifically, the total error introduced by perturbations of size less than ∈ is bounded by a constant multiple of ∈ in a simple series-parallel circuit, independent of the size of the circuit. However, the same result does not hold in the case of more general series-parallel circuits. In the case of a general stochastic circuit, we prove that the overall error probability is bounded by a linear function of the number of pswitches.


Item Type:Report or Paper (Technical Report)
Additional Information:This work was supported in part by the NSF Expeditions in Computing Program under grant CCF-0832824. The authors would also like to thank the Caltech Summer Undergraduate Research Fellowship (SURF) program for its support in funding this research, and Dan Wilhelm for his comments and suggestions in revising the paper.
Group:Parallel and Distributed Systems Group
Record Number:CaltechPARADISE:2009.ETR092
Persistent URL:http://resolver.caltech.edu/CaltechPARADISE:2009.ETR092
Official Citation:Po-Ling Loh, Hongchao Zhou, and Jehoshua Bruck. The Robustness of Stochastic Switching Networks. Technical Report. California Institute of Technology, Pasadena, CA. [CaltechPARADISE:2009.ETR092]
Usage Policy:You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.
ID Code:26123
Collection:CaltechPARADISE
Deposited By: Imported from CaltechPARADISE
Deposited On:21 Sep 2009
Last Modified:26 Dec 2012 13:54

Repository Staff Only: item control page