Article

Free access

Modular competitiveness for distributed algorithms

Authors:

James Aspnes,

Orli WaartsAuthors Info & Claims

STOC '96: Proceedings of the twenty-eighth annual ACM symposium on Theory of Computing

Pages 237 - 246

https://doi.org/10.1145/237814.237869

Published: 01 July 1996 Publication History

PDF eReader

References

[1]

K. Abrahamson. On achieving consensus using a shared memory. In Proc. 7th ACM Symposium on Principles of Distributed Computing, pp. 291- 302, August 1988.

Digital Library

Google Scholar

[2]

Y. Afek, H. Attiya, D. Dolev, E. Gafni, M. Merritt, and N. Shavit. Atomic Snapshots of Shared Memory, In Journal of the ACM, Vol. 40, No. 4, pages 879-890, September 1993. Preliminary version appears in Proc. 9th ACM Symposium on Principles of Distributed Computing, pp. 1-13, 1990.

Digital Library

Google Scholar

[3]

M. Ajtai, J. Aspnes, C. Dwork, and O. Waarts. A theory of competitive analysis for distributed algorithms. In Proc. 33rd IBBB Symposium on Foundations of Computer Science, pp. 401-411, November 1994. Full version available.

Digital Library

Google Scholar

[4]

N. Alon, G. Kalai, M. Ricklin, and L. Stockmeyer. Lower bounds on the competitive ratio for mobile user tracking and distributed job scheduling. In Proc. 33rd IBBB Symposium on Foundations of Computer Science, pages 334-343, October 1992.

Digital Library

Google Scholar

[5]

J. Anderson. Composite Registers. In Distributed Computing, Vol. 6, No. 3, pages 141-154. Preliminary version appears in Proc 9th ACM Symposium on Principles of Distributed Computing, pp. 15-30, August 1990.

Digital Library

Google Scholar

[6]

J. Aspnes. Time- and space-efficient randomised consensus. Journal of Algorithms 14(3):414-431, May 1993. An earlier version appeared in Proc. 9th ACM Symposium on Principles of Distributed Computing, pp. 325- 331, August 1990.

Digital Library

Google Scholar

[7]

J. Aspnes and M.P. Herlihy. Fast randomized consensus using shared memory. In Journel of Algorithms 11(3), pp.441-461, September 1990.

Digital Library

Google Scholar

[8]

J. Aspnes and M.P. Herlihy. Wait-free data structures in the Asynchronous PRAM Model. In Proceedings of the 2nd Annual Symposium on Parallel Algorithms and Architectures, July 1990, pp. 340-349, Crete, Greece.

Digital Library

Google Scholar

[9]

J. Aspnes and O. Waarts. Randomised consensus in expected O(nlog2n) operations per processor. In Proc. 33rd IBBB Symposium on Foundations of Computer Science, pp. 137-146, October 1992. To appear, SIAM Journal on Computing.

Digital Library

Google Scholar

[10]

J. Aspnes and O. Waarts. Modular competitiveness for distributed algorithms. Manuscript 1995.

Google Scholar

[11]

H. Attiya, M.P. Herlihy, and O. Rachman. Efficient atomic snapshots using lattice agreement. Technical report, Technion, Haifa, Israel, 1992. A preliminary version appeared in proceedings of the 6th International Workshop on Distributed Algorithms, Haifa, Israel, November 1992, (A. Segall and S. Zaks, eds.), Lecture Notes in Computer Science #647, Springer-Verlag, pp. 35-53.

Digital Library

Google Scholar

[12]

H. Attiya, A. Herzberg, and S. Rajsbaum. Optimal clock synchronization under different delay assumptions. In Proc. 18th ACM Symposium on Principles of Distriuted Computing, pp. 109-120, Aug. 1993.

Digital Library

Google Scholar

[13]

H. Attiya and O. Rachman. Atomic snapshots in O(nlog n) operations. In Proc. 12th ACM Symposium on Principles of Distributed Computing, pp. 29-40, Aug. 1993.

Digital Library

Google Scholar

[14]

B. Awerbuch and Y. Asar. Local optimization of global objectives: Competitive distributed deadlock resolution and resource allocation. In Proc. 35th IEEE Symposium on Foundation of Computer Science, pp. 240- 249, November 1994.

Digital Library

Google Scholar

[15]

B. Awerbuch, Y. Bartal, and A. Fiat. Competitive distributed file allocation. In Proc. 25th ACM Symposium on Theory of Computing, pp. 164- 173, May 1993.

Digital Library

Google Scholar

[16]

B. Awerbuch, Y. Burtal, and A. Fiat. Heat and Dump: competitive distributed paging. In Proc. 34th IBBB Symposium on Foundations of Computer Science, pp. 22-31, November 1993.

