7.12 Additional Reading

Early versions of the ring project described in this chapter can be found in [95]. A simulator that explores the interaction between pipes and forks is discussed in [97]. This simulator can be run either locally or from the Web and is available on the book web site. Local and Metropolitan Area Networks , 6th ed. by Stallings [111] has a good discussion of the token ring, token bus and FDDI network standards. Each of these networks is based on a ring architecture. Stallings also discusses the election methods used by these architectures for token regeneration and reconfiguration. The paper "A resilient mutual exclusion algorithm for computer networks" by Nishio et al. [88] analyzes the general problem of regenerating lost tokens in computer networks.

The theoretical literature on distributed algorithms for rings is large. The algorithms of Section 7.6 are based on a paper by Chang and Roberts [22], and the algorithms of Section 7.7 are discussed in Itai and Roteh [58]. A nice theoretical article on anonymous rings is "Computing on an anonymous ring" by Attiya et al. [7]. Introduction to Parallel Computing : Design and Analysis of Algorithms by Kumar et al. [67] presents a good overview of parallel algorithms and a discussion of how to map these algorithms onto particular machine architectures.