More Web Proxy on the site http://driver.im/

Article

Sub-logarithmic test-and-set against aweak adversary

Authors:

James AspnesAuthors Info & Claims

DISC'11: Proceedings of the 25th international conference on Distributed computing

Pages 97 - 109

Published: 20 September 2011 Publication History

Abstract

A randomized implementation is given of a test-and-set register with O(log log n) individual step complexity and O(n) total step complexity against an oblivious adversary. The implementation is linearizable and multi-shot, and shows an exponential complexity improvement over previous solutions designed to work against a strong adversary.

References

[1]

Afek, Y., Gafni, E., Tromp, J., Vitányi, P.M.B.: Wait-free test-and-set (extended abstract). In: Segall, A., Zaks, S. (eds.) WDAG 1992. LNCS, vol. 647, pp. 85-94. Springer, Heidelberg (1992).

Digital Library

[2]

Alistarh, D., Attiya, H., Gilbert, S., Giurgiu, A., Guerraoui, R.: Fast randomized test-andset and renaming. In: Lynch, N.A., Shvartsman, A.A. (eds.) DISC 2010. LNCS, vol. 6343, pp. 94-108. Springer, Heidelberg (2010).

Digital Library

[3]

Attiya, H., Censor, K.: Tight bounds for asynchronous randomized consensus. J. ACM55(5), 1-26 (2008).

Digital Library

[4]

Attiya, H., Censor-Hillel, K.: Lower bounds for randomized consensus under a weak adversary. SIAM J. Comput. 39(8), 3885-3904 (2010).

Digital Library

[5]

Attiya, H., Guerraoui, R., Hendler, D., Kuznetsov, P., Michael, M.M., Vechev, M.T.: Laws of order: expensive synchronization in concurrent algorithms cannot be eliminated. In: POPL, pp. 487-498 (2011).

Digital Library

[6]

Aumann, Y.: Efficient asynchronous consensus with the weak adversary scheduler. In: PODC 1997: Proceedings of the Sixteenth Annual ACM Symposium on Principles of Distributed Computing, pp. 209-218. ACM, New York (1997).

Digital Library

[7]

Golab, W.M., Hadzilacos, V., Hendler, D., Woelfel, P.: Constant-rmr implementations of cas and other synchronization primitives using read and write operations. In: PODC, pp. 3-12 (2007).

Digital Library

[8]

Golab, W.M., Hendler, D., Woelfel, P.: An o(1) rmrs leader election algorithm. SIAM J. Comput. 39(7), 2726-2760 (2010).

Digital Library

[9]

Golab, W.M., Higham, L., Woelfel, P.: Linearizable implementations do not suffice for randomized distributed computation. In: STOC, pp. 373-382 (2011).

Digital Library

[10]

Herlihy, M.: Randomized wait-free concurrent objects (extended abstract). In: Proceedings of the Tenth Annual ACM symposium on Principles of Distributed Computing, PODC 1991, pp. 11-21. ACM, New York (1991).

Digital Library

[11]

Herlihy, M.: Wait-free synchronization. ACM Trans. Program. Lang. Syst. 13(1), 124-149 (1991).

Digital Library

[12]

Mitzenmacher, M., Upfal, E.: Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, New York (2005).

Digital Library

[13]

Peterson, G.L., Fischer, M.J.: Economical solutions for the critical section problem in a distributed system (extended abstract). In: Proceedings of the Ninth Annual ACM Symposium on Theory of Computing, STOC 1977, pp. 91-97. ACM, New York (1977).

Digital Library

[14]

Plotkin, S.: Chapter 4: Sticky bits and universality of consensus. Ph.D. Thesis. MIT (1998).

[15]

Tromp, J., Vitányi, P.: Randomized two-process wait-free test-and-set. Distrib. Comput. 15(3), 127-135 (2002).

Digital Library

Cited By

Alistarh DGelashvili RVladu AGeorgiou CSpirakis P(2015)How To Elect a Leader Faster than a TournamentProceedings of the 2015 ACM Symposium on Principles of Distributed Computing10.1145/2767386.2767420(365-374)Online publication date: 21-Jul-2015
https://dl.acm.org/doi/10.1145/2767386.2767420
Giakkoupis GHelmi MHigham LWoelfel PServedio RRubinfeld R(2015)Test-and-Set in Optimal SpaceProceedings of the forty-seventh annual ACM symposium on Theory of Computing10.1145/2746539.2746627(615-623)Online publication date: 14-Jun-2015
https://dl.acm.org/doi/10.1145/2746539.2746627
Aghazadeh ZGolab WWoelfel PHalldórsson MDolev S(2014)Making objects writableProceedings of the 2014 ACM symposium on Principles of distributed computing10.1145/2611462.2611483(385-395)Online publication date: 15-Jul-2014
https://dl.acm.org/doi/10.1145/2611462.2611483
Show More Cited By

