Efficient Algorithms for Sorting and Synchronization

Author(s) : Andrew Tridgell
Pages : 115
Publication Date : Feb 1999

Thesis Abstract:

This is a thesis submitted by the author for the degree of Doctor of Philosophy at The Australian National University. This thesis presents efficient algorithms for internal and external parallel sorting and remote data update. The sorting algorithms approach the problem by concentrating first on highly efficient but incorrect algorithms followed by a cleanup phase that completes the sort.

The remote data update algorithm, rsync, operates by exchanging block signature information followed by a simple hash search algorithm for block matching at arbitrary byte boundaries. The last chapter of the thesis examines a number of related algorithms for text compression, differencing and incremental backup.

Contents:
1. Internal Parallel Sorting
2. External Parallel Sorting
3. The rsync algorithm
4. rsync enhancements and optimizations
5. Further applications for rsync
6. Conclusion

View/Download Efficient Algorithms for Sorting and Synchronization