Digital Library

Google Scholar

[17]

B. Awerbuch, S. Kutten, and D. Peleg. Competitive distributed job scheduling, in Proc. 24th ACM Symposium on Theory of Computing, pp. 571-580, May 1992.

Digital Library

Google Scholar

[18]

B. Awerbuch and D. Peleg. Sparse partitions. In Proc. 31st IBBB Symposium on Foundations of Computer Science, pp. 503-513, November 1990.

Digital Library

Google Scholar

[19]

Y. Bartal, A. Fiat, and Y. Rabani. Competitive algorithms for distributed data management. In Proc. 24th ACM Symposium on Theory of Computing, pp. 39-50, 1992.

Digital Library

Google Scholar

[20]

E. Borowsky and E. Gafni. Immediate atomic snapshots and fast renaming. In Proc. 12th ACM Symposium on Principles of Distributed Computing, pp. 41-51, August 1993.

Digital Library

Google Scholar

[21]

Y. Bartal and A. Rosen. The distributed k-server problem - A competitive distributed translator for k-server algorithms. In Proc. 33rd IEEE Symposium on Foundations of Computer Science, pp. 344-353, October 1992.

Digital Library

Google Scholar

[22]

G. Bracha and O. Rachman. Randomized consensus in expected O(n2 log n) operations. Proceedings of the Fifth International Workshop on Distributed Algorithms. Springer-Verlag, 1991.

Digital Library

Google Scholar

[23]

T. Chandra and C. Dwork. Using consensus to solve atomic snapshots. Submitted for Publication

Google Scholar

[24]

B. Chor, A. Israeli, and M. Li. Wait-Free Consensus Using Asynchronous Hardware. In SIAM Journal on Computing, Vol. 23, No. 4, pages 701-712, August 1994. Preliminary version appears in Proc. 6th ACM Symposium on Principles of Distributed Computing, pages 86-97, 1987.

Digital Library

Google Scholar

[25]

D. Dolev and N. Shavit. Bounded Concurrent Time-Stamp Systems are Constructible ! To appear in SIAM Journal on Computing Preliminary version appears in Proc. 21st ACM Symposium on Theory of Computing, pages 454-465, 1989. An extended version appears in IBM Research Report RJ 6786, March 1990.

Digital Library

Google Scholar

[26]

D. Dolev, R. Reischuk, and H.R. Strong. Early stopping in Byzantine agreement. In Journal of the ACM, 34:7, Oct. 1990, pp. 720-741. First appeared in: Eventual is Earlier than Immediate, IBM RJ 3915, 1983.

Digital Library

Google Scholar

[27]

C. Dwork, J. Halpern, and O. Waarts. Accomplishing work in the presence of failures. In Proc. 11th ACM Symposium, Principles of Distributed Computing, pp. 91-102, 1992.

Digital Library

Google Scholar

[28]

C Dwork, M.P. Herlihy, S. Plotkin, and O. Waarto. Time-lapse snapshots. Proceedings of Israel Symposium on the Theory of Computing and Systems, 1992.

Digital Library

Google Scholar

[29]

C. Dwork, M.P. Herlihy, and O. Waarts. Bounded round numbers. In Proc. 12th ACM Symposium on Principles of Distributed Comparing, pp. 53- 64, 1993.

Digital Library

Google Scholar

[30]

C. Dwork, M.P. Herlihy, and O. Waarts. Contention in shared memory algorithms. To appear in the Journal of the ACM. Preliminary version appears in Proc. 25th ACM Symposium on Theory of Computing, pages 174-183, May 1993. Expanded version: Digital Equipment Corporation Technical Report CRL 93/12.

Digital Library

Google Scholar

[31]

C. Dwork and Y. Moses. Knowledge and common knowledge in a Byzantine environment: crash failures. In Information and Computation 88(2) (1990), originally in Proc. TARK 1986.

Digital Library

Google Scholar

[32]

C. Dwork and O. Waarts. Simple and efficient bounded concurrent timestamping or bounded concurrent timestamp systems are comprehensible! To appear in the Journal of the ACM. Preliminary version appears in Proc. 24th ACM Symposium on Theory of Computing, pp. 655- 666, 1992.

Digital Library

Google Scholar

[33]

M. Fischer and A. Michael, Sacrificing serializability to attain high availability of data in an unreliable network. Research Report 221, Yale U., Feb. 1982.

Digital Library

Google Scholar

[34]

R. Gawlick, N. Lynch, and N. Shavit. Concurrent timestamping made simple. Proceedings of Israel Symposium on Theory of Computing and Systems, 1992.

Digital Library

Google Scholar

[35]

S. Haldar. Efficient bounded timestamping using traceable use abstraction - Is writer's guessing better than reader's telling? Technical Report RUU-CS-93-28, Department of Computer Science, Utrecht, September 1993.

