טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
Ph.D Thesis
Ph.D StudentEyal Ittay
SubjectScalable and Robust Algorithms for Cloud Storage
and for Sensor Networks
DepartmentDepartment of Electrical Engineering
Supervisors Professor Emeritus Raphael Rom
Professor Idit Keidar
Full Thesis textFull thesis text - English Version


Abstract

Fast advancements in the production and construction of computer systems have led to the proliferation of highly distributed systems, at a scale that was unimaginable not many years ago. Our work addresses two types of such systems - sensor networks and cloud computing. We construct scalable and robust distributed algorithms for these environments, prove their correctness, and analyze their behavior through simulation.


To perform monitoring of large environments, we can expect to see in years to come sensor networks with thousands of light-weight nodes monitoring conditions like seismic activity, humidity or temperature. Each of these nodes is comprised of a sensor, a wireless communication module, a processing unit and storage. The nature of these widely-spread networks prohibits the collection of all data at a central location. Fortunately, often the raw data is not necessary. Rather, an aggregate that can be computed inside the network.


In the first part of this work, we address two aggregation challenges in the field of sensor networks. First, we present LiMoSense, a fault-tolerant live monitoring algorithm for dynamic sensor networks. This is the first asynchronous robust average aggregation algorithm that performs live monitoring. Second, we address the distributed clustering problem, where the computed aggregate is a clustering of the sensor data.


Advances in datacenter technologies have lead to extended use of data centers to store large volumes of data in a managed distributed system. The users of such systems have increasing expectations of both efficiency and reliability, leading to various challenges in implementing these data stores. In the second part of this work, we address two challenges relating to consistency in large scale cloud storage systems.


Key-value stores (KVSs) have become the most popular way to access Internet-scale "cloud'' storage systems. We observe that a single storage provider might fail, and present an efficient wait-free algorithm that provides reliable storage with a set of potentially faulty real-world production KVS services.


We then introduce a novel architecture for efficiently implementing transactions in a distributed data store called ACID-Rain: ACID transactions in a Resilient Archive with Independent Nodes. ACID-Rain uses logs in a novel way, limiting reliability to a single tier of the system. It avoids collisions between transactions by using prediction to order them before they take actions that would lead to an abort.