Reversible session-based pi-calculus

(1)

Contents lists available atScienceDirect

Journal

of

Logical

and

Algebraic

Methods

in

Programming

www.elsevier.com/locate/jlamp

Reversible

session-based

pi-calculus

✩

Francesco Tiezzi

a

,

∗

, Nobuko Yoshida

b

a_University_of_Camerino,_Italy b_Imperial_College_London,_UK

a

r

t

i

c

l

e

i

n

f

o

a

b

s

t

r

a

c

t

Articlehistory:

Received31August2014

Receivedinrevisedform31March2015 Accepted31March2015

Availableonline15April2015 Keywords:

Reversiblecomputing Thepi-calculus Sessiontypes

Session-basedprogramming

Inthiswork,weincorporatereversibility intostructuredcommunication-based program-ming,toallowpartiesofasessiontoautomaticallyundo,inarollbackfashion,theeffect ofpreviouslyexecutedinteractions.Thispermitstotakedifferentcomputationpathsalong thesamesession,aswellastorevertthewholesessionandstart anewone.Ouraimis todeﬁneatheoretical basisfor examiningthe interplayinconcurrentsystemsbetween reversiblecomputation and session-based interaction.We thusproposeReS

π

a session-based variant of

π

-calculus using memory devices to keep track of the computation history of sessions in order to reverse it. We show how a session type discipline of

π

-calculusisextendedtoReS

π

,andillustrateitspracticaladvantagesforstaticveriﬁcation ofsafecompositionincommunication-centricdistributedsoftwareperformingreversible computations.Wealsoshowhowafullyreversiblecharacterisationofthecalculusextends tocommittable sessions,wherecomputationcangoforwardandbackwarduntilthesession iscommittedbymeansofaspeciﬁcirreversibleaction.

1. Introduction

In theﬁeldofprogramminglanguages,reversiblecomputing aimsatprovidinga computationalmodelthat, besidesthe standard forward executions, alsopermits backward executionsteps to undo the effect ofpreviously performedforward computations. Despite being a subject of study for many years, reversible computing is recently experiencing a rise in popularity.Thisismainlyduetothefactthatreversibilityisakeyingredientindifferentapplicationdomains.Inparticular, for whatspeciﬁcally concerns ourinterest, manyresearchers haveput forwardexploitingthisparadigm in thedesign of reliable concurrent systems.In fact,it permitsusto understand existingpatterns forprogrammingreliable systems(e.g., compensations,checkpointing,transactions)and,possibly,todevelopnewones.

Apromisinglineofresearchonthistopicadvocatesreversiblevariantsofwell-establishedprocesscalculi,suchasCCS[2]

and

π

-calculus[3],asformalismsforstudyingreversibilitymechanismsinconcurrent systems.Bypursingthislineof re-search, inthiswork we incorporatereversibility intoa variantof

π

-calculusequippedwithsession primitives supporting communication-based programming. A(binary)sessionconsistsinaseriesofreciprocalinteractions betweentwo parties, possibly withbranching andrecursion.Interactionsona sessionare performedvia adedicated private channel,which is generated when initiating the session. Sessionprimitives come together witha session type discipline offering a simple

✩ _This _work_is_a_revised_and_extended_version_of_[1]_,_presented_in_the_Proceedings_of_the_7th_Workshop_on_Programming_Language_Approaches_to ConcurrencyandCommunication-cEntricSoftware(PLACES).TheworkhasbeenpartiallysponsoredbyEPSRCEP/K011715/1,EP/K034413/1,EP/L00058X/1, theCOSTActionBETTY(IC1201),theEUprojectsASCENS(257414)andFP7-612985UpScale,andtheItalianMIURPRINprojectCINA(2010LHT4KM).

*

Correspondingauthor.

E-mailaddresses:francesco.tiezzi@unicam.it(F. Tiezzi),n.yoshida@imperial.ac.uk(N. Yoshida).

http://dx.doi.org/10.1016/j.jlamp.2015.03.004

(2)

checkingframeworktostaticallyguaranteethecorrectnessofcommunicationpatterns.Thispreventsprogramsfrom inter-actingaccordingtoincompatiblepatterns.

Practically, combiningreversibility andsessions paves the wayforthe development of session-based communication-centricdistributedsoftwareintrinsicallycapableofperformingreversiblecomputations.Inthisway,withoutfurthercoding effort by the applicationprogrammer,theinteraction among sessionpartiesis relaxedso that, e.g.,the computation can automatically go back, thus allowing to take different paths when the current one is not satisfactory. As an application example,used in thispaper forillustrating our approach,we considera simple scenario involvinga client andmultiple providersofferingthesameservice(e.g.,on-demandvideostreaming).Theclientconnectstoaprovidertorequestagiven service(specifying,e.g.,titleofamovie,videoquality,etc.).Theproviderreplieswithaquotedeterminedaccordingtothe requested qualityofserviceandtothe serversstatus(current load,available bandwidth,etc.). Then,the clientcaneither accept, negotiate or reject thequote; in the ﬁrst two cases,the interaction betweenthe two parties shall continue. Ifa problemoccursduringtheinteractionbetweentheclientandtheproviderforﬁnalisingtheserviceagreement,the compu-tationcanbeautomaticallyreverted.Thisallowstheclienttopartiallyundothecurrentsession,inordertotakeadifferent computationpathalongthesamesession,orevenstartanewsessionwith(possibly)anotherprovider.

The proposed reversible session-based calculus, called ReS

π

(ReversibleSession-based

π

-calculus), relies on memories to store information aboutinteractions andtheir effects on the system, which otherwise would be lost duringforward computations. This data is used to enable backward computations that revert the effects of the corresponding forward ones. Each memory isdevoted to record data concerning a single event, which can correspond to thetaking place ofa communication action, a choice or a thread forking. Memories are connected with one other, inorder to keep trackof thecomputation history,byusingunique threadidentiﬁersaslinks. Likeall otherformalismsforreversiblecomputingin concurrent settings, forward computationsare undone in a causal-consistent fashion [4,5]. This means that backtracking doesnothavetonecessarilyfollowtheexactorderofforwardcomputationsinreverse,becauseindependentactionscanbe undoneinadifferentorder.Thus,anactioncanbeundoneonlyafteralltheactionscausallydependingonithavealready beenundone.

Concerningthesessiontypediscipline, ReS

π

inheritsthenotionoftypesandthetypingsystemfrom

π

-calculus.Thus, therelatedresults aremainly basedonthe onesstatedfor

π

-calculus. Besidesthe possibilityoftakingadvantage ofthe theoryalreadydeﬁnedfor

π

-calculus,thisalsoallowsourinvestigationtofocusonastandardsessiontypesetting,rather thanonanad-hoconespeciﬁcallyintroducedforourcalculus.

