Perturbation resilient atomic commit protocols for mobile environments [Elektronische Ressource] / vorgelegt von Brahim Ayari

Brahim Ayari

Description

Perturbation-Resilient Atomic Commit Protocols forMobile EnvironmentsVom Fachbereich Informatik der Technischen Universit at DarmstadtgenehmigteDissertationzur Erlangung des akademischen Grades eines Doktor-Ingenieur (Dr.-Ing.)vorgelegt vonDipl.-Inform. Brahim Ayariaus Tunis, TunesienReferenten:Prof. Neeraj Suri, Ph.D.Prof. Philip Koopman, Ph.D.Datum der Einreichung: 16. Juni 2010Datum der mundlic hen Prufung: 01. September 2010Darmstadt 2010D17iiAbstractThe support of distributed atomic transactions is a key requirement for manycurrent mobile applications. Atomicity is a fundamental property ensuring that allnodes reach a consistent outcome. For this, distributed mobile transactions fun-damentally require perturbation-resilient atomic commit protocols. This is chal-lenging as mobile environments are typically characterized by frequent networkand node perturbations. The environmental constraints on mobile transactionparticipants and wireless links may increase the resource blocking time of xedts. Moreover, frequent node and link failures complicate the design ofatomic commit protocols by increasing both the transaction abort rate and re-source blocking time. Hence, the deployment of classical commit protocols is notnecessarily applicable to distributed mobile environments.

Sujets

• Informatik

Informations

• Publié par: technischen_universitat_darmstadt
• Publié le: 01 janvier 2010
• Nombre de lectures: 57
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

Perturbation-ResilientAtomicCommitProtocolsfor
tsvironmenEnMobile

VomFachbereichInformatikderTechnischenUniversit¨atDarmstadt
genehmigte

Dissertation

zurErlangungdesakademischenGradeseinesDoktor-Ingenieur(Dr.-Ing.)
onvorgelegtv

ariAyBrahimDipl.-Inform.

ausunesienTunis,T

Prof.NeeraReferenjSuri,ten:Ph.D.
KoPhilipProf.Ph.D.opman,

DatumderDatumm¨undlicderhenEinreicPrh¨ufung:ung:16.01.SJunieptem2010ber2010

2010DarmstadtD17

ii

AbstractThesupportofdistributedatomictransactionsisakeyrequirementformany
currentmobileapplications.Atomicityisafundamentalpropertyensuringthatall
nodesreachaconsistentoutcome.Forthis,distributedmobiletransactionsfun-
damentallyrequireperturbation-resilientatomiccommitprotocols.Thisischal-
lengingasmobileenvironmentsaretypicallycharacterizedbyfrequentnetwork
andnodeperturbations.Theenvironmentalconstraintsonmobiletransaction
participantsandwirelesslinksmayincreasetheresourceblockingtimeoffixed
participants.Moreover,frequentnodeandlinkfailurescomplicatethedesignof
atomiccommitprotocolsbyincreasingboththetransactionabortrateandre-
sourceblockingtime.Hence,thedeploymentofclassicalcommitprotocolsisnot
necessarilyapplicabletodistributedmobileenvironments.Existingprotocolsen-
suringstrictatomicityinmobileenvironmentsareeitherboundtoverynarrowand
specificapplicationscenariosorhavepoorcommitrates,highmessageoverhead
orablockingbehavior.
Inordertocopewithdifferentapplicationscenarios,wefirstidentifythree
classesofmobileenvironments:infrastructure-based,ad-hocandgeneric.Fur-
thermore,weconsiderandcomprehensivelyclassifytheperturbationsofthewire-
lessmobileenvironmentintoclassesaccordingtotheirimpactontheoutcomeof
commitprotocolsandontheirblockingbehavior.Totoleratetheseperturbation
classes,perturbation-tolerantmechanismsareprovided.Basedonthesemecha-
nisms,wedevelopafamilyofperturbation-tolerantatomiccommitprotocolswith
minimalresourceblockingtimeandoptimizedtransactioncommitrates.
Fortheinfrastructure-basedmobileenvironment,weproposeanapproachthat
decouplesthecommitofmobileparticipantsfromthatoffixedparticipants–
beyondusingthestrengthsofexistingapproaches.Consequently,thecommitset
isreducedtoasetofentitiesinthefixednetwork.Thus,thecommitcaneasily
besupportedbyanytraditionalatomiccommitprotocol.Forthead-hocmobile
environment,wepresentacommitapproachthatsupportsasignificantlywider
rangeofmobilitypatternsandpartitioningscenariosthanexistingprotocols.Our
approachisbasedonanovelcoordinationstrategyusingaflexiblepreselectionof
multiplecoordinatorsamongtheparticipatingnodes.Thus,thefailureofasingle
coordinatoristoleratedinthepresenceofnetworkpartitioning.Forthegeneric
mobileenvironment,wedevelopanapproachthattakesadvantageofaccessing
thewiredinfrastructureifavailable,bychoosingreliableinfrastructurenodesfor
coordinatingtransactions.Iftheaccesstothewiredinfrastructureisunavailable,
ourapproachadaptsitselftotheresultingad-hocenvironment.
Weevaluatedourframeworkandthealgorithmspresentedinthisthesisvia
extensivesimulationsandexperiments.Theyvalidatedtheefficiencyandscala-
bilityofthedevelopedsolutionsandadditionallyemphasizedtheirresilienceto
theconsideredenvironmental,networkandnodeperturbationsbyminimizingre-
sourceblockingtimesandoptimizingtransactioncommitrates.Furthermore,they
confirmedthesuitabilityofoursolutionstoawiderangeofmobileapplications.

