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.

Implementing P with Bounded Messages on a Network of ADD Channels

    We present an implementation of the eventually perfect failure detector (P) from the original hierarchy of the Chandra-Toueg [3] oracles on an arbitrary partitionable network composed of unreliable channels that can lose and reorder messages. Prior implementations of P have assumed different partially synchronous models ranging from bounded point-to-point message delay and reliable communication to unbounded message size and known network topologies. We implement P under very weak assumptions on an arbitrary, partitionable network composed of Average Delayed/Dropped (ADD) channels [11] to model unreliable communication. Unlike older implementations, our failure detection algorithm uses bounded-sized messages to eventually detect all nodes that are unreachable (crashed or disconnected) from it.

    References

    • 1. M. K. Aguilera, W. Chen and S. Toueg, Using the heartbeat failure detector for quiescent reliable communication and consensus in partitionable networks, Theoretical Computer Science 220(1) (1999) 3–30. Crossref, ISIGoogle Scholar
    • 2. C. Fernandez-Campusano, R. Cortinas and M. Larrea, A performance study of consensus algorithms in omission and crash-recovery scenarios, PDP 2014, 240–243. Google Scholar
    • 3. T. D. Chandra and S. Toueg, Unreliable failure detectors for reliable distributed systems, Journal of the ACM 43 (1996) 225–267. Crossref, ISIGoogle Scholar
    • 4. W. Chen, S. Toueg and M. K. Aguilera, On the quality of service of failure detectors, IEEE Trans. Computers 51(5) (2002) 561–580. Crossref, ISIGoogle Scholar
    • 5. M. J. Fischer, N. A. Lynch and M. Paterson, Impossibility of distributed consensus with one faulty process, J. ACM 32(2) (1985) 374–382. Crossref, ISIGoogle Scholar
    • 6. P. Fraigniaud, S. Rajsbaum, C. Travers, P. Kuznetsov and T. Rieutord, Perfect failure detection with very few bits, SSS 2016, 154–169. Google Scholar
    • 7. F. C. Freiling, R. Guerraoui and P. Kuznetsov, The failure detector abstraction, ACM Comput. Surv. 43(2) (2011) 9:1–9:40. Crossref, ISIGoogle Scholar
    • 8. M. Hutle, An efficient failure detector for sparsely connected networks, Parallel and Distributed Computing and Networks 2004, pp. 369–374. Google Scholar
    • 9. E. Jimenez, S. Arevalo and A. Fernandez, Implementing unreliable failure detectors with unknown membership, Inf. Process. Lett. 100(2) (2006) 60–63. Crossref, ISIGoogle Scholar
    • 10. R. van Renesse, Y. Minsky and M. Hayden, A gossip-style failure detection service, in Middleware, eds. N. DaviesS. JochenK. Raymond (Springer, London, 1998). CrossrefGoogle Scholar
    • 11. S. Sastry and S. Pike, Eventually perfect failure detectors using ADD channels, in IEEE Int. Symp. on Parallel and Distributed Processing with Applications (2007), pp. 483–496. Google Scholar