Competitive analysis of distributed algorithms

1. K. Abrahamson. On achieving consensus using a shared memory. In Proceedings of the Seventh ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, pages 291–302, August 1988.

   Google Scholar 

2. M. Ajtai, J. Aspnes, C. Dwork, and O. Waarts. A theory of competitive analysis for distributed algorithms. In Proc. 35th Symp. of Foundations of Computer Science, pages 401–411, 1994.

   Google Scholar 

3. R. Anderson and H. Woll. Wait-free parallel algorithms for the union-find problem. In Proc. 23rd ACM Symposium on Theory of Computing, pages 370–380, 1991.

   Google Scholar 

4. J. Aspnes and W. Hurwood. Spreading rumors rapidly despite an adversary. In Proc. 15th ACM Symposium on Principles of Distributed Computing, pages 143–151, 1996.

   Google Scholar 

5. J. Aspnes and O. Waarts. Modular competitiveness for distributed algorithms. In Proc. 28th ACM Symposium on the Theory of Computing, pages 237–246, 1996.

   Google Scholar 

6. H. Attiya and O. Rachman. Atomic snapshots in o(n log n) operations. In Proc. 12th ACM Symposium on Principles of Distributed Computing, pages 29–40, 1993.

   Google Scholar 

7. Y. Aumann. Efficient asynchronous consensus with the weak adversary scheduler. In Proc. 16th ACM Symposium on Principles of Distributed Computing, 1997.

   Google Scholar 

8. Y. Aumann and M.A. Bender. Efficient asynchronous consensus with the valueoblivious adversary scheduler. In Proc. 23rd International Colloquium on Automata, Languages, and Programming, 1996.

   Google Scholar 

9. S. Ben-David, A. Borodin, R. Karp, G. Tardos, and A. Widgerson. On the power of randomization in on-line algorithms. In Proc. 22nd Symposium on Theory of Algorithms, pages 379–386, 1990.

   Google Scholar 

10. T. Chandra. Polylog randomized wait-free consensus. In Proc. 15th ACM Symposium on Principles of Distributed Computing, 1996.

    Google Scholar 

11. B. Chor, A. Israeli, and M. Li. Wait-free consensus using asynchronous hardware. SIAM J. Comput., 23(4):701–712, August 1994. Preliminary version appears in Proceedings of the 6th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, pages 86–97, 1987.

    Article  Google Scholar 

12. S. Even and B. Monien. On the number of rounds needed to disseminate information. In Proc. 1st ACM Symposium on Parallel Algorithms and Architectures, 1989.

    Google Scholar 

13. M. Herlihy. Wait-free synchronization. ACM Transactions on Programming Languages and Systems, 13(1):124–149, January 1991.

    Article  Google Scholar 

14. E. Koutsoupias and C. Papadimitriou. Beyond competitive analysis. In Proc. 25th Symposium on Foundations of Computer Science, pages 394–400, 1994.

    Google Scholar 

15. B. Patt-Shamir and S. Rajsbaum. A theory of clock synchronization. In Proc. 26th ACM Symposium on the Theory of Computing, pages 810–819, 1994.

    Google Scholar 

16. M. Saks, N. Shavit, and H. Woll. Optimal time randomized consensus — making resilient algorithms fast in practice. In Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms, pages 351–362, 1991.

    Google Scholar 

17. D. Sleator and R. E. Tarjan. Amortized efficiency of list update and paging rules. Communications of the ACM, 28:202–208, 1985.

    Article  Google Scholar 

Download references