The resulting formalism offers a theoretical basis for examining the interplay between reversible computations and session-based structured interactions. We notice that reversibility enables session parties not only to partially undo the interactionsperformedalongthecurrentsession,butalsotoautomaticallyundo thewholesessionandrestartit,possibly involving different parties.The advantage of the reversible approach is that this behaviour is realised without explicitly implementingloops, butsimplyrelying onthe reversibilitymechanismavailable inthelanguage semantics.On theother hand,thesessiontypedisciplineaffectsreversibilityasitforcesconcurrentinteractionstofollowstructuredcommunication patterns.Ifwewouldconsideronlyasinglesession,duetolinearity,acausal-consistentformofreversibilitywouldnotbe necessary,i.e. concurrentinteractionsalong thesamesessionare forbiddenand, hence,therollbackwouldfollowa single path.Instead,inthegeneralcase,concurrent interactions alongdifferentsessionsmaytakeplace,thus introducingcausal dependences.Inthiscase, asessionexecutionhastobereverted inacausal-consistent fashion.Notably,interesting issues concerningreversibilityandsessiontypesarestillopenquestions,especiallyforwhatconcernsthevalidityinthereversible settingofstandardproperties(e.g.,progressenforcement)andpossiblynewproperties(e.g.,reversibilityofongoingsession history,safeclosureofsubordinatesessions).

It isworth noticing that theproposed calculus is fully reversible,i.e. backward computationsare always enabled. Full reversibility provides theoretical foundationsfor studying reversibility in session-based

π

-calculus, butit isnot suitable forapractical useon structuredcommunication-based programming. Infact,reverting acompleted sessionmightnot be desirable.Therefore,wealsoproposeanextensionofthecalculuswithanirreversible actionforcommittingthecompletion ofsessions.Inthisway,computationwouldgobackwardandforward,allowingthepartiestotrydifferentinteractions,until thesessionissuccessfullycompletedand,hence,irreversiblyclosed.

Summaryoftherestofthepaper.Section2reviewsstrictlyrelatedwork.Section3recallssyntaxandsemanticsdeﬁnitionsof theconsideredsession-basedvariantsof

π

-calculus.Section 4introduces ReS

π

,ourreversiblesession-basedcalculus. Sec-tion5showstheresultsconcerningthereversibilitypropertiesofReS

π

.Section6describestheassociatedtypingdiscipline. Section7presentstheextensionofReS

π

withirreversiblecommitactions.Section8concludesthepaperbytouchingupon directionsforfuturework.ProofsofresultsarecollectedinAppendix A.

2. Related work

Ourproposalcombines thenotion of(causal-consistent)reversibility with(typed)primitives supportingsession-based interactions in concurrent systems.We review here some of the closelyrelated works concerning either reversibility or sessiontypes.

Formsofreversiblecomputationcanbefoundindifferentformalismsintheliterature.Forexample,backwardreductions areconsideredinthe

λ

-calculustodeﬁneequalityonexpressions[6].Similarnotionsareusedinthedeﬁnitionsofbackand

(3)

forthbisimulations[7]onLabelledTransitionSystems,andofreversiblestepsinPetrinets[8].Moreinpractice,reversibility can be usedforexploring differentpossibilities ina computation.Forexample,the Prologlanguage uses itsbacktracking capabilitiestoexplorethestate-spaceofaderivationtofindasolutionforagivengoal.However,inourpaperwe mainly focusontheuseofreversiblecomputingasasuitable paradigmfordesigninganddevelopingreliableconcurrentsystems, which cameto prominencein recentyears.Alongthislineofresearch, theworksin thereversiblecomputingfield most closelyrelatedtooursarethoseconcerning thedefinitionofreversibleprocesscalculi.Webriefly discussthemostrelevant ofthembelow,andrefertheinterestedreaderto[9]foracomprehensivesurveyandalargerperspective.

ReversibleCCS(RCCS)[5]isthefirstproposalofreversiblecalculus,fromwhichallsubsequentworksdrewinspiration. The host calculus (i.e., the non-reversible calculus extended with capabilities for reversibility) is CCS without recursive definitionsandrelabelling.Toeachcurrentlyrunningthreadisassociatedanindividualmemorystackkeepingtrackofpast actions,aswell asforksandsynchronisations.Informationpushedonthememorystacks,upondoingaforwardtransition, can be then used fora rollback. The memories also serve asa naming scheme andyield unique identifiers forthreads. When a process divides in two sub-threads, each sub-thread inherits the father memory together with a fork number (either

1

or

2

) indicating which of the two sons the thread is. Then, in the caseof a forward synchronisation, the synchronisedthreadsexchangetheirnames(i.e.,memories)inordertoallowsthecorrespondingbackwardsynchronisation to takeplace.Adrawbackofthisapproachformemorisingforkactionsisthat theparalleloperatordoesnot satisfyusual structural congruence rules as commutativity,associativity andnil process as neutralelement. It is proved that RCCS is causally consistent,i.e. thecalculus allows backtrackalong anycausallyequivalent past,whereconcurrent actions canbe swappedandsuccessiveinverseactionscanbecancelled.RCCShasbeenusedforstudyingageneralnotionoftransactions in[10].

CCS-R [11]isanotherreversible variantofCCS,whichhowevermainlyaimsatformalisingbiologicalsystems.Like the previouscalculus,itreliesonmemorystacksforstoringinformationneededforbacktracking,whichnowalsorecordevents corresponding to theunfolding ofprocess definitions.Instead, differentlyfromRCCS,specific identifiersare used tolabel threads;incaseofunfolding,sub-threadsarelabelledon-the-fly.Forkingnowdoesnotexploitforknumbers,butitrequires thememorystackofagiventhreadbeemptybeforeenablingtheexecutionofitssons;thisforcesthesub-threadstoshare the memorythat their father hadbefore theforking. As inRCCS,in caseofsynchronisation, thecommunicating threads exchange their identifiers.The transitionsystemofCCS-Ris provedto bereversible anditis demonstratedthatCCS-R is soundandcompletew.r.t. CCS.

CCSwithcommunicationKeys (CCSK)[12]isareversibleprocess calculusobtainedbyapplyingageneralprocedureto producereversiblecalculi.Arelevantaspectofthisapproachisthatitdoesnotrelyonmemoriesforsupporting backtrack-ing.Theideaistomaintainthestructureofprocessesﬁxedthroughoutcomputations,thusavoidingtoconsumeguardsand alternativechoices,whichisthesourceofirreversibility.Pastbehaviouranddiscardedalternativesarethenrecordedinthe syntax ofterms.ThisisrealisedbytransformingthedynamicrulesoftheSOSsemanticsintostatic-like rules.Inthisway, backwardrulesareobtainedsimplyassymmetricversionsoftheforwardones.Toensurethatsynchronisationsareproperly reverted,twocommunicatingthreadshavetoagreeonacommunicationkey,whichwilluniquelyidentifythat communica-tion.Inthisway,thesynchronisingactionsarelockedtogetherandcanonlybeundonetogether.Asusual,resultsshowing that themethodyields well-behavedtransitionrelations areprovided.The proposedconvertingprocedure canbeapplied toothercalculiwithoutnamepassing,suchasACP[13]orCSP[14],butitisnotsuitableforcalculiwithnamebinders,as

π

-calculus,whichweareinterestedinthiswork.

ρπ

[15]isareversiblevariantofthehigher-order

π

-calculus[16].ItborrowsfromRCCStheuseofmemoriesforkeeping trackofpastactions.However,in

ρπ

memoriesarenotstackssyntacticallyassociatedtothreads,buttheysimplyareterms, each onededicatedtoa singlecommunication, inparallelwithprocesses.The connectionbetweenmemories andthreads iskept byresortingtoidentifiersinawaysimilar toCCSK.Forkhandlingreliesonspecificstructured tagsconnectingthe identifierofthefatherthreadwiththeidentifiersofitssub-threads.Besidesprovingthat

ρπ

iscausallyconsistent,itisalso shownthat itcan befaithfullyencodedintohigher-order

