| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Constructing a Reliable Test&Set Bit
March 1999 (vol. 10 no. 3)
pp. 252-265
Abstract—The problem of computing with faulty shared bits is addressed. The focus is on constructing a reliable test&set bit from a collection of test&set bits of which some may be faulty. Faults are modeled by allowing operations on the faulty bits to return a special distinguished value, signaling that the operation may not have taken place. Such faults are called omission faults. Some of the constructions are required to be gracefully degrading for omission. That is, if the bound on the number of component bits which fail is exceeded, the constructed bit may suffer faults, but only faults which are no more severe than those of the components; and the constructed bit behaves as intended if the number of component bits which fail does not exceed that bound. Several efficient constructions are presented, and bounds on the space required are given. Our constructions for omission faults also apply to other fault models.
[1] Y. Afek, D. Greenberg, M. Merritt,, and G. Taubenfeld, “Computing with Faulty Shared Memory,” Proc. 11th Ann. ACM Symp. Principles of Distributed Computing, pp. 47-58, Aug. 1992.
[2] Y. Afek, D. Greenberg, M. Merritt,, and G. Taubenfeld, “Computing with Faulty Shared Memory,” J. ACM, vol. 42, no. 6, pp. 1,231-1,274, Nov. 1995.
[3] Y. Afek, M. Merritt,, and G. Taubenfeld, “Benign Failure Models for Shared Memory (Preliminary Version),” Proc. Seventh Int'l Workshop Distributed Algorithms, pp. 69-83, Sept. 1993.
[4] E.W. Dijkstra,“Self-stabilizing systems in spite of distributed control,” Comm. ACM, vol. 17, no. 11 pp. 643-644, 1974,.
[5] M.J. Fischer, S. Moran, S. Rudich,, and G. Taubenfeld, “The Wakeup Problem,” SIAM J. Computing, vol. 25, no. 6, pp. 1,332-1,357, Dec. 1996. Also in Proc. 31st IEEE Ann. Symp. Foundations of Computer Science, pp. 106-116, Oct. 1990.
[6] P. Jayanti, T. Chandra,, and S. Toueg, “Fault-Tolerant Wait-Free Shared Objects,” Proc. 33rd IEEE Ann. Symp. Foundation of Computer Science, Oct. 1992. (Older version of [7].)
[7] P. Jayanti, T. Chandra,, and S. Toueg, “Fault-Tolerant Wait-Free Shared Objects,” J. ACM, vol. 45, no. 3, pp. 451-500, May 1998.
[8] M. Herlihy, “Wait-Free Synchronization,” ACM Trans. Programming Languages and Systems, vol. 13, no. 1,pp. 124-149, 1991.
[9] M. Herlihy and J. Wing, “Linearizability: A Correctness Condition for Concurrent Objects,” ACM Trans. Programming Languages and Systems, vol. 12, no. 3,pp. 463-492, 1990.
[10] L. Lamport, “On Interprocess Communication, Parts I and II,” Distributed Computing, vol. 1, pp. 77-101, 1986.
[11] M.C. Loui and H.H. Abu-Amara, “Memory Requirements for Agreement Among Unreliable Asynchronous Processes,” Advances in Computing Research, vol. 4, pp. 163-183, 1987.
[12] M. Schneider, “Self-Stabilization,” ACM Computing Surveys, vol. 25, no. 1, pp. 45-67, Mar. 1993.
Index Terms:
Test&set bits, reliability, omission faults, gracefully degradation, wait-free algorithms.
Citation:
Frank Stomp, Gadi Taubenfeld, "Constructing a Reliable Test&Set Bit," IEEE Transactions on Parallel and Distributed Systems, vol. 10, no. 3, pp. 252-265, Mar. 1999, doi:10.1109/71.755825
