dorian

Information about dorian

Published on November 19, 2007

Author: Rafael

Source: authorstream.com

Content

Scalable Failure Recovery for Tree-based Overlay Networks:  Scalable Failure Recovery for Tree-based Overlay Networks Dorian C. Arnold University of Wisconsin Paradyn/Condor Week April 30 – May 3, 2007 Madison, WI Overview:  Overview Motivation Address the likely frequent failures in extreme-scale systems State Compensation: Tree-Based Overlay Networks (TBŌNs) failure recovery Use surviving state to compensate for lost state Leverage TBŌN properties Inherent information redundancies Weak data consistency model: convergent recovery Final output stream converges to non-failure case Intermediate output packets may differ Preserves all output information HPC System Trends:  HPC System Trends 60% larger than 103 processors 10 systems larger than 104 processors Large Scale System Reliability :  Large Scale System Reliability Purple BlueGene/L Current Reliability Approaches:  Current Reliability Approaches Fail-over (hot backup) Replace failed primary w/ backup replica Extremely high overhead: 100% minimum! Rollback recovery Rollback to checkpoint after failure May require dedicated resources and lead to overloaded network/storage resources Our Approach: State Compensation:  Our Approach: State Compensation Leverage inherent TBŌN redundancies Avoid explicit replication No overhead during normal operation Rapid recovery Limited process participation General recovery model Applies to broad classes of computations Background: TBŌN Model:  Background: TBŌN Model FE Application Front-end Application Back-ends BE BE BE BE BE BE BE BE TBŌN Input TBŌN Output A Trip Down Theory Lane:  A Trip Down Theory Lane Formal treatment provides confidence in recovery model Reason about semantics before/after recovery Recovery model doesn’t change computation Prove algorithmic soundness Understand recovery model characteristics System reliability cannot depend upon intuition and ad-hoc reasoning Theory Overview:  Theory Overview TBŌN end-to-end argument: output only depends on state at the end-points Can recover from lost of any internal filter and channel states CPi CPk CPl CPj channel state channel state filter state Theory Overview (cont’d):  Theory Overview (cont’d) CPi CPk CPl CPj channel state channel state filter state TBŌN Output Theorem Output depends only on channel states and root filter state All-encompassing Leaf State Theorem State at leaves subsume channel state (all state throughout TBŌN) Result: only need leaf state to recover from root/internal failures Theory Overview (cont’d):  Theory Overview (cont’d) TBON Output Theorem All-encompassing Leaf State Theorem Builds on Inherent Redundancy Theorem Background: Notation:  Background: Notation CPi CPk CPl CPj csn,p( CPi ) cs( CPj ) fsp(CPj ) fsn(CPi ) Background: Data Aggregation:  Background: Data Aggregation Filter function: Packets from input channels Current filter state Output packet Updated filter state Background: Filter Function:  Background: Filter Function Built on state join and difference operators State join operator, Update current state by merging inputs Commutative: Associative: Idempotent: Background: Descendant Notation:  Background: Descendant Notation CPi CP CP CP CP CP CP CP CP … … desc0(CPi ) desc1(CPi ) desck(CPi ) desck-1(CPi ) fs( desck(CPi ) ): join of filter states of specified processes cs( desck(CPi ) ): join of channel states of specified processes TBŌN Properties: Inherent Redundancy Theorem:  TBŌN Properties: Inherent Redundancy Theorem The join of a CP’s filter state with its pending channel state equals the join of the CP’s children’s filter states. CP1 CP2 CP0 fsn(CP0 ) fsq(CP2 ) fsp(CP1 ) csn,p(CP0 ) csn,q(CP0 ) = The join of a CP’s filter state with its pending channel state equals the join of the CP’s children’s filter states. The join of a CP’s filter state with its pending channel state equals the join of the CP’s children’s filter states. TBŌN Properties: Inherent Redundancy Theorem:  TBŌN Properties: Inherent Redundancy Theorem The join of a CP’s filter state with its pending channel state equals the join of the CP’s children’s filter states. CP1 CP2 CP0 fs( desc1(CP0 )) cs( desc0(CP0)) = fs( desc0(CP0 )) TBŌN Properties: All-encompassing Leaf State Theorem:  TBŌN Properties: All-encompassing Leaf State Theorem The join of the states from a sub-tree’s leaves equals the join of the states at the sub-tree’s root and all in-flight data CP5 CP6 CP2 CP0 CP3 CP4 CP1 The join of the states from a sub-tree’s leaves equals the join of the states at the sub-tree’s root and all in-flight data TBŌN Properties: All-encompassing Leaf State Theorem:  TBŌN Properties: All-encompassing Leaf State Theorem The join of the states from a sub-tree’s leaves equals the join of the states at the sub-tree’s root and all in-flight data From Inherent Redundancy Theorem: … State Composition:  State Composition Motivated by previous theory State at leaves of a sub-tree subsume state throughout the higher levels Compose state below failure zones to compensate for lost state Addresses root and internal failures State decomposition for leaf failures Generate child state from parent and sibling’s State Composition:  State Composition CPi CPk CPl CPj cs( CPi , m) cs( CPj ) fs(CPj ) If CPj fails, all state associated with CPj is lost TBŌN Output Theorem: Output depends only on channel states and root filter state All-encompassing Leaf State Theorem: State at leaves subsume channel state (all state throughout TBŌN) Therefore, leaf states can replace lost channel state without changing computation’s semantics State Composition Algorithm:  State Composition Algorithm if detect child failure remove failed child from input list resume filtering from non-failed children endif if detect parent failure do determine/connect to new parent while failure to connect propagate filter state to new parent endif Summary: Theory can be Good!:  Summary: Theory can be Good! Allows us to make recovery guarantees Yields sensible, understandable results Better-informed implementation What needs to be implemented What does not need to be implemented References:  References Arnold and Miller, “State Compensation: A Scalable Failure Recovery Model for Tree-based Overlay Networks”, UW-CS Technical Report, February 2007. Other papers and software: http://www.paradyn/org/mrnet Slide25:  Bonus Slides! State Composition Performance:  State Composition Performance LAN connection establishment: ~1 millisecond Failure Model:  Failure Model Fail-stop Multiple, simultaneous failures Failure zones: regions of contiguous failure Application process failures May view as sequential data sources/sink Amenable to basic reliability mechanisms Simple restart, sequential checkpointing