π

-calculus.Notably,differentlyfromtheapproachesmentioned before,thesemanticsof

ρπ

isgiveninareductionstyle.Avariantofthiscalculus, calledroll-

π

[17],hasbeendeﬁnedto controlbackwardcomputationsbymeansofarollbackprimitive.Theapproachesproposedin[15,17]havebeenappliedin

[18]forreversingavariantofKlaim[19].

Anotherreversiblevariantof

π

-calculus isR

π

[20].Differentlyfrom

ρπ

,R

π

considersastandard

π

-calculus(without choice andreplication)ashostcalculus, anditssemantics isdeﬁnedin termsofa labelledtransitionrelation.Thislatter pointrequirestointroducesometechnicalitiestoproperlydealwithscopeextrusion.SimilarlytoRCCS,thiscalculusrelies on memorystacks,nowrecordingevents(i.e.,consumedpreﬁxesandrelatedsubstitutions)andforking(bymeans ofthe forksymbol

↑

).Resultsaboutthenotionofcausalityinducedbythesemanticsofthecalculusareprovided.

Reversiblestructures[21]isasimplecomputationalcalculus,basedonDSD[22],formodellingchemicalsystems.Since such systems are naturally reversible but have no backtracking memory, differently from most of the above proposals, reversible structures doesnot exploit memories.Instead, reversible structuresmaintain the structure ofterms andusea special symbol

ˆ

to indicatethenext operations(oneforwardandonebackward)that atermcan perform.Termsofthe calculus areparallelcompositionsofsignalsandgates(i.e.,termsthatacceptinputsignalsandemitoutputsignals),which interactaccording toa CCS-stylemodel.Whena forwardsynchronisation takesplace,theexecuted gate input islabelled bytheidentiﬁeroftheconsumedsignal,andthepointersymbolinsidethegateismovedforward.Thebackwards compu-tationis realisedby executingtheseoperationsina reverseway,thus releasingtheoutputsignal. Asusual, theinterplay

(4)

betweencausaldependencyandreversible structuresisstudied,withthe noveltythatinthissettingsignal identiﬁersare notnecessaryunique.

In ourwork we mainly take inspiration fromthe

ρπ

approach. Indeed,all other approachesbased on CCS andDSD cannotbedirectlyappliedtoacalculuswithname-passing.Moreover,the

ρπ

approachispreferabletotheR

π

onebecause the former proposes a reduction semantics, which we are interested in, while the latter proposesa labelled semantics, whichwouldcomplicateourtheoreticalframework(inordertoproperlydealwithscopeextensionofnames).Speciﬁcally, weuseunique(non-structured)tagsforidentifyingthreadsandmemoriesforrecordingtakingplaceofactions,choicesand forking.Eachmemoryisdevotedtostoring theinformationneededtorevertasingle event,andmemoriesare connected eachother,inordertokeeptrackofcomputationhistory,byusingtagsaslinks.

Forwhat concernsthe relatedworksonsession-basedcalculi, itis worthnoticing thatwe consider asettingas stan-dard and simple as possible, which is the one with synchronous binary sessions. In particular, our host calculus is the well-established variant of

π

-calculus introduced in [23], whose notation has been revised according to [24].We leave forfuture investigation the applicationofour approach to formalismsrelying on the other forms ofsessions introduced in the literature, among which we would like to mention asynchronous binary sessions [25], multiparty asynchronous sessions [26],multiparty synchronous sessions [27],sessions with higher-order communication[24],sessions speciﬁcally devisedforservice-orientedcomputing[28–30].

Finally,the paper withthe aimclosest to ours is [31], wherea formalism combining the notionsof reversibility and sessionis proposed. Thiscalculus issimpler thanReS

π

, becauseit isan extension ofthe formalism ofsessionbehaviours

[32]withoutdelegation(i.e.,itisasub-languageofCCS)withacheckpoint-basedbacktrackingmechanism.Infact,neither message nor channel passing are considered in the host calculus. Concerning reversibility, only the behaviour preﬁxed by the lastly traversed checkpointis recordedby a givenparty, that is each behaviour is simply paired witha one-size memory.Moreover, causal-consistency isnot considered,because inthisformalism partiesjustreduce insequential way. Alsocommittable sessionsarenottakenintoaccount.Ontheotherhand,thisformalismenabledthestudyofanextension ofthecompliancenotiontothereversiblesetting.

3. Session-based π-calculus

Inthissectionwepresentthesyntaxandsemanticsdeﬁnitionsofthehostlanguageconsideredforourreversible calcu-lus.Thisisavariantof

π

-calculusenrichedwithprimitivesformanagingstructuredbinarysessions.

3.1. Syntax

Weusethefollowingbasesets:sharedchannels,usedtoinitiatesessions;sessionchannels,consistingonpairsofendpoints

usedbythetwopartiestoexchangevalues withinanestablishedsession;variables,usedtostorevalues;labels,usedtoselect andofferbranching choices;andprocessvariables, usedforrecursion.The correspondingnotation andterminologyare as follows: Variables: x

,

y

, . . .

Shared channels: a

,

b

, . . .

Shared identiﬁers: u

,

u

, . . .

Channels: c

,

c

, . . .

Session channels s

,

s

. . .

Variables: x

,

y

, . . .

Session endpoints: s

,

¯

s

, . . .

Session identiﬁers: k

,

k

, . . .

Labels: l

,

l

, . . .

Process variables: X

,

Y

, . . .

Values: v

,

v

, . . .

⎧

⎪

⎨

⎪

⎩

Booleans:

true

, false

Integers: 0

,

1

, . . .

Shared channels: a

,

b

, . . .

Session endpoints: s

,

¯

s

, . . .

Notably,each sessionchannel s has two(dual) endpoints,denotedby s and

¯

s,each one assignedtoone sessionpartyto exchangevalueswiththeother.Wedeﬁnedualitytobeidempotent,i.e.

¯¯

s

=

s.Theuseoftwoseparatedendpointsissimilar tothatofpolarities in[33,23].Notation

˜·

standsfortuples,e.g.c means

˜

c1

,

. . . ,

cn.

Processes,rangedoverby P , Q ,. . . ,andexpressions,rangedoverbye,e,

. . .

aregivenbythegrammarinFig. 1.Weuse op

(

·,

. . . ,

·)

todenoteageneric expressionoperator;weassume thatexpressionsare equippedwithstandardoperatorson booleanandintegervalues(e.g.,

∧

,

+

,

. . .

).

Theinitiationofasessionistriggeredbythesynchronisationonasharedchannela oftwoprocessesoftheforma

¯

(

x

).

P

anda

(

y

).

Q .Thiscausesthegenerationofafreshsessionchannels,whoseendpointsreplacevariablesx and y,bymeans ofasubstitutionapplication,inordertobeusedby P and Q ,respectively,forlatercommunications.Primitivesk

!

e

.

P and k?

(

x

).

Q denoteoutputandinputviasessionendpointsidentiﬁedbyk andk,respectively.Thesecommunicationprimitives

(5)

Processes P ::= u¯(x).P connect | u(x).P connect dual | k!e.P output | k?(x).P input | kl.P selection | k {l1:P1, . . . ,ln:Pn} branching

| ifethenPelseQ conditional choice

| P_|Q parallel composition | (

ν

c)P restriction | X process variable |

μ