Google Scholar

[36]

J. Y. Halpern and Y. Moses. Knowledge and common knowledge in a distributed environment, Journal of Association for Computing Machinery, Vol 37, No 3, January 1990, pp. 549-587. A preliminary version appeared in Proc. 3rd ACM Symposium on Principles of Distributed Computing, 1984.

Digital Library

Google Scholar

[37]

J.Y. Halpern, Y. Moses, and O. Waarts. A characterization of eventual Byzantine agreement. In Proc 9th ACM Symposium on Principles of Distributed Computing, pp. 333-346, August 1990.

Digital Library

Google Scholar

[38]

M.P. Herlihy. Randomized wait-free concurrent objects. In Pros. 10th ACM Symposium on Princeples of Distributed Computing, August 1991.

Digital Library

Google Scholar

[39]

A. Israeli and M. Li. Bounded Time Stamps. In Distributed Computing, Vol. 6, No. 4, pages 205-209. Preliminary version appears in Proc. 28th IEEE Symposium on Foundations of Computer Science, pp. 371-382, October 1987.

Digital Library

Google Scholar

[40]

A. Israeli and M. Pinhasov. A Concurrent Time-Stamp Scheme which is Linear in Time and Space. In Proceedings of the 6th International Workshop on Distributed Algorithms, LNCS 647, Springer-Verlag, pages 95-109, 1992.

Digital Library

Google Scholar

[41]

E. Koutsoupias and C.H. Papadimitriou. Beyond competitive analysis. In Proc. 33rd IEEE Symposium on Foundations of Computer Science, pp. 394-400, November 1994.

Digital Library

Google Scholar

[42]

L. M. Kirousis, P. Spirakis and P. Tsigas. Reading many variables in one atomic operation: solutions with linear or sublinear complexity. In Proceedings of the 5th International Workshop on Distributed Algorsthms, 1991.

Digital Library

Google Scholar

[43]

Y. Moses and M.R. Tuttle. Programming simultaneous actions using common knowledge. Algorithmics 3(1), pp. 121-169, 1988 Preliminary version appeared in Proc. 28th IEEE Symposium on Foundations of Competer Sciences, pp. 208-221, 1986.

Digital Library

Google Scholar

[44]

G. Neiger. Using knowledge to achieve consistent coordination in distributed systems. Manuscript, 1990.

Google Scholar

[45]

G. Neiger and M. R. Tuttle. Common knowledge and consistent simultaneous coordination. In Proceedings of the 4th International Workshop on Distributed Algorithms, 1990.

Digital Library

Google Scholar

[46]

C.H. Papadimitriou and M. Yannakakis. Linear programming without the matrix. In Proc 25th ACM Symposium on Theory of Computing, pp. 121-129, May 1993.

Digital Library

Google Scholar

[47]

B. Patt-Shamir and S. Rajsbaum. A theory of clock synchronization. In Proc. 25th ACM Symposium on Theory of Computing, pp. 810-819, May 1994.

Digital Library

Google Scholar

[48]

Y. Riany, N. Shavit and D. Touiton. Practical Snapshots. In Procedings of Israel Symposium on Theory of Computing and System, 1994.

Google Scholar

[49]

M. Saks, N. Shavit, and H. Woll. Optimal time randomized consensus making resilient algorithms fast in practice. In Proceedings of the 2nd ACM.SIAM Symposium on Diserate Algorithms, pp. 351-382, 1991.

Digital Library

Google Scholar

[50]

D. D. Sleator and R. E. Tarjan. Amortised efficiency of list update and paging rules. Comm. of the ACM 28(2), pp. 202-908, 1985.

Digital Library

Google Scholar

[51]

P.M.B. Vitanyi and B. Awerbuch. Atomic Shared Register Access by Asynchronous Hardware. In Free. 27th IEEE Symposium on Foundations of Computer Science, pp. 233-243, 1986. Errata in Proc. 28th IEEE Symposium on Foundations of Computer Science, 1987.

Google Scholar

Cited By

View all

Dwork C(2019)Distributed computing columnACM SIGACT News10.1145/235666.23567127:3(50-54)Online publication date: 27-Feb-2019
https://dl.acm.org/doi/10.1145/235666.235671
Reineke JGrund D(2008)Relative competitive analysis of cache replacement policiesACM SIGPLAN Notices10.1145/1379023.137566543:7(51-60)Online publication date: 12-Jun-2008
https://dl.acm.org/doi/10.1145/1379023.1375665
Reineke JGrund DFlautner KRegehr J(2008)Relative competitive analysis of cache replacement policiesProceedings of the 2008 ACM SIGPLAN-SIGBED conference on Languages, compilers, and tools for embedded systems10.1145/1375657.1375665(51-60)Online publication date: 12-Jun-2008
https://dl.acm.org/doi/10.1145/1375657.1375665
Show More Cited By

