Editing Mutual exclusion (section)

==Bound on the mutual exclusion problem==

One binary [[Test-and-set|test&set]] register is sufficient to provide the deadlock-free solution to the mutual exclusion problem. But a solution built with a test&set register can possibly lead to the starvation of some processes which become caught in the trying section.<ref name="Distributed computing: fundamentals, simulations, and advanced topics"/> In fact, <math>\Omega(\sqrt{n})</math> distinct memory states are required to avoid lockout. To avoid unbounded waiting, ''n'' distinct memory states are required.<ref>{{Citation | url=http://research.microsoft.com/en-us/um/people/lamport/pubs/mutual2.pdf | last=Burns |first=James E. |author2 = Paul Jackson, Nancy A. Lynch| title =Data Requirements for Implementation of N-Process Mutual Exclusion Using a Single Shared Variable  | journal=Journal of the Association for Computing Machinery |date = January 1982| volume=33 | issue=2 | pages=313–348 }}</ref>