X.P recursion | 0 inaction Expressions e ::₌ v value | x variable | op(e1, . . . ,en) composed expression

Fig. 1. Session-basedπ-calculus: syntax.

realise thestandardsynchronous messagepassing,wheremessages resultfromtheevaluationofexpressions. Notably,an exchangedvaluecanbeanendpointthatisbeingusedinasession(thischannel-passingmodalityiscalleddelegation),thus allowing complexnestedstructuredcommunications.Constructsk

l

.

P andk

{

l1

:

P1

,

. . . ,

ln

:

Pn

}

denotelabelselection

andlabelbranching(wherel1

,

. . . ,

ln areassumedtobepairwisedistinct)viaendpointsidentiﬁedbyk andk,respectively.

Theymimemethodinvocationinobject-basedprogramming.

The aboveinteraction primitivesare thencombinedby standardprocess calculiconstructs:conditional choice,parallel composition,restriction,recursionandtheemptyprocess(denotinginaction).Itisworthnoticingthatrestrictioncanhave bothsharedandsessionchannelsasargument:

(

ν

a

)

P statesthata isaprivatesharedchannelofP ;similarly,

(

ν

s

)

P states

that the two endpoints of the session channel, namely s and s,

¯

are invisible from processes different from P (see the seventh lawin Fig. 2), i.e.no external process can perform a session action on either of these endpoints (this ensures non-interferencewithinasession).Asamatterofnotation,wewillwrite

(

ν

c1

,

. . . ,

cn

)

P inplaceof

(

ν

c1

)

. . . (

ν

cn)P .

We adopt the following conventions about the operators precedence: preﬁxing, restriction, and recursion bind more tightlythanparallelcomposition.

Bindingsare deﬁnedasfollows:u

¯

(

x

).

P , u

(

x

).

P andk?

(

x

).

P bind variablex in P ;

(

ν

a

)

P bindsshared channela in P ;

(

ν

s

)

P bindssession channel s in P ; ﬁnally,

μ

X

.

P bindsprocess variable X in P . Thederived notions ofboundandfree names, alpha-equivalence

≡

α ,andsubstitutionare standard.For P aprocess, fv

(

P

)

denotes thesetoffreevariables,fc

(

P

)

denotesthesetoffreesharedchannels,andfse

(

P

)

thesetoffreesessionendpoints.Forthesakeofsimplicity,weassumethat freeandboundvariablesarealwayschosentobedifferent,andthatboundvariablesarepairwisedistinct;thesameapplies tonames.Ofcourse,theseconditionsarenotrestrictiveandcanalwaysbefulﬁlledbypossiblyusingalpha-conversion.

3.2. Semantics

Theoperationalsemanticsisgivenintermsofastructuralcongruenceandofareductionrelation.Notably,thesemantics is only deﬁned for closed terms, i.e. terms without free variables. Indeed, we consider the binding of a variable as its declaration(andinitialisation),thereforefreeoccurrencesofvariablesattheoutsetinatermmustbepreventedsincethey aresimilartousesofvariablesbeforetheirdeclarationinprograms(whichareconsideredasprogrammingerrors).

Thestructuralcongruence,written

≡

,isdeﬁnedasthesmallestcongruencerelationonprocessesthatincludesthe equa-tionallawsshowninFig. 2.Thesearethestandardlawsof

π

-calculus.ReadingthelawsinFig. 2byrowfromlefttoright, andfrom topto bottomrow, theﬁrst threeare themonoidlaws for

|

(i.e.,it isassociativeandcommutative,andhas 0

asidentityelement).Thesecond fourlawsdealwithrestrictionandenablegarbage-collectionofchannels,scopeextension andscopeswap,respectively.Theeighthlawpermitsarecursiontobeunfolded(notation P

[

Q

/

X

]

denotesreplacementof free occurrencesof X in P byprocess Q ).The lastlawequatesalpha-equivalentprocesses,i.e. processesonlydifferingin theidentityofboundvariables/channels.

To deﬁne the reduction relation, we use an auxiliary function

· ↓

for evaluating closed expressions:e

↓

v says that expressione evaluatestovalue v (wherev

↓

v,andx

↓

isundeﬁned).

The reductionrelation, written

→

, is the smallest relation on closed processes generated by the rules in Fig. 3. We commentonsalientpoints.Anewsessionisestablishedwhentwo parallelprocessessynchroniseviaasharedchannel a;

thisresultsinthegenerationofafresh(private) sessionchannel whoseendpointsareassignedtothetwosessionparties (rule [Con]).Duringa session,thetwo partiescanexchangevalues(fordata- andchannel-passing, rule[Com])andlabels (forbranchingselection,rule[Lab]).Theotherrulesarestandardandstatethat:conditionalchoiceevolvesaccordingtothe evaluationoftheexpressionargument(rules[If1]and[If2]);ifapartofalargerprocessevolves,thewholeprocessevolves accordingly(rules[Par]and[Res]);andstructuralcongruentprocesseshavethesamereductions(rule[Str]).

(6)

(P|Q)|R≡P| (Q|R) P|Q≡Q|P

P|0≡P (

ν

c)0≡0

(

ν

a)P|Q≡ (

ν

a)(P|Q) if a∈/fc(Q) (

ν

c1)(

ν

c2)P≡ (

ν

c2)(

ν

c1)P

(

ν

s)P|Q ≡ (

ν

s)(P|Q) if s,¯s∈/fse(Q)

μ

X.P≡P[

μ

X.P/X] P_≡Q if P_≡αQ

Fig. 2. Session-basedπ-calculus: structural congruence.

¯ a(x).P1 | a(y).P2 → (

ν

s)(P1[¯s/x] |P2[s/y]) s,s¯∈/fse(P1,P2) [Con] ¯ k!e.P1 | k?(x).P2 → P1|P2[v/x] (k=s or k= ¯s), e↓v [Com] ¯ kli.P | k {l1:P1, . . . ,ln:Pn} → P|Pi (k=s or k= ¯s), 1≤i≤n [Lab]

ifethenP1elseP2 → P1 e↓ true [If1]

ifethenP1elseP2 → P2 e↓ false [If2]

P → P P| Q → P|Q [Par] P → P (νc)P → (νc)P [Res] P≡P → Q≡Q P → Q [Str] Fig. 3. Session-basedπ-calculus: reduction relation.

3.3. Themultipleprovidersscenariointhesession-based

π

-calculus

ThescenarioinvolvingaclientandmultipleprovidersintroducedinSection1canberenderedin

π

-calculus asfollows (forthesakeofsimplicity,hereweconsiderjusttwoproviders):

Pclient

|

Pprovider1

|

Pprovider2

wheretheclientprocess Pclientisdeﬁnedas

alogin

(

x

).

x

!

srv_req

.

x?

(

yquote

).

if

accept

(

yquote

) then

x

lacc

.

Pacc

else

(if

negotiate

(

yquote

) then

x

lneg

.

Pneg

else

x

lrej

.

0

)

whileaproviderprocess Pprovider i isasfollows

alogin

(

y

).

y?

(

zreq

).

y

!

quotei

(

zreq

)

.

y

{

lacc

:

Qacc

,

lneg

:

Qneg

,

lrej

:

0

}

Weshowbelowapossibleevolutionofthesystem,wheretheclientcontactsprovider1 andacceptstheproposedquote:

Pclient

|

Pprovider1

|

Pprovider2

→