Index Terms

Modular competitiveness for distributed algorithms
1. Theory of computation
  1. Computational complexity and cryptography
    1. Complexity classes
  2. Design and analysis of algorithms

Recommendations

Formula for competitiveness

Approaches taken by the countries of Asia's Pacific rim to competing successfully in the electronics marketplace are examined. Key elements are strong government support, national technical objectives, dynamic science and technology centers, and robust ...
Software development offshoring competitiveness: a case study of asean countries
Industry Knowledge Competitiveness Advances Economic Competitiveness
ICEE '12: Proceedings of the 2012 3rd International Conference on E-Business and E-Government - Volume 04

Industry economic competitiveness is foundation of country's integrate competitiveness and knowledge competitiveness is main influence factor of industry economic competitiveness. Based on connotation and relation discriminating of knowledge ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '96: Proceedings of the twenty-eighth annual ACM symposium on Theory of Computing

July 1996

661 pages

ISBN:0897917855

DOI:10.1145/237814

Chairman:
Gary L. Miller

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1996

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC96

Sponsor:

SIGACT

STOC96: ACM Symposium on Theory of Computing

May 22 - 24, 1996

Pennsylvania, Philadelphia, USA

Acceptance Rates

STOC '96 Paper Acceptance Rate 74 of 201 submissions, 37%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
343
Total Downloads

Downloads (Last 12 months)49
Downloads (Last 6 weeks)7

Reflects downloads up to 26 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Dwork C(2019)Distributed computing columnACM SIGACT News10.1145/235666.23567127:3(50-54)Online publication date: 27-Feb-2019
https://dl.acm.org/doi/10.1145/235666.235671
Reineke JGrund D(2008)Relative competitive analysis of cache replacement policiesACM SIGPLAN Notices10.1145/1379023.137566543:7(51-60)Online publication date: 12-Jun-2008
https://dl.acm.org/doi/10.1145/1379023.1375665
Reineke JGrund DFlautner KRegehr J(2008)Relative competitive analysis of cache replacement policiesProceedings of the 2008 ACM SIGPLAN-SIGBED conference on Languages, compilers, and tools for embedded systems10.1145/1375657.1375665(51-60)Online publication date: 12-Jun-2008
https://dl.acm.org/doi/10.1145/1375657.1375665
Aspnes J(2005)Competitive analysis of distributed algorithmsOnline Algorithms10.1007/BFb0029567(118-146)Online publication date: 22-Nov-2005
https://doi.org/10.1007/BFb0029567
Renaud KLo JBishop Jvan Zyl PWorrall B(2003)Algon: a framework for supporting comparison of distributed algorithm performanceEleventh Euromicro Conference on Parallel, Distributed and Network-Based Processing, 2003. Proceedings.10.1109/EMPDP.2003.1183620(425-432)Online publication date: 2003
https://doi.org/10.1109/EMPDP.2003.1183620
Aguilera MEnglert BGafni E(2003)Uniform Solvability with a Finite Number of MWMR RegistersDistributed Computing10.1007/978-3-540-39989-6_2(16-29)Online publication date: 2003
https://doi.org/10.1007/978-3-540-39989-6_2
Berman PGaray J(2002)Adaptability and the Usefulness of Hints (Extended Abstract)Algorithms — ESA’ 9810.1007/3-540-68530-8_23(271-282)Online publication date: 15-Mar-2002
https://doi.org/10.1007/3-540-68530-8_23
Urban PDefago XSchiper A(2000)Contention-aware metrics for distributed algorithms: comparison of atomic broadcast algorithmsProceedings Ninth International Conference on Computer Communications and Networks (Cat.No.00EX440)10.1109/ICCCN.2000.885548(582-589)Online publication date: 2000
https://doi.org/10.1109/ICCCN.2000.885548
Aumann YKapah-Levy ATarjan RWarnow T(1999)Cooperative sharing and asynchronous consensus using single-reader single-writer registersProceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms10.5555/314500.314532(61-70)Online publication date: 1-Jan-1999
https://dl.acm.org/doi/10.5555/314500.314532
Aumann YBurns JAttiya H(1997)Efficient asynchronous consensus with the weak adversary schedulerProceedings of the sixteenth annual ACM symposium on Principles of distributed computing10.1145/259380.259441(209-218)Online publication date: 1-Aug-1997
https://dl.acm.org/doi/10.1145/259380.259441
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Formula for competitiveness

Software development offshoring competitiveness: a case study of asean countries

Industry Knowledge Competitiveness Advances Economic Competitiveness