Related presentations


Other presentations created by Rafael

specsavers
07. 11. 2007
0 views

specsavers

The Great Years 1945 1965
28. 12. 2007
0 views

The Great Years 1945 1965

20 best practices
01. 10. 2007
0 views

20 best practices

ArcSpiral
24. 10. 2007
0 views

ArcSpiral

fg04
28. 11. 2007
0 views

fg04

TD10 WS item6 IssuesNGN IMS
28. 11. 2007
0 views

TD10 WS item6 IssuesNGN IMS

brown ligo
29. 11. 2007
0 views

brown ligo

independence
07. 12. 2007
0 views

independence

plant types
11. 12. 2007
0 views

plant types

inf emerg arih 29092005
25. 10. 2007
0 views

inf emerg arih 29092005

BowcockNewZealand
30. 10. 2007
0 views

BowcockNewZealand

8thICSR 286 Gurrieri310806
31. 10. 2007
0 views

8thICSR 286 Gurrieri310806

westnilevirus 071205
24. 10. 2007
0 views

westnilevirus 071205

lecture8
14. 11. 2007
0 views

lecture8

16 ProductBrandMgmt1
16. 11. 2007
0 views

16 ProductBrandMgmt1

1TTplan2
17. 12. 2007
0 views

1TTplan2

ShipOrg
05. 11. 2007
0 views

ShipOrg

Word 2002 tut05 edited
06. 12. 2007
0 views

Word 2002 tut05 edited

Vegetation Presentation
07. 01. 2008
0 views

Vegetation Presentation

the punic wars
31. 10. 2007
0 views

the punic wars

s433 bu
29. 10. 2007
0 views

s433 bu

Egypt3 25 05
22. 11. 2007
0 views

Egypt3 25 05

abc5lc
27. 12. 2007
0 views

abc5lc

Hurault PlantetPresentation
01. 11. 2007
0 views

Hurault PlantetPresentation

CHI2006 sgaw
04. 01. 2008
0 views

CHI2006 sgaw

Lindroos beta beam MWATT
25. 10. 2007
0 views

Lindroos beta beam MWATT

trill 4
28. 12. 2007
0 views

trill 4

Arvind Singhal1
20. 02. 2008
0 views

Arvind Singhal1

L4 Community
24. 02. 2008
0 views

L4 Community

CSULB SCAG Forecast
27. 02. 2008
0 views

CSULB SCAG Forecast

Developing a Healthy Lifestyle
05. 03. 2008
0 views

Developing a Healthy Lifestyle

Pierre Rolin
14. 03. 2008
0 views

Pierre Rolin

Paradox
03. 10. 2007
0 views

Paradox

Lerch
30. 03. 2008
0 views

Lerch

2007 GameOn
06. 11. 2007
0 views

2007 GameOn

Kubalkeynote507LasVe gas
13. 04. 2008
0 views

Kubalkeynote507LasVe gas

celadrin
19. 11. 2007
0 views

celadrin

Vegetation of Little Cayman
02. 01. 2008
0 views

Vegetation of Little Cayman

NFerrari
03. 12. 2007
0 views

NFerrari

LeeSchoolPowerPoint01
14. 11. 2007
0 views

LeeSchoolPowerPoint01

PhenixDanceDemo
28. 11. 2007
0 views

PhenixDanceDemo

510863 CrossCheck
28. 11. 2007
0 views

510863 CrossCheck

LYMAN
31. 10. 2007
0 views

LYMAN

13 genetica di popolazione
03. 01. 2008
0 views

13 genetica di popolazione

2001 10 31 Finger Search
02. 11. 2007
0 views

2001 10 31 Finger Search

menten
15. 11. 2007
0 views

menten

bhattacharyya
29. 11. 2007
0 views

bhattacharyya

ovdza5bxdivpc7y
25. 10. 2007
0 views

ovdza5bxdivpc7y

LMallon05022007
06. 11. 2007
0 views

LMallon05022007

vylkan1
09. 10. 2007
0 views

vylkan1

Present Paola
18. 12. 2007
0 views

Present Paola

XLM H
13. 12. 2007
0 views

XLM H

potapova etal iafpa2006
27. 09. 2007
0 views

potapova etal iafpa2006

ParentsandPeersTPP
28. 12. 2007
0 views

ParentsandPeersTPP

57011 Week1 Slides
26. 11. 2007
0 views

57011 Week1 Slides