iii

iv

KurzfassungDieUnterst¨utzungverteilteratomarerTransaktionenisteineentscheidende
Voraussetzungf¨urvieleaktuellemobileApplikationen.Atomizit¨atisteinegrundle-
gendeEigenschaft,diegew¨ahrleistet,dassalleKnoteneinkonsistentesErgebnis
erreichen.UmdieAtomizit¨atverteiltermobilerTransaktionengew¨ahrleistenzu
k¨onnen,bedarfesst¨orungsresistenterCommit-Protokolle,damobileUmgebun-
gentypischerweisedurchh¨aufigeNetzwerk-undKnotenst¨orungengekennzeich-
netsind.DieumgebungsbedingtenBeschr¨ankungenbeimobilenTransaktionsteil-
nehmernunddrahtlosenVerbindungenk¨onnendieRessourcen-Blockierungszeit
vondrahtgebundenenstation¨arenTeilnehmernerh¨ohen.Dar¨uberhinauser-
schwerenh¨aufigeKnoten-undVerbindungsfehlerdieAnwendungkonventioneller
atomarerCommit-ProtokollendurchdieErh¨ohungsowohlderTransaktionsab-
bruchratealsauchderRessourcen-BlockierungszeitderTransaktion.Daheristder
EinsatzklassischerCommit-Protokollef¨urverteiltemobileUmgebungenalsnicht
empfehlenswertzuerachten.BestehendeProtokolle,dieeinestrikteAtomizit¨atin
mobilenUmgebungengew¨ahrleisten,sindentwederansehrbegrenzteundspezi-
fischeAnwendungsszenariengebundenodergehenmitniedrigenCommit-Raten,
hohemNachrichten-OverheadoderBlockierungsverhalteneinher.
UmdieAnwendbarkeitinunterschiedlicheSzenariensicherzustellen,identi-
fizierenwirzun¨achstdreiKlassenvonmobilenUmgebungen:Infrastruktur-basiert,
ad-hocundgenerisch.DesWeiterenklassifizierenwirm¨oglicheSt¨orungender
drahtlosenmobilenUmgebungentsprechendihrerAuswirkungaufdasErgeb-
nisderCommit-ProtokolleundaufderenBlockierungsverhalten.Umdiese
St¨orungsklassenzutolerieren,sindst¨orungstoleranteMechanismenvorgesehen.
BasierendaufdiesenMechanismenundunterBer¨ucksichtigungderidentifizierten
AnwendungsszenarienentwickelnwireineFamilievonst¨orungstolerantenatom-
arenCommit-ProtokollenmitminimalerRessourcen-Blockierungszeitundopti-
ransaktions-Commit-Raten.TmiertenF¨urdieInfrastruktur-basiertemobileUmgebungschlagenwireinenAnsatz
vor,derdieTransaktionsausf¨uhrungmobilerTeilnehmervonderstation¨arerTeil-
nehmerentkoppeltundderzwardieSt¨arkenbestehenderAns¨atzesubsumiert,
dabeiaber¨uberdieeinfacheVerwendungdieserAns¨atzehinausgeht.Dabeire-
duziertsichdasCommit-SetzueinemSetvonEinheitenimFestnetzundesk¨onnen
traditionelleatomareCommit-Protokolleleichteingesetztwerden.F¨urdieAd-
hoc-Umgebungpr¨asentierenwireinenAnsatz,dereinewesentlichbreitereReihe
vonMobilit¨atsmusternundPartitionierungsszenarienalsdiebestehendenPro-
tokolleunterst¨utzt.UnserAnsatzbasiertaufeinerneuenKoordinierungsstrategie
miteinerflexiblenVorauswahlvonmehrerenKoordinatorenunterdenbeteiligten
Knoten.SokannderAusfalleineseinzigenKoordinators,z.B.beieinerNetzwerk-
Partitionierung,toleriertwerden.F¨urdiegenerischeUmgebungentwickelnwir
einenAnsatz,derdenZugriffaufdiedrahtgebundeneInfrastruktur,fallsvorhan-
den,nutzt,indemzuverl¨assigeInfrastruktur-Knotenf¨urdieKoordinierungder
Transaktionenausgesuchtwerden.WennderZugriffaufdiedrahtgebundeneIn-

