Thesis (M.S.)--University of Florida, 2001. / Title from first page of PDF file. Document formatted into pages; contains x, 75 p.; also contains graphics. Vita. Includes bibliographical references (p. 71-74).

Thesis (M. Phil.)--University of Hong Kong, 2001. / Includes bibliographical references (leaves 80-84).

The entire thesis text is included in the research.pdf file; the official abstract appears in the short.pdf file; a non-technical public abstract appears in the public.pdf file. Title from PDF of title page (University of Missouri--Columbia, viewed on January 19, 2010). Thesis advisor: Dr. Tina Smilkstein. Includes bibliographical references.

Thesis (Ph.D)--Electrical and Computer Engineering, Georgia Institute of Technology, 2010. / Committee Chair: Madisetti, Vijay; Committee Member: Jayant, Nikil; Committee Member: Lee, Chin-Hui; Committee Member: Ramachandran, Umakishore; Committee Member: Yalamanchili, Sudhakar. Part of the SMARTech Electronic Thesis and Dissertation Collection.

Includes bibliographical references (p. 39-41).

The paper \A Nearly Optimal Oracle for Avoiding Failed Vertices and Edges" by Aaron Bernstein and David Karger lays out a nearly optimal algorithm for nding the shortest distances and paths between vertices with any given single failure in constant time without reconstructing the oracle. Using their paper as a guideline, we have implemented their algorithm in C++ and recorded each step in this thesis. Each step has its own pseudo-code and its own analysis to prove that the entire oracle construction stays within the stated running time and total space bounds, from the authors. The effciency of the algorithm is compared against that of the brute-force methods total running time and total space needed. Using multiple test cases with an increasing number of vertices and edges, we have experimentally validated that their algorithm holds true to their statements of space, running time, and query time.

Distributed systems are rapidly increasing in importance due to the need for scalable computations on huge volumes of data. This fact is reflected in many real-world distributed applications such as Amazon's EC2 cloud computing service, Facebook's Cassandra key-value store or Apache's Hadoop MapReduce framework. Multi-core architectures developed by companies such as Intel and AMD have further brought this to prominence, since workloads can now be distributed across many individual cores. The nodes or entities in such systems are often built using commodity hardware and are prone to physical failures and security vulnerabilities. Achieving fault tolerance in such systems is a challenging task, since it is not easy to observe and control these distributed entities. Replication is a standard approach for fault tolerance in distributed systems. The main advantage of this approach is that the backups incur very little overhead in terms of the time taken for normal operation or recovery. However, replication is grossly wasteful in terms of the number of backups required for fault tolerance. The large number of backups has two major implications. First, the total space or memory required for fault tolerance is considerably high. Second, there is a significant cost of resources such as the power required to run the backup processes. Given the large number of distributed servers employed in real-world applications, it is a hard task to provide fault tolerance while achieving both space and operational efficiency. In the world of data fault tolerance and communication, coding theory is used as the space efficient alternate for replication. A direct application of coding theory to distributed servers, treating the servers as blocks of data, is very inefficient in terms of the updates to the backups. This is primarily because each update to the server will affect many blocks in memory, all of which have to be re-encoded at the backups. This leads us to the following thesis statement: Can we design a mechanism for fault tolerance in distributed systems that combines the space efficiency of coding theory with the low operational overhead of replication? We present a new paradigm to solve this problem, broadly referred to as fusion. We provide fusion-based solutions for two models of computation that are representative of a large class of applications: (i) Systems modeled as deterministic finite state machines and, (ii) Systems modeled as programs containing data structures. For finite state machines, we use the notion of Hamming distances to present a polynomial time algorithm to generate efficient backup state machines. For programs hosting data structures, we use a combination of erasure codes and selective replication to generate efficient backups for most commonly used data structures such as queues, array lists, linked lists, vectors and maps. We present theoretical and experimental results that demonstrate the efficiency of our schemes over replication. Finally, we use our schemes to design an efficient solution for fault tolerance in two real-world applications: Amazons Dynamo key-value store, and Google's MapReduce framework. / text

Not available / text

published_or_final_version / abstract / toc / Computer Science and Information Systems / Doctoral / Doctor of Philosophy