(

ν

s

)(

¯

s

!

srv_req

. ¯

s?

(

yquote

). if

accept

(

yquote

) then

s

¯

lacc

.

Pacc

[¯

s

/

x

]else (. . .)

|

s?

(

zreq

).

s

!

quotei

(

zreq

)

.

s

{

lacc

:

Qacc

[

s

/

y

] ,

lneg

:

Qneg

[

s

/

y

] ,

lrej

:

0

} )

|

Pprovider2

→

(

ν

s

)(

¯

s?

(

yquote

). if

accept

(

yquote

) then

¯

s

lacc

.

Pacc

[¯

s

/

x

]else (. . .)

|

s

!

quotei

(

srv_req

)

.

s

{

lacc

:

Qacc

[

s

/

y

][

srv_req

/

zreq

] , . . .} )

|

Pprovider2

→

(

ν

s

)( if

accept

(

quote

) then

¯

s

lacc

.

Pacc

[¯

s

/

x

][

quote

/

yquote

]else (. . .)

|

s

{

lacc

:

Qacc

[

s

/

y

][

srv_req

/

zreq

] , . . .} )

|

Pprovider2

→

(7)

(

ν

s

)(

¯

s

lacc

.

Pacc

[¯

s

/

x

][

quote

/

yquote

] |

s

{

lacc

:

Qacc

[

s

/

y

][

srv_req

/

zreq

] , . . .} )

|

Pprovider2

→

(

ν

s

)(

Pacc

[¯

s

/

x

][

quote

/

yquote

] |

Qacc

[

s

/

y

][

srv_req

/

zreq

] )

|

Pprovider2

4. Reversible session-based π-calculus

Inthissection,weintroduceReS

π

,areversibleextensionofthecalculusdescribedinSection3.

A reversible calculus is typically obtained fromthe corresponding host calculus by adding memorydevices (see Sec-tion2).Theyaimatstoringinformationaboutinteractionsandtheireffectsonthesystem, whichotherwisewouldbelost during forward computations,ase.g.the discarded branchina conditional choice.In doingthis, we followtheapproach of [15], whichin its turnis inspired by[5] (forthe useof memories)andby [12] (for the useof threadidentiﬁers). Of course,sincehereweconsiderashostcalculusasession-basedvariantofstandard

π

-calculus,ratherthananasynchronous higher-ordervariant,thetechnicaldevelopmentisdifferent.

Roughly,ourapproachtokeeptrackofcomputation historyisasfollows:we tagprocesseswithuniqueidentiﬁersand use memoriesto store theinformationneededto reverseeach single forwardreduction. Thus,the historyofareduction sequence isstoredina numberofsmallmemories connectedeach other byusingtags aslinks. Inthisway,ReS

π

terms can perform,besidesforwardreductions (denotedby

),alsobackwardreductions (denotedby

) thatundo theeffectof theformerones.AsinthereversiblecalculidiscussedinSection2,forwardcomputationsarerevertedinacausal-consistent

fashion.Thatis,independent(moreprecisely,concurrent)actionscanbeundoneinanorderpossiblydifferentfromtheexact order offorwardreductionsinreverse.Speciﬁcally, anaction canbeundoneonly afteralltheactions causallydepending onithavealreadybeenundone.Wewillcomebackoncausal-consistencyinSection5.

BeforeintroducingthetechnicalitiesofReS

π

,weinformallyprovideabasicintuitionaboutitsmainfeatures.Letuscome backtothescenariointroducedinSection1andspeciﬁedin

π

-calculusinSection 3.3.WecanobtainaReS

π

speciﬁcation ofthescenariobysimplyannotatingthe

π

-calculustermwiththe(unique)tagst1,t2andt3 asfollows:

t1

:

Pclient

|

t2

:

Pprovider1

|

t3

:

Pprovider2

Now,the computationdescribed inSection 3.3corresponds toasequence ofﬁveforwardreductionsleadingto theReS

π

process M havingthefollowingform:

(

ν

s

, ˜

t

) (

t₁

:

Pacc

[¯

s

/

x

][

quote

/

yquote

] |

t2

:

Qacc

[

s

/

y

][

srv_req

/

zreq

]

|

t1

−

alogin

(

x

)(

y

)(

ν

s

)

P_client P_provider1

→

t2

,

t1

,

t2

| . . . | . . . | . . . | . . . )

|

Pprovider2

The forwardcomputation hascreated atuplet of

˜

freshtags, whichincludesthe tagst₁ andt₂ attachedto theresulting processes of client and provider1, respectively. Moreover, each reduction has created a memory

. . .

, which isspawn in parallelwiththetwoprocessesoftheinvolvedpartiesanddevotedtostoretheinformationforrevertingthecorresponding forwardreduction. Here,forthesake ofpresentation,we haveomittedthecontentofsuch memories,exceptfortheone generatedbytheﬁrstreduction:itrecordsthattheprocesstaggedbyt1 (i.e.,theclient)initiatesasessions alongchannel

aloginwiththeprocesstaggedbyt2 (i.e.,theﬁrstprovider);italsorecordsthevariablesreplacedbythesessionendpoints andthecontinuationprocessestogetherwiththeirtags.Notably,process M cannotimmediatelyusethismemorytorevert theinteractioncorrespondingtothesessioninitiation.Indeed,amemorycantriggerabackwardreductiononlyiftwo pro-cessesproperlytaggedwiththecontinuationtagsareavailable,whichisnotthecaseoftheﬁrstmemoryintheprocess M. Therefore,asexpected,alltheotherforwardreductionsmustbepreviouslyrevertedinordertorevertthesessioninitiation one.

4.1. Syntax

The syntax of ReS

π

is given in Fig. 4. In addition to the basesets used for

π

-calculus processes in Section 3, here we usetags,rangedoverby t,t, . . . , touniquelyidentifythreads.Lettersh,h,. . . denotenames,i.e.(shared andsession) channelsandtagstogether.Uniquenessoftagsisensuredbyusingtherestrictionoperatorandbyonlyconsideringreachable

processes(seeDeﬁnition 3).

ReS

π

processes are built upon standard (session-based)

π

-calculus processes by labelling them with tags. Thus, the syntax of

π

-calculusprocesses P ,aswellasofexpressionse,isthesameofthatshowninFig. 1and,hence,itisomitted here.ItisworthnoticingthatonlyReS

π

processescanexecute(i.e.,

π

-calculusonescannot).

(8)

ReS

π

Processes M ::= t:P thread

| (

ν

h)M channel/tag restriction

| M|N parallel composition

| m memory

| nil empty process

Memories m ::= t1−A→t2,t1,t2 action memory

| t,e? P_:Q,t choice memory

| t⇒ (t1,t2) fork memory

A ::= a(x)(y)(

ν

s)P Q | ke(x)P Q action events | kliP{l1:P1, . . . ,ln:Pn}

Fig. 4. ReSπsyntax (π-calculus Processes P and Expressions e are inFig. 1).

ReS

π

alsoextends

π

-calculuswithmemory processesm.Inparticular,therearethreekindofmemories:

•

Actionmemory

t1

−

A

→

t2

,

t1

,

t2

,storinganactioneventA togetherwiththetagt1oftheactivepartyoftheaction,the tagt2ofthecorrespondingpassiveparty,andthetagst₁ andt₂ ofthetwonewthreadsactivatedbythecorresponding reduction. An actionevent A, as we shall clarify later, records all information necessary to revert the corresponding interaction, which can be either a session initiation a

