| 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 Call be randomized. In particular, read operations of read/write registers call return out-of-date values, and dequeue operations of queues call 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 call 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 Üresin 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 call rely oil some partial or out-of-date, data to reconfigure its, computing environment in response to physical movement. |