Θέμα της παρούσης διπλωματικής εργασίας αποτελεί η μελέτη, ανάπτυξη και πειραματική επιβεβαίωση αλγοριθμικών τεχνικών για την σχεδίαση αυτοοργανώμενων δομών δεδομένων (self-organizing data structures) και η ανάπτυξη τυχαιοποιημένων εκδόσεών τους. Μια αυτοοργανώμενη δομή δεδομένων διαθέτει κάποιον αλγόριθμο για να αναδιοργανώνει τους δείκτες και τα δεδομένα κατάστασης μετά από κάθε πρόσβαση ή πράξη . Ο αλγόριθμος αυτοοργάνωσης είναι σχεδιασμένος ώστε αντιδρώντας σε αρχικά άγνωστες ιδιότητες της ακολουθίας αιτήσεων (request sequence), να οδηγεί τη δομή δεδομένων σε κατάσταση πλεονεκτική για τις ιδιότητες της ακολουθίας με αποτέλεσμα τη μείωση του χρόνου που χρειάζεται στο μέλλον ανά πράξη. Ο πρώτος αλλά και ο μόνος μέχρι σήμερα πιθανός υποψήφιος αλγόριθμος αναζήτησης σε δένδρο που μπορεί να είναι Ο(1)-ανταγωνιστικός είναι το splay δένδρο (splay tree) που παρουσιάστηκε από τους Sleator και Tarjan [1]. Στην εργασία των Sleator και Tarjan παρουσιάζονται κάποιες εικασίες, οι οποίες δεν έχουν αποδειχθεί. Σημαντικότερη είναι η εικασία δυναμικής βελτιστότητας (dynamic optimality conjecture) σύμφωνα με την οποία το splay δένδρο είναι Ο(1)-ανταγωνιστικό. Η εικασία δυναμικής δακτυλοδότησης (dynamic finger conjecture) και η εικασία διαπέρασης (traversal conjecture) είναι αληθείς, αν είναι αληθής η εικασία δυναμικής βελτιστότητας. Ο Cole [3], [4] προσπάθησε να αποδείξει την ορθότητα της εικασίας δυναμικής δακτυλοδότησης σε μια από τις σημαντικότερες εργασίες για τα splay δένδρα. O J. Iacono [2] ανέπτυξε εναλλακτικές δομές δεδομένων που έχουν χρόνο χειρότερης περίπτωσης ανά πράξη (και όχι επιμερισμένο κόστος) της τάξης του Ο(logn), σε αντιδιαστολή με τον Ο(n) χρόνο χειρότερης περίπτωσης των splay trees. Σε αντιπαράθεση με τη δομή του Iacono, οι Mihai Badoiu και Erik D. Demaine παρουσίασαν μια δυναμική δομή αναζήτησης[7], η οποία επιτυγχάνει την ενοποιημένη ιδιότητα και που είναι απλούστερη από τη δομή του Iacono. Μεταξύ όλων των δυναμικών δομών αναζήτησης με βάση τις συγκρίσεις , η συγκεκριμένη δομή έχει τον καλύτερο χρόνο εκτέλεσης. Εκτός της παραπάνω δομής, ο Demaine ανέπτυξε ένα Ο(loglogn) ανταγωνιστικό online δυαδικό δέντρο αναζήτησης[5] , βελτιώνοντας το μέχρι πρότινος βέλτιστο ανταγωνιστικό ποσοστό της τάξης Ο(logn). Αυτή είναι η πρώτη μεγάλη βελτίωση της εικασίας δυναμικής βελτιστότητας (dynamic optimality conjecture) των Sleator και Tarjan , σύμφωνα με την οποία υπάρχουν Ο(1) ανταγωνιστικά δυαδικά δέντρα αναζήτησης. Σε σχέση με τη δυναμική βελτιστότητα των Splay trees, σημαντική συνεισφορά αποτελεί και η εργασία του George F. Georgakopoulos[6]. Ο George F. Georgakopoulos παρουσιάζει μια επέκταση της splay τεχνικής , την οποία ονομάζει chain-splay(αλυσιδωτό splay) . Τα chain-splay δέντρα εφαρμόζουν splay στο στοιχείο που προσπελαύνουμε προς τη ρίζα όπως ακριβώς γίνεται και στα κλασικά splay trees, αλλά εκτελούν και μερικές τοπικές splay πράξεις τακτοποίησης κάτω από το στοιχείο που προσπελάσαμε. Αποδεικνύεται πως η τεχνική chain–splay είναι Ο(loglogn) ανταγωνιστική σε σχέση με οποιοδήποτε offline αλγόριθμο αναζήτησης. Tέλος, ο George F. Georgakopoulos [9] έδωσε ένα νέο λήμμα επαναζύγισης για τα splay δέντρα και με βάση αυτό το λήμμα, αποδεικνύει πως τα splay δέντρα είναι ανταγωνιστικά προς κάθε κλάση δυναμικών ισοζυγισμένων δέντρων. Οι παραπάνω δομές θα μελετηθούν τόσο σε θεωρητικό όσο και σε πειραματικό επίπεδο με σκοπό την εξαγωγή χρήσιμων συμπερασμάτων σε σχέση με την αποδοτικότητά τους αλλά και με σκοπό την καταγραφή των ακόμη ανοικτών προβλημάτων και των προοπτικών επίλυσης τους. Επιπλέον, θα παρουσιαστούν τυχαιοποιημένες εκδόσεις των δομών των Demaine και Georgakopoulos. Οι δομές αυτές θα υλοποιηθούν και η απόδοσή τους θα τεκμηριωθεί τόσο πειραματικά όσο και θεωρητικά. Σημαντικής σημασίας είναι η σύγκρισή τους με τις αρχικές δομές, ώστε να εξαχθούν συμπεράσματα σχετικά με την συμβολή της τυχαιοποίησης στη βελτίωση της απόδοσης των δομών. / -