Building an infrastructure for exascale applications requires, in addition to many other key components, a stable and efficient failure detector. This article describes the design and evaluation of a robust failure detector that can maintain and distribute the correct list of alive resources within proven and scalable bounds. The detection and distribution of the fault information follow different overlay topologies that together guarantee minimal disturbance to the applications. A virtual observation ring minimizes the overhead by allowing each node to be observed by another single node, providing an unobtrusive behavior. The propagation stage uses a nonuniform variant of a reliable broadcast over a circulant graph overlay network and guarantees a logarithmic fault propagation. Extensive simulations, together with experiments on the Titan Oak Ridge National Laboratory supercomputer, show that the algorithm performs extremely well and exhibits all the desired properties of an exascale-ready algorithm.
AngskunTBosilcaGDongarraJ (2007) Binomial graph: a scalable and fault-tolerant logical network topology. In: StojmenovicIThulasiramRKYangLTJiaWGuoMde MelloRF (eds) Parallel and Distributed Processing and Applications ISPA, Berlin: Springer, pp. 471–482.
2.
BertierMMarinOSensP (2003) Performance analysis of a hierarchical failure detector. In: Proceedings of theInternational Conference on Dependable Systems and Networks, 22–25 June 2003San Francisco, CA, 2003, pp. 635–644.
3.
BhatPBRaghavendraCSPrasannaVK (2003) Efficient collective communication in distributed heterogeneous systems. Journal Parallel and Distributed Computing63(3): 251–263.
4.
BlandWBouteillerAHeraultT. (2013a) An evaluation of user-level failure mitigation support in MPI. Computing95(12): 1171–1184.
ChandraTDTouegS (1996) Unreliable failure detectors for reliable distributed systems. Journal of the ACM43(2): 225–267.
8.
ChenWTouegSAguileraMK (2002) On the quality of service of failure detectors. IEEE Transactions Computers51(5): 561–580.
9.
DasAGuptaIMotivalaA (2002) Swim: Scalable weakly-consistent infection-style process group membership protocol. In: International Conference on Dependable Systems and Networks, 23–26 June 2002Washington, DC, USA, 2002, pp. 303–312.
10.
EgwutuohaIPLevyDSelicB. (2013) A survey of fault tolerance mechanisms and checkpoint/restart implementations for high performance computing systems. The Journal of Supercomputing65(3): 1302–1326.
11.
FerreiraKBBridgesPBrightwellR (2008) Characterizing application sensitivity to OS interference using kernel-level noise injection. In: Proceeding SC‘08, IEEE Computer Society Press, 2008. 15–21 Nov. 2008, Austin, TX, USA: IEEE.
12.
FraigniaudP (1992) Asymptotically optimal broadcasting and gossiping in faulty hypercube multicomputers. IEEE Transactions Computers41(11): 1410–1419.
13.
GuptaIChandraTDGoldszmidtGS (2001) On scalable and efficient distributed failure detectors. In: Proceedings of the Twentieth Annual ACM Symposium on Principles of Distributed Computing, PODC’01, New York, NY, USA, 2001, pp. 170–179. ACM. DOI: 10.1145/383962.384010.
14.
HayashibaraNCherifAKatayamaT (2002) Failure detectors for large-scale distributed systems. In: 21st Symposium on Reliable Distributed Systems (SRDS 2002), Osaka, Japan, 13–16 October 2002, pp. 404–409. DOI:10.1109/RELDIS.2002.1180218.
15.
HeraultTBouteillerABosilcaG. (2015) Practical scalable consensus for pseudo-synchronous distributed systems. In: Proceeding. SC’15, IEEE Computer Society Press, 2015. Austin, Texas — November 15–20, 2015.
16.
HéraultTRobertY (2015) Fault-tolerance techniques for high-performance computing. In: HéraultTRobertY (eds) Computer Communications and Networks. Verlag: Springer, 2015.
17.
HeydemannMC (1997) Cayley graphs and interconnection networks. In: HahnGSabidussiG (eds) Graph Symmetry: Algebraic Methods and Applications, Springer, 1997, pp. 167–224.
18.
HoeflerTSchneiderTLumsdaineA (2010) Characterizing the influence of system noise on large-scale applications by simulation. In: Proceeding. SC‘10, IEEE Computer Society Press, 2010.
19.
HoritaYTauraKChikayamaT (2005) A scalable and efficient self-organizing failure detector for grid applications. In: Proceedings of the 6th IEEE/ACM International Workshop on Grid Computing, GRID’05, Washington, DC, USA, 2005, pp. 202–210. IEEE Computer Society.
20.
KattiADi FattaGNaughtonT. (2015) Scalable and fault tolerant failure detection and consensus. In: Proceeding. EuroMPI’15, 2015. ACM.
KrishnamoorthyMKrishnamurthyB (1987) Fault diameter of interconnection networks. Computers & Mathematics with Applications13(5–6): 577–582.
23.
LarreaMFernándezAArévaloS (2000) Optimal implementation of the weakest failure detector for solving consensus. In: Proceedings, 2000, 19th IEEE Symposium on Reliable Distributed Systems, SRDS’00, Nürnberg, Germany, 16–18 October 2000, pp. 52–59.
24.
LiawSCChangGJCaoF. (1998) Fault-tolerant routing in circulant networks and cycle prefix networks. Annals of Combinatorics2(2): 165–172.
25.
MitzenmacherMUpfalE (2005) Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge: Cambridge University Press.
26.
PelcA (1996) Fault-tolerant broadcasting and gossiping in communication networks. Networks28(3): 143–156.
SnyderSCarnsPHJenkinsJ. (2014) A case for epidemic fault detection and group membership in HPC storage systems. In: 5th Int. Workshop on Performance Modeling, Benchmarking, and Simulation (PMBS), LNCS 8966, 2014, pp. 237–248. Springer.
TockYMandlerBMoreiraJE. (2013) Design and implementation of a scalable membership service for supercomputer resiliency-aware runtime. In: Proceedings, 2013, Processing – 19th International Conference Euro-Par 2013 Parallel, Aachen, Germany, 26–30 August 2013, pp. 354–366. DOI:10.1007/978-3-642-40047-6_37.
31.
van RenesseRMinskyYHaydenM (1998) A gossip-style failure detection service. In: Proceedings of the IFIP International Conference on Distributed Systems Platforms and Open Distributed Processing, Middleware ‘98, London, UK, 1998, pp. 55–70. Springer-Verlag. URL http://dl.acm.org/citation.cfm?id=1659232.1659238.
