2011/01/09 by Ted Herman, Herman, Ted
Computer Science · Medicine · #Automotive and Human Injury Biomechanics #D.1.3 #D.4.1 #Distributed #FOS: Computer and information sciences #H.3.4 #Parallel #and Cluster Computing (cs.DC) #cs.DC
paper · pdf · doi:10.48550/arxiv.1101.1680
22 pages
arxiv created 2011/01/09 · openalex publication_date 2011/01/09 · arxiv updated 2011/01/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A token ring is an arrangement of N processors that take turns engaging in an activity which must be controlled. A token confers the right to engage in the controlled activity. Processors communicate with neighbors in the ring to obtain and release a token. The communication mechanism investigated in this paper is the safe register abstraction, which may arbitrarily corrupt a value that a processor reads when the operation reading a register is concurrent with an write operation on that register by a neighboring processor. The main results are simple protocols for quasi-atomic communication, constructed from safe registers. A quasi-atomic register behaves atomically except that a special undefined value may be returned in the case of concurrent read and write operations. Under certain conditions that constrain the number of writes and registers, quasi-atomic protocols are adequate substitutes for atomic protocols. The paper demonstrates how quasi-atomic protocols can be used to implement a self-stabilizing token ring, either by using two safe registers between neighboring processors or by using O(lg N) safe registers between neighbors, which lowers read complexity.