Recommendations

Randomized mutual exclusion with sub-logarithmic RMR-complexity

Mutual exclusion is a fundamental distributed coordination problem. Shared-memory mutual exclusion research focuses on local-spin algorithms and uses the remote memory references (RMRs) metric. Attiya, Hendler, and Woelfel (40th STOC, 2008) established ...
Faster randomized consensus with an oblivious adversary

Two new algorithms are given for randomized consensus in a shared-memory model with an oblivious adversary. Each is based on a new construction of a conciliator, an object that guarantees termination and validity, but that only guarantees agreement with ...
Distributed Resource Discovery in Sub-Logarithmic Time
PODC '15: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing

We present a new distributed algorithm for the resource discovery problem introduced by Harchol-Balter, Leighton, and Levin in PODC'99. The resource discovery problem consists of a synchronous network with n machines in which at any timestep any machine ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

DISC'11: Proceedings of the 25th international conference on Distributed computing

September 2011

504 pages

ISBN:9783642240997

Editor:
David Peleg
Weizmann Institute of Science, Department of Computer Science, Rehovot, Israel

Sponsors

CINI: CINI: Consorzio Interuniversitario Nazionale per l'Informatica
Università di Roma 'La Sapienza': Università di Roma 'La Sapienza'
Microsoft Research: Microsoft Research
EATCS: European Association for Theoretical Computer Science

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 20 September 2011

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Alistarh DGelashvili RVladu AGeorgiou CSpirakis P(2015)How To Elect a Leader Faster than a TournamentProceedings of the 2015 ACM Symposium on Principles of Distributed Computing10.1145/2767386.2767420(365-374)Online publication date: 21-Jul-2015
https://dl.acm.org/doi/10.1145/2767386.2767420
Giakkoupis GHelmi MHigham LWoelfel PServedio RRubinfeld R(2015)Test-and-Set in Optimal SpaceProceedings of the forty-seventh annual ACM symposium on Theory of Computing10.1145/2746539.2746627(615-623)Online publication date: 14-Jun-2015
https://dl.acm.org/doi/10.1145/2746539.2746627
Aghazadeh ZGolab WWoelfel PHalldórsson MDolev S(2014)Making objects writableProceedings of the 2014 ACM symposium on Principles of distributed computing10.1145/2611462.2611483(385-395)Online publication date: 15-Jul-2014
https://dl.acm.org/doi/10.1145/2611462.2611483
Alistarh DAspnes JCensor-Hillel KGilbert SGuerraoui R(2014)Tight Bounds for Asynchronous RenamingJournal of the ACM10.1145/259763061:3(1-51)Online publication date: 2-Jun-2014
https://dl.acm.org/doi/10.1145/2597630
Aghazadeh ZGolab WWoelfel PFatourou PTaubenfeld G(2013)Brief announcementProceedings of the 2013 ACM symposium on Principles of distributed computing10.1145/2484239.2484286(322-324)Online publication date: 22-Jul-2013
https://dl.acm.org/doi/10.1145/2484239.2484286
Alistarh DAspnes JGiakkoupis GWoelfel PFatourou PTaubenfeld G(2013)Randomized loose renaming in o(log log n) timeProceedings of the 2013 ACM symposium on Principles of distributed computing10.1145/2484239.2484240(200-209)Online publication date: 22-Jul-2013
https://dl.acm.org/doi/10.1145/2484239.2484240
Giakkoupis GHelmi MHigham LWoelfel P(2013)An $O\sqrt n$ Space Bound for Obstruction-Free Leader ElectionProceedings of the 27th International Symposium on Distributed Computing - Volume 820510.1007/978-3-642-41527-2_4(46-60)Online publication date: 14-Oct-2013
https://dl.acm.org/doi/10.1007/978-3-642-41527-2_4
Helmi MHigham LWoelfel PKowalski DPanconesi A(2012)Strongly linearizable implementationsProceedings of the 2012 ACM symposium on Principles of distributed computing10.1145/2332432.2332508(385-394)Online publication date: 16-Jul-2012
https://dl.acm.org/doi/10.1145/2332432.2332508
Giakkoupis GWoelfel PKowalski DPanconesi A(2012)On the time and space complexity of randomized test-and-setProceedings of the 2012 ACM symposium on Principles of distributed computing10.1145/2332432.2332436(19-28)Online publication date: 16-Jul-2012
https://dl.acm.org/doi/10.1145/2332432.2332436
Aspnes JKowalski DPanconesi A(2012)Faster randomized consensus with an oblivious adversaryProceedings of the 2012 ACM symposium on Principles of distributed computing10.1145/2332432.2332434(1-8)Online publication date: 16-Jul-2012
https://dl.acm.org/doi/10.1145/2332432.2332434

View Options

View options

Media

Figures

Other

Tables

View Table of Contents