v

frastrukturnichtverf¨ugbarist,passtsichunserAnsatzandiedarausresultierende
an.c-UmgebungAd-hoUnserentwickeltesFrameworkunddieindieserArbeitvorgestelltenAlgorith-
menwurdendurchumfangreicheSimulationenundExperimenteevaluiert.Die
EvaluationsergebnissedemonstrierendieEffizienzundSkalierbarkeitderentwi-
ckeltenL¨osungenundbest¨atigenihreWiderstandsf¨ahigkeitgegen¨uberNetzwerk-
undKnoten-St¨orungendurchMinimierungderRessourcen-Blockierungszeitenund
OptimierungderTransaktions-Commit-Raten.Dar¨uberhinauszeigendieErgeb-
nissedieEignungunsererL¨osungenf¨ureinebreiteReihevonmobilenAnwen-
dungsszenarien.

vi

tswledgemenknoAcItisapleasuretothankallthepeoplewhohavehelped,guidedand
supportedmeinthesuccessfulcompletionofthisthesis.Withouttheir
contributions,thisresearchwouldnothavebeenpossible.

Mygreatestgratitudegoestomysupervisor,Prof.Dr.NeerajSuri,
whoseencouragement,guidanceandsupportfromtheinitialtothefinal
levelenabledmetodevelopanunderstandingofthesubject.Besidesthis,
heandwasadvicealwawyserepatienneeded.tandIwhouldelpfulliketowhenevthankerhisDr.Abencouragemedelmajidnt,Khelilsupforervisionhis
valuableadviceandinspiringdiscussionsonmyresearchwork.Agreatmany
thanksalsotoProf.PhilipKoopmanforacceptingtobemyco-advisor.

bers.Then,HopingIwnotouldtolikeforgettoanthankyoneallofpasttheandformerpresenandtcurrenDEEDStcolleges,group’smmanem-y
thankstoFaisal,Azad,Hamza,Ripon,Andr´eas,Dinu,Adina,Robert,Dan,
Marco,Peter,Matthias,Piotr,Vinay,Stefan,Daniel,ThorstenandMo-
hammadreza.Also,specialthanksgotoBirgit,UteandSabineforhelping
mewithvariouspaperworkandallothercircumstancesrelatedtolivingin
.yGerman

Iwouldalsoliketothankallmyteachers,advisorsandfriends,who
supportedmeduringmyeducationinTunisiaandGermany.Theyalways
wishedmesuccessandbelievedinme.

Mysincereandheartfeltthanksgotomydeceasedfather,Abdelwaheb
Ayari,andmymother,MananaKharratVVAyari.Mymotherwasalways
therewhenIneededher.Herconstantmoralsupporthasbeenveryencour-
agingalltheseyears.Ialsothankmybrother,Saifeddine,andsisters,Hager
andKaouther,fortheirendlesslove.

andIsaourvbedelothevedbdestaughfortheter,last.Eya,Iforwoalluldtheliketothankunderstanding,mybelolovve,edsuppwife,ortEmnaand,
ofhappinessencouragementhatttheyandalwastrengysthbroughfortmetoallme.theseTheyyears.wereacontinuoussource

vii

viii

tstenCon

Abstract

(german)Kurzfassung

wledgemenknoActs

FiguresofList

ablesTofList

AlgorithmsofList

iii

v

vii

xiii

xv

xvii

1IntroductionandProblemContext1
1.1ProblemStatement........................4
1.2ThesisContributions.......................6
1.3PublicationsResultingfromtheThesis.............9
1.4ThesisStructure..........................10

2StateoftheArtandPractice13
2.1ClassicalTransactionCommit