(

x

)(

y

)(

ν

s

)

P Q , a communication along an established session

k

e

(

x

)

P Q ,ora branchselectionk

liP

{

l1

:

P1

,

. . . ,

ln

:

Pn

}

.Notably,inthelattertwo events,k canonlybe eithers

ors (i.e.,

¯

itcannotbeavariable).

•

Choicememory

t

,

e?P

:

Q

,

t

,storing achoiceevente?P

:

Q togetherwiththe tagt ofthe conditionalchoice andthe tagt ofthe newactivatedthread.The choiceevente?P

:

Q recordsthe evaluatedexpression e,andthe processes P

andQ ofthethen-branchandelse-branch,respectively.

•

Forkmemory

t

⇒ (

t1

,

t2

)

,storingthetagt ofasplittingthread,i.e. a threadoftheformt

: (

P

|

Q

)

,togetherwiththe tagst1andt2 ofthetwonewactivatedthreads,i.e.t1

:

P andt2

:

Q .Theuseofforkmemoriesisanalogoustothatof

connectors in[18].

Threadsandmemories arecomposedbyparallelcomposition andrestrictionoperators.Thelatter,aswellasthenotion ofboundandfreeidentiﬁers,extendtonames.Inparticular,forM aReS

π

process,ft

(

M

)

denotesthesetoffreetags;fv

(

·)

, fc

(

·)

andfse

(

·)

extend naturally toReS

π

processes.Ofcourse, we still rely onthe sameassumptions on free andbound variables/channelsmentionedinSection3.1.

NotallprocessesallowedbythesyntaxinFig. 4aresemanticallymeaningful.Indeed,inageneraltermofthecalculus, thehistorystoredinthememoriesmaynotbeconsistent,duetotheuseofnon-uniquetagsorbrokenconnectionsbetween continuation tags within memories and corresponding threads. Forexample,given the choicememory

t

,

e?P

:

Q

,

t

,we havea brokenconnectionwhenno threadtaggedby t exists intheReS

π

processandno memoryoftheform

t

−

A

→

t2

,

t1

,

t2

,

t1

−

A

→

t

,

t1

,

t2

,

t

,

e?P1

:

P2

,

t1

,and

t

⇒ (

t1

,

t2

)

exist.

The class ofmeaningful ReS

π

processes we are interested in consists of programs andruntimeprocesses. The former are theterms that canbe written by programmers,i.e. theyare ReS

π

processes withnomemory. In fact,memories are not expected to occur inthe source code written by programmers.We assume that thethreads within a program have uniquetags.ThelattertermsoftheclassaretheReS

π

processesthatcanbeobtainedbymeansofforwardreductionsfrom programs;inthisway,historyconsistencyisensured.Usingtheterminologyfrom[20],theprocessesoftheconsideredclass arecalledreachable.Weformalisetheirdeﬁnitionbelow.

Deﬁnition 1 (Programs).ThesetofReS

π

programs isthesetoftermsgeneratedbythefollowinggrammar

M

::=

t

:

P

| (

ν

c

)

M

|

M

|

N

|

nil

andwhosethreadshavedistincttags,where P isa

π

-calculusprocessasinFig. 1.

Deﬁnition 2 (Runtimeprocesses). The set of ReS

π

runtimeprocesses isthe set ofterms obtainedby the transitive closure under

(seeSection4.2)ofthesetofReS

π

programs.

Deﬁnition 3 (Reachableprocesses). The set of ReS

π

reachableprocesses isthe union of the sets of programs and runtime processes.

NoticethatinDefinition 1therestrictionoperatorisdefinedonchannelsc ratherthanonnamesh.Thisbecausethere isnoneedtorestricttagsinaprogram.Infact,itissufficienttousedistincttags,asrequiredbythedefinition.Inpractice,

(9)

(M|N)|L≡M| (N|L) M|N≡N|M

M|nil≡M (

ν

h)nil≡nil

(

ν

t)M|N≡ (

ν

t)(M|N) if t∈/ft(N) (

ν

h1)(

ν

h2)M≡ (

ν

h2)(

ν

h1)M

(

ν

a)M|N≡ (

ν

a)(M|N) if a∈/fc(N) t: (

ν

c)P≡ (

ν

c)t:P

t_:P_≡t_:Q if P_≡Q (

ν

s)M_|N_{≡ (}

ν

s)(M_|N) if s,¯s∈/fse(N)

M_≡N if M_≡αN t: (P|Q)≡ (

ν

t1,t2)(t1:P|t2:Q | t⇒ (t1,t2))

Fig. 5. ReSπstructural congruence (additional laws).

theprogrammerwouldhavetowritejusta

π

-calculustermthatcanbethenautomaticallyannotatedwithuniquetagsto obtainaReS

π

program.Atruntime,asshowninthenextsubsection,itistheoperationalsemanticsinchargeofgenerating freshtagsforthenewthreadsbymeansoftherestrictionoperator.

4.2. Semantics

TheoperationalsemanticsofReS

π

isgivenintermsofastructuralcongruenceandofareductionrelation.

Thestructuralcongruence

≡

extendsthat of

π

-calculus(Fig. 2)withtheadditionallawsinFig. 5.Mostofthenewlaws simplydealwiththeparallelandrestrictionoperatorsonReS

π

processes.Thus,weonlyfocusonrelevantlaws(below,the lawsarereadbyrowfromlefttoright,andfromtoptobottomrow).Theeighthlawpermitsarestrictionona

π

-calculus process to be moved to the level of ReS

π

processes. The ninth law lifts the congruence at

π

-calculus process level to the threads level. The last law is crucial for fork handling: it is used to split a single thread composed of two parallel processesintotwothreadswithfreshtags;thetagoftheoriginalthreadandthenewtagsareproperlyrecordedinafork memory.

Thereductionrelation ofReS

π

,written

,isgivenastheunionoftheforwardandbackwardreductionrelationsdeﬁned by the rules inFig. 6:

= ∪

. Relations

and

are thesmallest relationson closed ReS

π

reachable processes generatedbythecorrespondingrulesintheﬁgure.

We commentonsalientpoints.Whentwo parallelthreads synchronisetoestablishanewsession(rule [fwCon]), two freshtagsarecreatedtouniquelyidentifythetwocontinuationsofthesynchronisingthreads.Moreover,allrelevant infor-mationisstoredintheactionmemory

t1

−

a

(

x

)(

y

)(

ν

s

)

P1P2

→

t2

,

t1

,

t2

:thetagt1oftheinitiator(i.e.,thethreadexecuting a preﬁxoftheforma

¯

(

·)

), thetagt2 ofthethreadexecutingthedualaction,thetagst1 andt2 oftheircontinuations,the shared channel a used forthe synchronisation,the replacedvariables x and y,the generatedsession channel s, andthe processes P1 and P2 to which substitutionsare applied. All such informationis exploited to revert thisreduction (rule [bwCon]). In particular, the corresponding backward reduction is triggered by the coexistence ofthe memory described abovewithtwothreadstaggedt₁ andt₂,allofthemwithinthescopeofthesessionchannels andtagst₁andt₂generated by theforwardreduction(which,infact,areremovedbythebackwardone).Noticethat,whenconsideringreachable pro-cesses, dueto taguniqueness,thetwo processes P and Q mustcoincide with P1

[¯

s

/

x

]

and P2

