The Synchronization Power of Atomic Bitwise Operations

Author Damien Imbs



PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2015.26.pdf
  • Filesize: 0.49 MB
  • 17 pages

Document Identifiers

Author Details

Damien Imbs

Cite AsGet BibTex

Damien Imbs. The Synchronization Power of Atomic Bitwise Operations. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 26:1-26:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.OPODIS.2015.26

Abstract

In a distributed system, processes must reach a certain level of synchronization to solve a common problem. The strongest form of synchronization can be reached through consensus: all the processes must agree on a common value that has been proposed by one of them. Consensus is universal in shared memory systems: any type of shared object can be implemented using it. Unfortunately, consensus is impossible to solve using only shared registers when processes can crash. To circumvent this impossibility, one can use stronger objects, for example Test&Set or Compare&Swap. The synchronization power of these objects can be measured using the concept of Consensus Number: the maximum number of processes for which they can solve consensus in a crash-prone system. Bitwise AND, OR and XOR operations are very widely used, but have received little attention in the distributed setting. Because bitwise operations are available in most modern processors, they can constitute a valuable tool for synchronization in distributed systems. It is then natural to consider the level of synchronization that these operations can achieve. This paper introduces shared AND/OR and AND/OR/XOR registers. A shared AND/OR register consists of an array of x bits and offers three atomic operations: AND and OR operations, which take an array of x bits as parameter and change the state of the register by applying the corresponding bitwise operation, and a read operation which returns the content of the array. A shared AND/OR/XOR register additionally offers a XOR operation. We show that shared AND/OR registers of x bits have consensus number lfloor (x+1)/2 rfloor, by presenting an algorithm that solves consensus using these registers, and by proving that consensus cannot be solved for n processes using AND/OR registers that have strictly less than 2n-1 bits. We then show that shared AND/OR/XOR registers of x bits have consensus number x using a similar technique.
Keywords
  • Asynchronous systems
  • Binary operations
  • Consensus
  • Consensus number
  • Read/write shared memory
  • Shared objects
  • Synchronization
  • Wait-freedom

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Yehuda Afek, Eli Gafni, and Adam Morrison. Common2 extended to stacks and unbounded concurrency. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Principles of Distributed Computing (PODC'06), pages 218-227, 2006. URL: http://dx.doi.org/10.1145/1146381.1146415.
  2. Yehuda Afek, Eytan Weisberger, and Hanan Weisman. A completeness theorem for a class of synchronization objects (extended abstract). In Proceedings of the Twelth Annual ACM Symposium on Principles of Distributed Computing (PODC'93), pages 159-170, 1993. URL: http://dx.doi.org/10.1145/164051.164071.
  3. Elizabeth Borowsky and Eli Gafni. Generalized FLP impossibility result for t-resilient asynchronous computations. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing (STOC'93), pages 91-100, 1993. URL: http://dx.doi.org/10.1145/167088.167119.
  4. Soma Chaudhuri. More choices allow more faults: Set consensus problems in totally asynchronous systems. Information and Computation, 105(1):132-158, 1993. URL: http://dx.doi.org/10.1006/inco.1993.1043.
  5. Michael J. Fischer, Nancy A. Lynch, and Mike Paterson. Impossibility of distributed consensus with one faulty process. Journal of the ACM, 32(2):374-382, 1985. URL: http://dx.doi.org/10.1145/3149.214121.
  6. Eli Gafni and Petr Kuznetsov. On set consensus numbers. Distributed Computing, 24(3-4):149-163, 2011. URL: http://dx.doi.org/10.1007/s00446-011-0142-8.
  7. Phuong Hoai Ha, Philippas Tsigas, and Otto J. Anshus. The synchronization power of coalesced memory accesses. IEEE Transactions on Parallel and Distributed Systems, 21(7):939-953, 2010. URL: http://dx.doi.org/10.1109/TPDS.2009.135.
  8. Maurice Herlihy. Impossibility and universality results for wait-free synchronization. In Proceedings of the Seventh Annual ACM Symposium on Principles of Distributed Computing (PODC'88), pages 276-290, 1988. URL: http://dx.doi.org/10.1145/62546.62593.
  9. Maurice Herlihy. Wait-free synchronization. ACM Transactions on Programming Languages and Systems (TOPLAS), 13(1):124-149, 1991. URL: http://dx.doi.org/10.1145/114005.102808.
  10. Maurice Herlihy and Nir Shavit. The topological structure of asynchronous computability. Journal of the ACM, 46(6):858-923, 1999. URL: http://dx.doi.org/10.1145/331524.331529.
  11. Damien Imbs and Michel Raynal. A note on atomicity: Boosting test&set to solve consensus. Information Processing Letters, 109(12):589-591, 2009. URL: http://dx.doi.org/10.1016/j.ipl.2009.02.004.
  12. Prasad Jayanti. Robust wait-free hierarchies. Journal of the ACM, 44(4):592-614, 1997. URL: http://dx.doi.org/10.1145/263867.263888.
  13. Michael C. Loui and Hosame H. Abu-Amara. Memory requirements for agreement among unreliable asynchronous processes. Advances in Computing research, 4:163-183, 1987. Google Scholar
  14. Serge A. Plotkin. Sticky bits and universality of consensus. In Proceedings of the Eighth Annual ACM Symposium on Principles of Distributed Computing (PODC'89), pages 159-175, 1989. URL: http://dx.doi.org/10.1145/72981.72992.
  15. Michael E. Saks and Fotios Zaharoglou. Wait-free k-set agreement is impossible: The topology of public knowledge. SIAM Journal on Computing, 29(5):1449-1483, 2000. URL: http://dx.doi.org/10.1137/S0097539796307698.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail