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.

A TIME-FREE ASSUMPTION TO IMPLEMENT EVENTUAL LEADERSHIP

    Leader-based protocols rest on a primitive able to provide the processes with the same unique leader. Such protocols are very common in distributed computing to solve synchronization or coordination problems. Unfortunately, providing such a primitive is far from being trivial in asynchronous distributed systems prone to process crashes. (It is even impossible in fault-prone purely asynchronous systems.) To circumvent this difficulty, several protocols have been proposed that build a leader facility on top of an asynchronous distributed system enriched with synchrony assumptions. This paper introduces a novel approach to implement an eventual leader protocol, namely a time-free behavioral assumption on the flow of messages that are exchanged. It presents a very simple leader protocol based on this assumption. It then presents a second leader protocol combining this timeless assumption with eventually timely channels. As it considers several assumptions, the resulting hybrid protocol has the noteworthy feature to provide an increased overall assumption coverage. A probabilistic analysis shows that the time-free assumption is practically always satisfied.

    References

    • M. K. Aguileraet al., On Implementing Omega with Weak Reliability and Synchrony Assumptions, Proc. 22th ACM Symposium on Principles of Distributed Computing (PODC'03) (ACM Press, 2003) pp. 306–314. Google Scholar
    • M. K. Aguileraet al., Communication-Efficient Leader Election and Consensus with Limited Link Synchrony, Proc. 23th ACM Symposium on Principles of Distributed Computing (PODC'04) (ACM Press, 2004) pp. 328–337. Google Scholar
    • E. Anceaumeet al., Journal of Computer and System Sciences 68, 123 (2004). Crossref, ISIGoogle Scholar
    • T. D. Chandra and S. Toueg, Journal of the ACM 43(2), 225 (1996). Crossref, ISIGoogle Scholar
    • T. D. Chandra, V. Hadzilacos and S. Toueg, Journal of the ACM 43(4), 685 (1996). Crossref, ISIGoogle Scholar
    • C. Dwork, N. Lynch and L. Stockmeyer, Journal of the ACM 35(2), 288 (1988). Crossref, ISIGoogle Scholar
    • C. Fetzer, M. Raynal and F. Tronel, An Adaptive Failure Detection Protocol, Proc. 8th IEEE Pacific Rim Int'l Symposium on Dependable Computing (PRDC'01) (IEEE Computer Society Press, 2001) pp. 146–153. Google Scholar
    • M. J. Fischer, N. Lynch and M. S. Paterson, Journal of the ACM 32(2), 374 (1985). Crossref, ISIGoogle Scholar
    • R. Guerraoui, Indulgent Algorithms, Proc. 19th ACM Symposium on Principles of Distributed Computing, (PODC'00) (ACM Press, 2000) pp. 289–298. Google Scholar
    • R. Guerraoui and M. Raynal, IEEE Transactions on computers 53(4), 453 (2004). Crossref, ISIGoogle Scholar
    • N. Hayashibaraet al., The ϕ Accrual Failure Detector, Proc. 23th IEEE Symposium on Reliable Distributed Systems (SRDS'04) (IEEE Computer Society Press, 2004) pp. 66–78. Google Scholar
    • L. Lamport, ACM Transactions on Computer Systems 16(2), 133 (1998). Crossref, ISIGoogle Scholar
    • M. Larrea, A. Fernandez and S. Arevalo, Optimal Implementation of the Weakest Failure Detector for Solving Consensus, Proc. 19th Symposium on Reliable Distributed Systems (SRDS'00) (IEEE Computer Society Press, 2000) pp. 52–60. Google Scholar
    • A. Mostefaoui, E. Mourgaya and M. Raynal, Future Generation Computer Systems 18(6), 757 (2002). Crossref, ISIGoogle Scholar
    • A. Mostefaoui, E. Mourgaya and M. Raynal, Asynchronous Implementation of Failure Detectors, Proc. Int. IEEE Conference on Dependable Systems and Networks (DSN'03) (IEEE Computer Society Press, 2003) pp. 351–360. Google Scholar
    • A. Mostefaoui, D. Powell and M. Raynal, A Hybrid Approach for Building Eventually Accurate Failure Detectors, Proc. 10th IEEE Int. Pacific Rim Dependable Computing Symposium (PRDC'04) (IEEE Computer Society Press) pp. 57–65. Google Scholar
    • A. Mostefaoui and M. Raynal, Low-Cost Consensus-Based Atomic Broadcast, 7th IEEE Pacific Rim Int. Symposium on Dependable Computing (PRDC'2000) (IEEE Computer Society Press, 2000) pp. 45–52. Google Scholar
    • A. Mostefaoui and M. Raynal, Parallel Processing Letters 11(1), 95 (2001). LinkGoogle Scholar
    • A. Mostefaoui, M. Raynal and C. Travers, Crash-Resilient Time-free Eventual Leader-ship, Proc. 23th IEEE Symposium on Reliable Distributed Systems (SRDS'04) (IEEE Computer Society Press, 2004) pp. 208–217. Google Scholar
    • D. Powell, Failure Mode Assumptions and Assumption Coverage, Proc. of the 22nd Int. Symp. on Fault-Tolerant Computing (FTCS-22) (1992) pp. 386–395. Google Scholar