[

s

/

y

]

;indeed,asregistered inthememory,theselatterprocesseshavebeentaggedwitht₁andt₂ bytheforwardreduction.Thefactthattwothreads taggedwitht₁ andt₂ areavailableinparalleltothememoryensuresthatallactionspossiblyexecutedbythetwo contin-uationsactivatedbytheforwardcomputation havebeenundoneand,hence,wecansafelyproceedtoundonetheforward computationitself.

Rules[fwCom],[bwCom],[fwLab],[bwLab],[fwIf1],[fwIf2]and[bwIf]aresimilar.Notably,intheﬁrsttworules men-tioned above,besides tags andcontinuation processes,theaction memorystoresthe sessionendpoint k ofthe receiving party(theotherendpointk is

¯

obtainedbyduality),theexpressione generatingthesentvalue,andthereplacedvariablex.

It isalsoworthnoticingthat, sinceallinformationaboutachoiceeventisstoredinthe correspondingmemory,we need justonebackwardrule([bwIf])toreverttheeffectoftheforwardrules[fwIf1]and[fwIf2].Themeaningoftheremaining rules,dealingwithparallelcomposition,restrictionandstructuralcongruentterms,isstraightforward.

4.3. ThemultipleprovidersscenarioinReS

π

Let us consider again the multiple providers scenario. We have shownat the beginning of thissection that a ReS

π

speciﬁcationcanbeobtainedbysimplyannotatingthe

π

-calculustermwithuniquetagsasfollows:

(10)

t1: ¯a(x).P1 | t2:a(y).P2 s,¯s∈/fse(P1,P2) [fwCon] (

ν

s,t₁,t₂)(t₁:P1[¯s/x] |t₂:P2[s/y] | t1−a(x)(y)(

ν

s)P1P2→t2,t1,t2) (

ν

s,t₁,t₂)(t₁:P|t₂:Q| t1−a(x)(y)(

ν

s)P1P2→t2,t1,t2) [bwCon] t1: ¯a(x).P1 | t2:a(y).P2 t1: ¯k!e.P1 | t2:k?(x).P2 (k=s or k= ¯s) [fwCom] (

ν

t₁,t₂)(t₁:P1|t2:P2[v/x] e↓v | t1−ke(x)P1P2→t2,t1,t2) (

ν

t₁,t₂)(t₁ :P|t₂:Q| t1−ke(x)P1P2→t2,t1,t2) [bwCom] t1: ¯k!e.P1 | t2:k?(x).P2 t1: ¯kli.P | t2:k {l1: P1, . . . ,ln:Pn} (k=s or k= ¯s) [fwLab] (

ν

t₁,t₂)(t₁:P|t₂:Pi 1≤i≤n | t1−kliP{l1:P1, . . . ,ln: Pn}→t2,t1,t2) (

ν

t₁,t₂)(t₁:Q |t₂:Q | t1−kliP{l1:P1, . . . ,ln:Pn}→t2,t₁,t₂) [bwLab] t1: ¯kli.P | t2:k {l1: P1, . . . ,ln:Pn}

t: ifethenP1elseP2 (

ν

t)(t:P1| t,e? P1:P2,t) e↓ true [fwIf1]

t_{: if}ethenP1elseP2 (

ν

t)(t:P2| t,e? P1:P2,t) e↓ false [fwIf2]

(

ν

t)(t:P| t,e? P1:P2,t) t: ifethenP1elseP2 [bwIf]

M M M| N M|N [fwPar] M M M| N M|N [bwPar] M M (νh)M (νh)M [fwRes] M M (νh)M (νh)M [bwRes] M≡M N≡N M N [fwStr] M≡M N≡N M N [bwStr] Fig. 6. ReSπreduction relation.

Now,thecomputationdescribedinSection3.3correspondstothefollowingsequenceofforwardreductions: t1

:

Pclient

|

t2

:

Pprovider1

|

t3

:

Pprovider2

M

= (

ν

s

,

t₁1

,

t1₂

,

t2₁

,

t2₂

,

t3₁

,

t3₂

,

t₁4

,

t5₁

,

t4₂

)

(

t5₁

:

Pacc

[¯

s

/

x

][

quote

/

yquote

] |

t₂4

:

Qacc

[

s

/

y

][

srv_req

/

zreq

]

|

t1

−

alogin

(

x

)(

y

)(

ν

s

)

P_client P_provider1

→

t2

,

t₁1

,

t1₂

|

t1

1

−

s

srv_req

(

zreq

)

→

t12

,

t21

,

t22

|

t₂2

−¯

s

quote

(

yquote

)

P_provider1P_client

→

t12

,

t32

,

t31

|

t₁3

,

accept

(

quote

)

? Pclient_t

:

Pclient_e

,

t41

|

t₁4

−

s

laccPacc

[¯

s

/

x

][

quote

/

yquote

]

{

lacc

:

Qacc

[

s

/

y

][

srv_req

/

zreq

], . . .}→

t₂3

,

t5₁

,

t4₂

)

|

Pprovider2

Basically,ﬁvememorieshavebeengenerated,eachonededicatedtoreverttheeffectsofthecorrespondingforward reduc-tion.

Ifa problem occursduring the subsequent interactions betweenthe clientand theprovider forﬁnalising the service agreement,thecomputationcanberevertedtotheinitialstate.Inparticular,thebackwardrules[bwCon],[bwCom],[bwLab] and[bwIf]canbeappliedonlyiftheReS

π

termcontainsamemoryinparallelwiththread(s)appropriately taggedbythe

(11)

continuationtag(s)storedinthememory.Forexample,toapplytherule[bwCon]intheprocessM,twothreadstaggedby

t1

1 andt21mustbeinparallelwiththeﬁrstmemory,whichactuallyisnotthecase.Infact,inM,onlythelastmemorycan triggerabackwardstep,bymeansoftheapplicationofrule[bwLab]:

M

= (

ν

s

,

t₁1

,

t1₂

,

t₁2

,

t2₂

,

t3₁

,

t3₂

,

t4₁

)

(

t4

1

: ¯

s

lacc

.

Pacc

[¯

s

/

x

][

quote

/

yquote

]

|

t3

2

:

s

{

lacc

:

Qacc

[

s

/

y

][

srv_req

/

zreq

] , . . .}

|

t1

−

alogin

(

x

)(

y

)(

ν

s

)

→

t2

,

t11

,

t12

|

t1₁

−

s

srv_req

(

zreq

)

P_client P_provider1

→

t12

,

t21

,

t22

|

t2₂

−¯

s

quote

(

yquote

)

P_provider1P_client

→

t₁2

,

t3₂

,

t3₁

|

t3₁

,

accept

(

quote

)

? Pclient_t

:

Pclient_e

,

t41

)

|

Pprovider2

In thisway, the threads labelledby t5

1 andt42 are removed, whilethe threads performing the selection andoffering the branchingchoice,labelledbyt4

1 andt32 respectively,arerestored.

Then, intheprocess M,onlythe lastmemorycan triggerabackward reduction,whichundoestheconditional choice performedbytheclientthread.Similarly,otherbackwardreductionscanbesubsequentlytriggeredbytheothermemories, consumingthemfromthebottomtothetopoftheterm.Inthisway,theforwardcomputationcanbecompletelyreverted:

M

t1

:

Pclient

|

t2

:

Pprovider1

|

t3

:

Pprovider2

