Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Read–modify–write
open-in-new
<h2 id="consensus-number">Consensus number</h2> <p class="note">This section is an excerpt from <a href="/facts/Consensus_(computer_science)/rC0eH88V">Consensus (computer science) § Consensus number</a>.[<a href="https://en.wikipedia.org/w/index.php?title=Consensus_(computer_science)&action=edit">edit</a>]</p> <p>To solve the consensus problem in a shared-memory system, concurrent objects must be introduced. A concurrent object, or shared object, is a data structure which helps concurrent processes communicate to reach an agreement. Traditional implementations using <a href="/facts/Critical_section/zYwj5uh5">critical sections</a> face the risk of crashing if some process dies inside the critical section or sleeps for an intolerably long time. Researchers defined <a href="/facts/Non-blocking_algorithm/KhLDma0v">wait-freedom</a> as the guarantee that the algorithm completes in a finite number of steps. </p><p>The consensus number of a concurrent object is defined to be the maximum number of processes in the system which can reach consensus by the given object in a wait-free implementation.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> Objects with a consensus number of n {\displaystyle n} can implement any object with a consensus number of n {\displaystyle n} or lower, but cannot implement any objects with a higher consensus number. The consensus numbers form what is called <a href="/facts/Maurice_Herlihy/QvzHk8u9">Herlihy</a>'s hierarchy of synchronization objects.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> </p> <table><tbody><tr><th>Consensusnumber</th><th>Objects</th></tr><tr><td> 1 {\displaystyle 1} </td><td><a href="/facts/Atomic_semantics/eUeJj9kF">atomic</a> <a href="/facts/Shared_register/GUVL28yU">read/write registers</a>, <a href="/facts/Lock_(computer_science)/e3a9gnJT">mutex</a></td></tr><tr><td> 2 {\displaystyle 2} </td><td><a href="/facts/Test-and-set/KyR6bYFo">test-and-set</a>, <a href="/facts/Swap_(computer_programming)/lMfoMXCq">swap</a>, <a href="/facts/Fetch-and-add/7GCQDxB2">fetch-and-add</a>, wait-free <a href="/facts/Queue_(abstract_data_type)/hVPjPXus">queue</a> or <a href="/facts/Stack_(abstract_data_type)/bj7l94v1">stack</a></td></tr><tr><td>...</td><td>...</td></tr><tr><td> 2 n − 2 {\displaystyle 2n-2} </td><td>n-register assignment</td></tr><tr><td>...</td><td>...</td></tr><tr><td> ∞ {\displaystyle \infty } </td><td><a href="/facts/Compare-and-swap/7mJkkycd">compare-and-swap</a>, <a href="/facts/Load-link%2fstore-conditional/owLXpjeu">load-link/store-conditional</a>,<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> memory-to-memory move and swap, queue with peek operation, fetch&cons, sticky byte</td></tr></tbody></table> According to the hierarchy, read/write registers cannot solve consensus even in a 2-process system. Data structures like stacks and queues can only solve consensus between two processes. However, some concurrent objects are universal (notated in the table with ∞ {\displaystyle \infty } ), which means they can solve consensus among any number of processes and they can simulate any other objects through an operation sequence.<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Linearizability/u3pnNCvs">Linearizability</a></li> <li><a href="/facts/Read%25E2%2580%2593erase%25E2%2580%2593modify%25E2%2580%2593write/copgTWeh">Read–erase–modify–write</a></li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>Massmind: "The read–modify–write problem" <a href="http://techref.massmind.org/techref/readmodwrite.htm" target="_blank">http://techref.massmind.org/techref/readmodwrite.htm</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>"Basic RAID Organizations". umass.edu. Archived from the original on 2021-02-24. Retrieved 2013-10-04. <a href="https://web.archive.org/web/20210224160746/http://www.ecs.umass.edu/ece/koren/architecture/Raid/basicRAID.html" target="_blank">https://web.archive.org/web/20210224160746/http://www.ecs.umass.edu/ece/koren/architecture/Raid/basicRAID.html</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Herlihy, Maurice (January 1991). "Wait-Free Synchronization" (PDF). ACM Transactions on Programming Languages and Systems. 11 (1): 124–149. doi:10.1145/114005.102808. S2CID 2181446. Archived (PDF) from the original on 5 June 2011. Retrieved 19 December 2011. <a href="http://www.cs.brown.edu/~mph/Herlihy91/p124-herlihy.pdf" target="_blank">http://www.cs.brown.edu/~mph/Herlihy91/p124-herlihy.pdf</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Imbs, Damien; Raynal, Michel (25 July 2010). "The multiplicative power of consensus numbers" (PDF). Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing. Association for Computing Machinery. pp. 26–35. doi:10.1145/1835698.1835705. ISBN 978-1-60558-888-9. S2CID 3179361. Archived (PDF) from the original on 27 January 2022. Retrieved 22 April 2021. <a href="978-1-60558-888-9" target="_blank">978-1-60558-888-9</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>Fich, Faith; Hendler, Danny; Shavit, Nir (25 July 2004). "On the inherent weakness of conditional synchronization primitives". Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing. Association for Computing Machinery. pp. 80–87. CiteSeerX 10.1.1.96.9340. doi:10.1145/1011767.1011780. ISBN 1-58113-802-4. S2CID 9313205. <a href="1-58113-802-4" target="_blank">1-58113-802-4</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>Herlihy, Maurice (January 1991). "Wait-Free Synchronization" (PDF). ACM Transactions on Programming Languages and Systems. 11 (1): 124–149. doi:10.1145/114005.102808. S2CID 2181446. Archived (PDF) from the original on 5 June 2011. Retrieved 19 December 2011. <a href="http://www.cs.brown.edu/~mph/Herlihy91/p124-herlihy.pdf" target="_blank">http://www.cs.brown.edu/~mph/Herlihy91/p124-herlihy.pdf</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> </ol>