World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

AN ORDER DEGREE ALTERNATOR FOR ARBITRARY TOPOLOGIES

    An alternator is an arbitrary set of interacting processes that satisfies three conditions. First, if a process executes its critical section, then no neighbor of that process can execute its critical section at the same state. Second, along any infinite sequence of system states, each process will execute its critical section, an infinite number of times. Third, along any maximally concurrent computation, the alternator will stabilize to a sequence of states in which the processes will execute their critical sections in alternation. A principal reason for interest in alternators is their ability to transform systems correct under serial execution semantics to systems that are correct under concurrent execution semantics. An earlier alternator for arbitrary topology required 2q states where q is the dependency graph circumference and after stabilization would wait 2q steps between critical section executions. In a synchronous environment, this alternator requires only 2d+1 states where d is the degree of the graph of process dependencies for the system and after stabilization will require a wait of 2d+1 steps between critical section executions. In an asynchronous environment, the synchronization properties of this alternator must be supplemented with an asynchronous unison algorithm. The asynchronous unison algorithm requires expansion of the required number of states to dt, where t is the longest chordless cycle in the dependency graph; however, the required wait between critical section executions remains O(d).

    References

    • Mohamed G. Gouda and Furman Haddix, The Linear Alternator, Proceedings of 2nd Workshop on Self-Stabilizing Systems (1997) pp. 31–47. Google Scholar
    • Mohamed G. Gouda and Furman Haddix, The Alternator, Proceedings of 3rd Workshop on Self-Stabilizing Systems (1999) pp. 48–53. Google Scholar
    • Tzong-Jye Liu and Chia-Lin Lee, 2-state alternator for uniform rings with arbitrary size, 19th International Conference on Advanced Information Networking and Applications1 (2005) pp. 847–852. Google Scholar
    • Colette Johnenet al., Self-Stabilizing Neighborhood Synchronizer in Tree Networks, International Conference on Distributed Computing Systems (1999) pp. 487–494. Google Scholar
    • Colette Johnen and Luc O. Alima, Parallel Processing Letters6 (2002) pp. 327–340. Google Scholar
    • Mohamed G.   Gouda and Furman   Haddix , Tree-Embedded Alternators: Trees, Rings, Grids, and Hypercubes , International Seminar about Self-Stabilizing Systems ( Luminy , 2004 ) . Google Scholar
    • Mikhail Nesterenko and Anish Arora, Journal of Parallel and Distributed Computing 52, 766 (2002). Google Scholar
    • S. S. Kulkarniet al., Information Processing Letters 93, 207 (2005), DOI: 10.1016/j.ipl.2004.11.009. Crossref, ISIGoogle Scholar
    • C. Boulinier, F. Petit and V. Villain, When Graph Theory Helps Self-Stabilization, Proceedings of the Twenty-third Annual ACM Symposium on Principles of Distributed Computing (2004) pp. 150–159. Google Scholar
    • Furman Haddix, "Chapter 3. Tree and Grid Alternators", Alternating Parallelism and the Stabilization of Distributed Systems, Dissertation, Department of Computer Sciences, The University of Texas at Austin, (1999), pp. 27-50 . Google Scholar
    • Shlomi Dolev, Amos Israeli and Shlomo Moran, Proceedings of the Ninth Annual ACM Symposium on Principles of Distributed Computing (1990) pp. 103–117. Google Scholar
    • Rajeev Alur and Thomas A. Henzinger, ACM Transactions on Programming Languages and Systems 20, 1171 (1998), DOI: 10.1145/295656.295659. Crossref, ISIGoogle Scholar
    • J. Couvreur, N. Francez and M. Gouda, Asynchronous Unison, Proceedings of the 12th International Conference on Distributed Computing Systems (1992) pp. 486–493. Google Scholar