Now,theclientcanstartanewsession,possiblywithprovider2.

NoticethatinReS

π

thereisnoneedofexplicitlyimplementingloopsforenablingtheclienttoundoandrestartsessions. Notice also that here we do not consider speciﬁc primitives and techniques that avoid interacting againwith the same provider.ThiswouldbreaktheLoopLemma(seeLemma 5)andcomplicateourtheoreticalframework;wereferto[34]for adeﬁnitionofsomeofsuchcontrolledformsofreversibility.

5. Properties of the reversible calculus

We presentinthissection some propertiesof ReS

π

,whichare typically enjoyedbyreversible calculi. Weexploit ter-minology, argumentsandproof techniquesofpreviousworksonreversiblecalculi(inparticular,[15,5,20]).Asa matterof notation,wewilluse

P

and

R

todenotethesetof

π

-calculusprocessesandofReS

π

processes,respectively.

5.1. Correspondencewith

π

-calculus

WeﬁrstshowthatReS

π

isaconservativeextensionofthe(session-based)

π

-calculus.Infact,asmostreversiblecalculi,

ReS

π

isonlyadecorationofits hostcalculus.Suchdecorationcanbeerasedbymeansoftheforgetfulmap

φ

,whichmaps

ReS

π

termsinto

π

-calculusonesbysimplyremovingmemories,tagannotationsandtagrestrictions.

Deﬁnition 4 (Forgetfulmap).The forgetful map

φ

:

R

→

P

, mappinga ReS

π

process M intoa

π

-calculus process P , is inductivelydeﬁnedonthestructureofM asfollows:

φ (

t

:

P

)

=

P

φ ((

ν

c

)

N

)

= (

ν

c

)φ (

N

)

φ ((

ν

t

)

N

)

= φ(

N

)

φ (

N1

|

N2

)

= φ(

N1

)

| φ(

N2

)

φ (

m

)

=

0

φ (

nil

)

=

0

ToprovethecorrespondencebetweenReS

π

and

π

-calculus,we needthefollowingauxiliarylemmarelatingstructural congruenceofReS

π

tothatof

π

-calculus.

Lemma 1. LetM andN betwoReS

π

processes.IfM

≡

N then

φ (

M

)

≡ φ(

N

)

.

Proof. We proceedbyinductiononthederivationofM

≡

N (seeAppendixA.1.1).

2

Now, we can show that each forwardreduction of a ReS

π

process corresponds to a reduction of the corresponding

π

-calculusprocess.

(12)

Proof. We proceedbyinductiononthederivationofM

N (seeAppendixA.1.1).

2

ThecorrespondencebetweenReS

π

and

π

-calculusreductionsiscompletedbythefollowinglemmas, whichintuitively aretheinverseofLemma 1andLemma 2.

Lemma 3. LetP andQ betwo

π

-calculusprocesses.IfP

≡

Q thenforanyReS

π

processM suchthat

φ (

M

)

=

P thereexistsaReS

π

processN suchthat

φ (

N

)

=

Q andM

≡

N.

Proof. The proofisstraightforward(seeAppendixA.1.1).

2

Lemma 4. LetP andQ betwo

π

-calculusprocesses.IfP

→

Q thenforanyReS

π

processM suchthat

φ (

M

)

=

P thereexistsaReS

π

processN suchthat

φ (

N

)

=

Q andM

N.

Proof. We proceedbyinductiononthederivationofP

→

Q (seeAppendixA.1.1).

2

5.2. Looplemma

Thefollowinglemmashowsthat,inReS

π

,backwardreductionsaretheinverseoftheforwardonesandviceversa.

Lemma 5 (Looplemma).LetM andN betworeachableReS

π

processes.M

N ifandonlyifN

M.

Proof. The proof for the if part is by inductionon the derivation of M

N, while the proof for the onlyif part is by inductiononthederivationofN

M (seeAppendixA.1.2).

2

5.3. Causalconsistency

We show herethat reversibilityin ReS

π

iscausally consistent. Informally,this means that an action can be reverted onlyafteralltheactionscausallydependingonithavealreadybeenreverted.Inthisway,inthepresenceofindependent actions,backward computationsarenot requiredtonecessarilyfollowtheexact executionorderofforwardcomputations inreverse.Weformalisebelowthenotionsofindependent(i.e.,concurrent)actionsandofcausalconsistency.

Asin[15]and[5],werelyonthenotionoftransition.InReS

π

,atransition isatripletoftheformM

−−−−−−→

m,M, N (resp. M

−−−−−−→

m,M, N),where M and N areclosedreachableReS

π

processessuchthat M

N (resp. M

N),m is theactionor choicememoryinvolvedinthereduction,and

M

isthesetofforkmemoriespossiblyinvolvedinthereduction.Amemory isinvolved inareductionifitiscreatedorremovedbythereduction.Weuse

η

todenotetransitionlabels

(

m

,

M,

)

and

(

m

,

M,

)

.If

η

is

(

m

,

M,

)

,thenits inverseis

η

_•

= (

m

,

M,

)

andviceversa.Ina transitionM

−→

η N,we call M the source ofthetransitionandN itstarget.Weuse

τ

torangeovertransitions;

τ

• denotestheinverseoftransition

τ

.

Twotransitionsarecoinitial iftheyhavethesamesource,coﬁnal iftheyhavethesametarget,composable ifthetargetof oneisthesourceoftheother.Asequenceoftransitions,whereeachpairofsequentialtransitionsiscomposable,iscalleda

trace;weuse

σ

torangeovertraces.Notionsoftarget,sourceandcomposabilityextendnaturallytotraces.Weuse

M to

denotetheemptytracewithsource M and

σ

1

;

σ

2 thecompositionoftwocomposabletraces

σ

1and

σ

2.

WeconsideronlytransitionsM

−→

η N whereM andN donotcontainthreadsoftheformt

: (

P

|

Q

)

.Thisconditioncan bealwayssatisﬁedbysplittingallthreadsofthiskindintosub-threads, untiltheirdisappearanceintheconsideredterms, usingthestructurallawt

: (

P

|

Q

)

≡ (

ν

t1

,

t2

)(

t1

:

P

|

t2

:

Q

|

t

⇒ (

t1

,

t2

)

.Moreover,sinceconflictsbetweentransitionsare identifiedby meansoftagidentifiers (seeDefinition 5below),we onlyconsidertransitionsthat donotuse

α

-conversion on tags, andthat generatesfork memories in a deterministic way, e.g. given a memory

t

⇒ (

t1

,

t2

)

tags t1 andt2 are generatedbyapplyinganinjectivefunctiontot.

Thestamp

λ(

η

)

ofatransitionlabel

η

identiﬁes thethreadsinvolvedinthecorresponding transition,andisdeﬁnedas follows(weuseT todenoteasetoftags

{

ti

}

i∈I):

λ(

m

,

M

,

) = λ(

m

,

M

,

) = λ(

m

)

∪ λ

λ(m)

(

M

)

λ(

t1

−

A

→

t2

,

t₁

,

t₂

) = {

t1

,

t2

,

t₁

,

t₂

}

λ(

t

,

e? P

:

Q

,

t

) = {

t

,

t

}

λ

T

(

{

mi

}

i∈I

)

=

i∈I

λ

T

(

mi

)

λ

T

(

t

⇒ (

t1

,

t2

)

) =

{

t1

,

t2

}

if t

∈

T

∅

otherwise