UMI  
ProQuest® Dissertations & Theses
The world's most comprehensive collection of dissertations and theses. Learn more...
ProQuest  
 
 
Memory in media with manufacturing faults
by McCann, Mark A., PhD, PRINCETON UNIVERSITY, 2007, 0 pages; 3267417
 

Abstract: As computational systems scale to arbitrarily large sizes, and as they are expected to function reliably for arbitrary lengths of time, there are certain realities of the physical world that can not be ignored in the design and modeling of computational systems. For example, considerations for the delivery of power and removal of heat seem to limit the system to a two-dimensional surface. Additionally, it can be argued that all of the following restrictions are desirable and reasonable: there is a finite variety of components, no components (or external agents) are immune to failure, and components can communicate only with a bounded number of other components over a bounded distance. A very general model, with a reasonable ability to capture many of these features, is that of a cellular automaton. We extend the widely studied model of transient faults (which occur independently at different places and different times) in cellular automata to consider manufacturing faults (which occur independently at different places, but affect cells for all time). Although a well known monotone binary transition rule (known as Toom’s Rule) in two dimensions can remember a bit (that is, the system can be used to preserve a single Boolean value for all time with probability one) in the presence of transient faults, we show that no monotone binary transition rule in two dimensions can remember a bit when both manufacturing faults and transient faults are present. On the other hand, we give a monotone binary transition rule in three dimensions that can remember a bit in the presence of both manufacturing faults and transient faults. (By adding one or two further dimensions, one can reduce the problem of performing an arbitrary computation reliably to the problem of remembering a single bit.) We also study cellular automata that are based on hyperbolic (rather than Euclidean) tessellations (including infinite regular trees), and we completely classify the cases in which majority voting among all nearest neighbors can tolerate manufacturing faults and/or transient faults.

 
Advisor: NULL
School: PRINCETON UNIVERSITY
Source: DAI-B 68/06, p. 3906, Dec 2007
Source Type: PhD
Subjects: Computer science
Publication Number: 3267417
     
Adobe PDF Access the complete dissertation:
 

» Find an electronic copy at your library.
  Use the link below to access a full citation record of this graduate work:
  http://gateway.proquest.com/openurl%3furl_ver=Z39.88-2004%26res_dat=xri:pqdiss%26rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation%26rft_dat=xri:pqdiss:3267417
  If your library subscribes to the ProQuest Dissertations & Theses (PQDT) database, you may be entitled to a free electronic version of this graduate work. If not, you will have the option to purchase one, and access a 24 page preview for free (if available).

 
 
 

About ProQuest Dissertations & Theses
With over 2.3 million records, the ProQuest Dissertations & Theses (PQDT) database is the most comprehensive collection of dissertations and theses in the world. It is the database of record for graduate research.

The database includes citations of graduate works ranging from the first U.S. dissertation, accepted in 1861, to those accepted as recently as last semester. Of the 2.3 million graduate works included in the database, ProQuest offers more than 1.9 million in full text formats. Of those, over 860,000 are available in PDF format. More than 60,000 dissertations and theses are added to the database each year.

If you have questions, please feel free to visit the ProQuest Web site - http://www.il.proquest.com - or call ProQuest Hotline Customer Support at 1-800-521-3042.



Copyright © 2007 ProQuest. All rights reserved. Terms and Conditions

ProQuest