A randomized memory model and its applications in distributed computing /
Randomization is a powerful tool in the design of algorithms. As summarized by Motwani and Raghavan, and by Gupta et al., randomized algorithms are often simpler and more efficient than deterministic algorithms for the same problem. Simpler algorithms have the advantages of being easier to analyze...
| Main Author: | |
|---|---|
| Format: | Thesis Book |
| Language: | English |
| Published: |
[Place of publication not identified] :
[publisher not identified] ;
2001.
|
| Subjects: | |
| Online Access: | http://proxy.library.tamu.edu/login?url=http://proquest.umi.com/pqdweb?did=726104521&sid=1&Fmt=2&clientId=2945&RQT=309&VName=PQD |
| Summary: | Randomization is a powerful tool in the design of algorithms. As summarized by Motwani and Raghavan, and by Gupta et al., randomized algorithms are often simpler and more efficient than deterministic algorithms for the same problem. Simpler algorithms have the advantages of being easier to analyze and implement. A well known example is the factoring problem, for which simple randomized polynomial-time algorithms are widely used, while no corresponding deterministic polynomial time algorithm is known. Randomized algorithms have a failure probability, which can typically be made arbitrarily small and which manifests itself either in the form of incorrect results (Monte Carlo algorithms) or in the form of unbounded running time (Las Vegas algorithms). In this dissertation, we propose a shared memory framework for distributed algorithms, in which the implementation of the shared memory can be randomized. In particular, read operations of read/write registers can return out-of-date values, and dequeue operations of queues can return out-of-order values with some small probability of lost values. We define new conditions, which constrain this error probability, such that interesting classes of popular algorithms will work correctly when implemented over such randomized data structures. At the same time, our conditions are sufficiently weak to allow certain kinds of probabilistic replicated systems to implement such memory. It is shown by Malkhi et al. that these replicated systems have very attractive properties, such as high scalability, availability and fault tolerance. As we will show, using this random memory model can result in improved load, availability in the face of server crashes, and message complexity, but seems to require a special style of programming. We consider two interesting classes of algorithms as applications for our randomized data structures: a class of iterative algorithms in the framework of Uresin and Dubois as an application for random registers and a class of randomized optimization algorithms by Aldous and Vazirani for random queues. Furthermore, we explore an application of our randomized data structures to mobile computing where a mobile computing entity can rely on some partial or out-of-date data to reconfigure its computing environment in response to physical movement. |
|---|---|
| Item Description: | Vita. "Major Subject: Computer Science". |
| Physical Description: | ix, 75 leaves : illustrations ; 28 cm. Issued also on microfiche from University Microfilm Inc. |
| Bibliography: | Includes bibliographical references (leaves 70-74). |