Web apps and imprecise probabilities

Web Apps & Imprecise Probabilitites? Jorge Castro[0000−0002−1390−1313], Joaquim Gabarro[0000−0003−3771−2813], Maria Serna[0000−0001−9729−8648] ALBCOM. CS Dept. Universitat Polit` ecnica de Catalunya, Barcelona. {castro, gabarro, mjserna}@cs.upc.edu Abstract. We propose a model for the behaviour of Web apps in the unreliable WWW. Web apps are described by orchestrations. An orchestration mimics the personal use of the Web by defining the way in which Web services are invoked. The WWW is unreliable as poorly maintained Web sites are prone to fail. We model this source of unreliability trough a probabilistic approach. We assume that each site has a probability to fail. Another source of uncertainty is the traffic congestion. This can be observed as a non-deterministic behaviour induced by the variability in the response times. We model non-determinism by imprecise probabilities. We develop here an ex-ante normal to characterize the behaviour of finite orchestrations in the unreliable Web. We show the existence of a normal form under such semantics for orchestrations using asymmetric parallelism. Keywords. Web apps, orchestrations, Orc, imprecise probabilities, normal forms. 1 Introduction The appearance of the World Wide Web [4] deeply changed our every day life and in particular the way to interact with the world. In this paper we address the following problem: How to give an ex-ante (before execution) meaning of our interaction trough the Web. We model such interactions by means of orchestrations. An orchestration is the sequence and conditions in which one Web service invokes other Web services in order to realize some useful task [1]. An orchestration defines the flow control from a one-party perspective (in this case us) [17]. In general, before executing a Web app (for instance to search for flight info and get hotel reservations), we have an idea of the possible outcomes of the execution. Orchestrations are designed to address two main issues: –Interacting trough the Web using big doses of parallelism. We can have several browsers (like Mozilla, Chrome or Explorer) an try to get different pieces of information at the same time. ?J. Castro was partially supported by the Spanish Ministry for Economy and Competitiveness (MINECO) under grant (TIN2017- 89244-R) and the recognition 2017 SGR-856 (MACDA) from AGAUR (Generalitat de Catalunya). J. Gabarro and M. Serna were partially supported by MINECO and FEDER funds under grant GRAMM (TIN2017-86727-C2-1-R) and Generalitat de Catalunya, Ag´ encia de Gesti´ o d’Ajuts Universitaris i de Recerca, under project 2017 SGR 786 (ALBCOM). M. Serna was also supported by MINECO under grant BGSMath (MDM- 2014-044). Castro, J.; Gabarró, J.; Serna, M. Web apps and imprecise probabilities. A: International Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems. "Information Processing and Management of Uncertainty in Knowledge-Based Systems. Theory and Foundations, 17th International Conference, IPMU 2018: Cádiz, Spain, June 11-15, 2018: proceedings, part II". Cham: Springer, 2018, p. 226-238. DOI 10.1007/978-3-319-91476-3_19 –Web is unreliable. Sometimes the invoked service responds but others does not. Perhaps those Web services are no longer maintained or simply they are not available at this moment. A natural way to overcome unreliability is the use of redundancy. The causes of uncertainty depend deeply on the universe we are dealing with. For instance, the causes of uncertainty in economy [12,9] appear to be quite different from those on the Web. When a basic service is invoked, a site call is executed, the site can provide an answer returning some information or it can fail to (broken link). Moreover, this situation is far from being stable. Usually, based on our knowledge on the site behaviour or on external information, it is feasible to assume a priori probability for the broken (or silent) site event. In order to minimize the risk of calling a silent site, it is usual to issue several calls to sites providing similar information. In such a case the answer that arrives first is chosen. However, there is no a priori knowledge on which site will respond first [5] because in many cases becomes too hard to get sufficient data on the environment in order to provide precise probabilistic predictions. This lack of of precise probabilistic knowledge appears when considering an indeterministic behaviour. Following [3],we propose to model non-determinism in terms of imprecise probabilities. The ex-ante characterization of an orchestration, although formulated in terms of imprecise probabilities, has an obvious practical relevance. Let us consider an orchestration Pthat guarantees the result great success with an imprecise probability greater than 1/3 and obtains the satisfactory result with probability greater than 3/4. Let Qbe another orchestration that guarantees these same results with imprecise probabilities that are greater than, respectively, 1/4 and 4/5. Depending on our particular circumstances we can choose in a reasoned way which of the two processes, Por Q, is more convenient for our interests. Besides proposing the uncertainty model we extend the bag semantics for orchestrations proposed in [7] to deal with daemonic indeterminism through imprecise probabilities. This allows us to generalize the previous theorem on the existence of normal forms to a more general setting. Technically, Theorem 2 shows a normal form characterization for probabilistic orchestrations and Theorem 3 extends this result to the non-deterministic case. We complement this theoretical result by developing a complete example of uncertainty analysis in our proposed model. We also sketch other possible applications of imprecise probabilities to orchestrations. In order to make the paper self-contained we start introducing the Orc language [14]. We also recall the bag semantics [7] providing meaning to Orc expressions. 2 Orchestrations in reliable environments An orchestration is a user-defined program that utilizes services on the Web. In Orc [14] services are modelled by sites which have some predefined semantics. Typical examples of services are: an eigensolver, a search engine or a database. A site accepts an argument and publishes a result value1. For example, a call to a search engine, Find(s), 1The words “publishes”,“returns” and “outputs” are used interchangeably. The terms “site” and “service” are also used interchangeably. may publish the set of sites which currently offer service s. A site is silent if it does not publish a result. A site call can publish at most one response. Although a site call may have a well-defined result it may be the case that a call to the site, in an untrusted environment, fails (silence). Orc contains a number of inbuilt sites: 0is always silent while 1(x)always publishes x. An orchestration which composes a number of service calls into a complex computation can be represented by an Orc expression. An orchestrator may utilize any service that is available on the grid. In this paper we deal only with finite orchestrations where finite means: excluding iteration and recursion. Two Orc expressions Pand Qcan be combined using the following operators [14,11]: –Sequence P>x>Q(x):Pis evaluated and, for each value vpublished by P, an instance Q(v)is executed. If Ppublishes the stream, v1, v2,...vn, then P>x>Q(x)publishes some permuted stream of the outputs of the calls Q(v1), Q(v2), . . . , Q(vn). When the value of xis not needed we write PQ. –Symmetric Parallelism P|Q:Pand Qare evaluated in parallel. P|Qpublishes some interleaving of the streams published by Pand Q. –Asymmetric Parallelism P(x)< x < Q:Pand Qare evaluated in parallel. Some sub-expressions in Pmay become blocked by a dependency on x. The first result published by Qis bound to x, the remainder of Q’s evaluation is terminated and evaluation of the blocked residue of Pis resumed. Usually orchestrations assume some degree of redundancy. Following an example. Example 1. Suppose that you need to send news to a group. Usually you prefer the BBC but it is uncertain to get a result because there is a call for strike. In such a case, you also try to get news from the CNN ,News = (BBC |CNN ). To inform the group, you send the news to Alice, but at this moment you are uncertain about her capacity to get the email, therefore you send also the news to Bob, Emails(x) = (Alice(x)| Bob(x)). Consider the orchestration eNews =Emails(x)<x<News. Let us describe the behaviour of eNews. A call to eNews spans into simultaneous (parallel) calls (or threads) to News and Emails(x). The call to News span into parallel calls to BBC and CNN . The call to Emails(x)span into parallel calls to Alice(x)and Bob(x)At this moment the call to eNews has evolved into four simultaneous threads (the programs executing the calls) corresponding to BBC ,CNN ,Alice(x)and Bob(x). The thread corresponding to Alice(x)will remain blocked until variable xtakes a value. The same will happen with Bob(x). Eventually (at some future time) the calls to BBC and CNN return. Assume that BBC returns first, this value will be assigned to x. Once xhas a value, threads corresponding to Alice(x)and Bob(x)proceed and Alice and Bob will receive an email with the BBC news. Another result is possible if CNN returns first. In this case Alice and Bob get the CNN info. Note that eNews has no control about which result will appear, therefore is a non-deterministic program. ut To reason about a program, we need a semantics to assign meaning [6]. Bag semantics was introduced in [7] to give a precise description of the approach taken in Example 1. In such approach we abstract from return time. First, let us start from the operational semantics introduced in [14]. In such a model any variable xcontains all the possible values before being used. Therefore, variables keep a stream of values. When an orchestration Epublishes a stream v1, v2, . . . , vn,the relative ordering of the values depends on the relative response time of the sites appearing in E. However, when we are uncertain about return times, is a strongly desirable abstract from time. In such a case we forget about orderings in the streams describing them as a multi-set or bag bbv1, v2, . . . , vncc (notation bb · cc is taken from [13]). In such a case, the “meaning” of E, denoted by [[E]], is the bag bbv1, v2, . . . , vncc and we write [[E]] = bbv1, v2, . . . , vncc. The fact that site 0never returns is formalized as site 0re- turns nothing, that is [[0]] = bb cc =∅. As the pruning operator (or parallel asymmetric composition) can give rise to a non deterministic behaviour, we consider also the “daemonic choice” operator u[13, p. 4] to denote non deterministic choice. Toni Hoare in [10], considers the non-deterministic choice PuQbetween processes Pand Q. In such a case PuQdenotes a process which behaves like Por Q, where the selection is done without knowledge or control of the external environment. Such a choice is called daemonic choice. A semantic characterization of PuQin terms of refusal sets can be found in [10]. In a reliable environment, a call to a site Salways returns a value and we write [[S]] = bbscc. In the following examples we justify the use of bags and how they can be obtained from the simple bags corresponding to site calls. Example 2. [[BBC ]] = bbbbccc and [[CNN ]] = bbcnncc. A call to News in the preceding Example 1 returns a bag containing two items, [[News]] = [[BBC |CNN ]] = bbbbc,cnncc. This result is consistent with the idea that in News the BBC and the CNN are called in parallel an they return at different moments. The orchestration has no control on which one will return first. The bag bbbbc,cnncc mimics the idea that eventually we will get both results but we forget temporal information. ut Sometimes we want to introduce redundancy as, for example in TwiceBBC = (BBC |BBC ). Observe that this orchestration returns bbbbc,bbccc mimicking the idea of getting twice the same result. Showing the need of using bags (or multisets). Sometimes we get expressions that depend on the values that a variable gets during the execution. In such a case, the bag semantics provides a meaning for the variable that is used to derive the meaning of the expression. Besides in a reliable environment, asymmetric parallelism introduces indeterminism. The following example illustrates those traits. Example 3. Now we face the meaning of xappearing in eNews =Emails(x)< x < News. According to Example 2 we have [[News]] = bbbbc,cnncc. As we do not control explicitly the return times, under some (external and uncontrolled) circumstances, a call News returns bbc but in some other cases it returns cnn. So, xcan hold either of both values, i.e., [[x]] = bbbbccc u bbcnncc. Assuming [[Emails(x)]] = bbalice x,bob xcc, [[eNews]] = [[Emails(bbc)]] u[[Emails(cnn)]] =bbalice bbc,bob bbccc u bbalice cnn,bob cnncc This result translates the idea that, depending on external circumstances, two possible output streams are possible: Alice and Bob get the BBC or Alice and Bob get the CNN.The orchestrator has no control on which one will occur. ut Working in a similar way with the different operations the existence of a normal form can be shown. Theorem 1 ([7]). Given an Orc expression Eit holds that either [[E]] = bb cc or there is a unique non-deterministic finite decomposition in multi-sets [[E]] = uiMi, where elements in Micorresponds to the possible values returned by site calls. 3 Orchestrations & probabilistic information Until now, we have considered reliable orchestrations as we were certain about returns. In this section, we consider unreliable settings modelled with probabilities. Let ∆n={(p1, . . . , pn)|pi≥0,1≤i≤n, Pn i=1 pi= 1}. We adopt from [13] the notation (prog1@p1[] prog2@p2[] · · · [] progn@pn)where (p1, . . . , pn)∈∆nand (prog1,...,progn)are sequential programs to represent a probabilistic program that behaves like progiwith probability pi. The probabilistic choice follows two natural laws [15,13]. When the same program prog1appears twice, we should add the probabilities: (prog1@p1[] prog1@p2[] prog3@p3[] · · · [] progn@pn) =prog1@(p1+p2) [] prog3@p3[] · · · [] progn@pn. The second rule assumes distributivity in respect to the daemonic choice operator. (prog1uprog0 1)@p1[] prog2@p2[] · · · [] progn@pn = (prog1@p1[] · · · [] progn@pn)u(prog0 1@p1[] prog2@p2[] · · · [] progn@pn). Sometimes we can model a faulty uncertain behaviour by a probability distribution on the involved processes, but this is not always possible. We have two semantic models for faulty behaviour. –Probabilistic information. In this case we model a faulty site as a site Sreturning swith a probability p, and failing to return (behaves like site 0) with probability (1 −p). The faulty version of S, denoted as SFis SF= (S@p[] 0@(1 −p)). Moreover [[SF]] = [[S]]@p[] bb cc@(1 −p)=bbscc@p[] bb cc@(1 −p). We identify bbscc@1 [] bb cc@0=bbscc and bbscc@0 [] bb cc@1=bb cc. We assume probabilistic independence on the behaviour of the sites. Two consecutive calls to a given site are considered independent in relation to its probabilistic behaviour. –No probabilistic information. In such a case, we assume indeterminism, i.e., [[SF]] = [[S]] u bb cc. When it is clear from the context that Sis faulty, we denote SFshortly as S. Example 4. Suppose that, from a user point of view, sites CNN and BBC are unreliable, [[BBC ]] = bbbbccc@2/3 [] bb cc@1/3and [[CNN ]] = bbcnncc@1/2 [] bb cc@1/2. A precise semantics for [[News]] comes from the way in which probabilities interact with parallel composition [7]. Assuming independence among executions, the probabilistic behaviour is given in the following table: bbbbccc@2/3bb cc@1/3 bbcnncc@1/2bbcnn,bbccc@(1/2×2/3) bbcnncc@(1/2×1/3) bb cc@1/2bbbbccc@(1/2×2/3) bb cc@(1/2×1/3) Therefore [[News]] = bbcnn,bbccc@1/3 [] bbcnncc@1/6 [] bbbbccc@1/3 [] bb cc@1/6. Different bags can represent the orchestration result. The empty bag bb cc appears when both sites fail. This result is different form the one in Example 2 where only the bag bbcnn,bbccc appears. ut Probabilistic distributions are parametrized when sites are parametrized S(x1,...xn): [[S(x1,...xn)]] = bbs(v1, . . . , vn)cc if (x1,...xn) = (v1,...vn) bb cc if ∃i: 1 ≤i≤n:xiundefined Example 5. Suppose that Alice succeeds (or returns) with probability 4/5and Bob returns with probability 5/7. In the case of Alice we have: [[Alice(x)]] = (bbalice vcc@4/5 [] bb cc@1/5if x=v bb cc if xis undefined When x=bbcnncc it holds [[Alice(cnn)]] = bbalice cnncc@4/5 [] bb cc@1/5. When xis undefined, x=bb cc and [[Alice(bb cc)]] = bb cc. When it is clear from the context, we write [[Alice(x)]] = bbalice xcc@4/5 [] bb cc@1/5assuming implicitly that, when xis undefined [[Alice(x)]] = bb cc. Let Emails(x)be (Alice(x)|Bob(x)). The semantics is bbalice x,bob xcc@4/7 [] bbalice xcc@8/35 [] bbbob xcc@1/7 [] bb cc@2/35. When x=bbcnncc, the semantics of Emails(cnn)is bbalice cnn,bob cnncc@4/7 [] bbalice cnncc@8/35 [] bbbob cnncc@1/7 [] bb cc@2/35, and, when xis undefined, [[Emails(x)]] = bb cc .ut The tools described in Examples 4 and 5 can be generalized. We can show that when there is no asymmetric parallelism (no indeterminism) probabilistic information can be carried out through constructors. Based on the approach given in [7], we can shown the existence of a normal form. Theorem 2. Let Ebe a finite orchestration, defined trough sequencing and parallel composition over ndifferent faulty sites. Assume site isucceeds and returns a value with probability pi. Under the bag semantics, there is a probabilistic finite choice decomposition in multisets [[E]] = [] jMj@Fj(p), elements in Mjcorresponds to the possible values returned by site calls, parameter pis the success probability vector (p1, . . . , pn), and Fjis an arithmetic expression defined on p. 4 Daemonic choice & imprecise probabilities We consider in this section the more general case of a non-deterministic orchestration defined on a faulty environment. In order to provide a semantic characterization, we keep probabilistic information as much as possible and encode non-deterministic choices as imprecise probabilities. In this way, the behaviour of a non-deterministic choice on nprocesses P1uP2u· · · uPncorresponds to any of the possible behaviours defined by an imprecise probability choice: {(P1@p1[] P2@p2[] · · · [] Pn@pn)|(p1, p2,...pn)∈∆n)}. Consequently, we identify the meaning [[P1uP2u · · · u Pn]] with {([[P1]]@p1[] [[P2]]@p2[] · · · [] [[Pn]]@pn)|(p1, p2,...pn)∈∆n)}. Let us observe that in the asymmetric parallelism operation the non deterministic choices are restricted to the selection of an element from a multiset. The following example attempts to to grasp the relation between our approach and imprecise probabilities. Example 6. To assign a meaning to eNews, recall from Example 4 that [[News]] = bbcnn,bbccc@1/3 [] bbcnncc@1/6 [] bbbbccc@1/3 [] bb cc@1/6 We like to keep this probabilistic information as much as possible in [[x]]. As [[x]] has to be some possible multisets with at most one element we translate bbcnn,bbccc into bbcnncc u bbbbccc. In a first approach [[x]] should be the process bbcnncc u bbbbccc@1/3 [] bbcnncc@1/6 [] bbbbccc@1/3 [] bb cc@1/6. Modelling non-determinism by imprecise probabilities [[bbcnncc u bbbbccc]] = {bbcnncc@p1[] bbbbccc@p2|(p1, p2)∈∆2} Substituting in the previous expression, we get [[x]] = nbbcnncc@1 2p1[] bbbbccc@1 3p1[] bb cc@1 6p1 [] bbcnncc@1 6p2[] bbbbccc@2 3p2[] bb cc@1 6p2|(p1, p2)∈∆2o. Regrouping terms we get for [[x]] nbbcnncc@1 2p1+1 6p2[] bbbbccc@1 3p1+2 3p2[] bb cc@1 6|(p1, p2)∈∆2o Observe that, although the characterization of [[x]] is imprecise, we can assure that the probability of having cnn as a result lies in the interval [1/6,1/2] and that the probability of bbc lies in [1/3,2/3]. We rewrite [[x]] as : {(bbcnncc@p[] bbbbccc@q[] bb cc@1/6) |p∈[1/6,1/2], q ∈[1/3,2/3], p +q= 5/6} Assuming the semantics of Emails(x)in Example 5, then [[eNews]] is n[] bbalice cnn,bob cnncc@4 7p[] bbalice cnncc@8 35p[] bbbob cnncc@1 7p [] bbalice bbc,bob bbccc@4 7q[] bbalice bbccc@8 35q[] bbbob bbccc@1 7q [] bb cc@3 14)|p∈[1/6,1/2], q ∈[1/3,2/3], p +q= 5/6o. The meaning [[eNews]] provides, for each possible output stream, a probability interval. This quantitative information may be relevant in any discussion about the appropriateness of this orchestration. ut Our next result provides a generalization of a similar result in [7]. We are able to include asymmetric parallelism in the bag semantics and devise a normal form. The proof is by induction on the structure of the orchestration and uses formalizations of the preceding ideas. Theorem 3. Let Ebe a finite faulty orchestration, defined trough sequencing, parallel composition and asymmetric parallelism over ndifferent faulty sites. Assume that site i succeds an returns a value with probability piand let p= (p1, . . . , pn). Under the bag semantics, encoding the daemonic choice due to asymmetric parallelism into imprecise probabilities, there are multisets M1,...M`and a Cartesian product of probability spaces ∆m1× · · · × ∆mksuch that [[E]] = M1@F1(p, δ) [] · · · [] Ml@Fl(p, δ)|δ∈∆n1× · · · × ∆nk. Multiset’s elements correspond to possible values returned by by site calls and formulas Fjare arithmetic expressions defined on the success probability vector pand a tuple of distributions δ. 5 An example of application In order to clarify the measurable probabilities p= (p1, . . . , pn)and the source for imprecise probabilities δ∈∆n1× · · · × ∆nkappearing in Theorem 3 we analyse the meaning on a longer orchestration. Consider the orchestration EmailFlightHotel sending to Alice information about flights and hotels. Three hotels are asked to give information: Hotels = (H1|H2|H3) and two flight companies are contacted: Flights = (F1|F2). Thus, EmailFlightHotel =Alice(f, h)< f < Flights <h<Hotels The set of sites is {H1, H2, H3, F1, F2,Alice(f, h)}. The success probabilities are respectively {1/2,1/3,1/4,1/5,1/6,2/3}. Observe that [[Hotels]] = bbh1, h2, h3cc@1/24 [] bbh1, h2cc@3/24 [] bbh1, h3cc@2/24 [] bbh2, h3cc@1/24 [] [] bbh1cc@6/24 [] bbh2cc@3/24 [] bbh3cc@2/24 [] bb cc@6/24 Note that any probability appearing in [[Hotels]] is a funcion of the success probability of H1, H2, H3given by p= (1/2,1/3,1/4). For instance the 6/24 appearing in bbh1cc@6/24 is computed as 6/24 = 1/2(1 −1/3)(1 −1/4). To assign a meaning to h, each multiset gets an imprecise probability on its elements. That is bbh1, h2, h3cc =bbh1cc@p1,1[] bbh2cc@p1,2[] bbh3cc@p1,3|(p1,1, p1,2, p1,3)∈∆3 bbh1, h2cc =bbh1cc@p2,1[] bbh2cc@p2,2[] |(p2,1, p2,2)∈∆2 bbh1, h3cc =bbh1cc@p3,1[] bbh3cc@p3,3|(p3,1, p3,3)∈∆2 bbh2, h3cc =bbh2cc@p4,2[] bbh3cc@p4,3|(p4,2, p4,3)∈∆2 Define δ= (p1,1, p1,2, p1,3, p2,1, p2,2, p3,1, p3,3, p4,2, p4,3)∈∆3×∆2×∆2×∆2, then: [[h]] = {bbh1cc@Ph1[] bbh2cc@Ph2[] bbh3cc@Ph3[] bb cc@Ph∅[] }where: Ph1=1 24(p1,1+ 3p2,1+ 2p3,1+ 6) Ph2=1 24(p1,2+ 3p2,2+p4,2+ 3) Ph3=1 24(p1,3+ 2p3,3+p4,3+ 2) Ph∅=6 24 Note that Phiis a function of pand δpreviously defined, that is Phi=Fhi(p, δ), similarly for Ph∅. Working in a similar way. [[Flights]] = bbf1, f2cc@1/30 [] bbf1cc@5/30 [] bbf2cc@4/30 [] bb cc@20/30 In this case the probabilities appearing in [[Flights]] are function of p0= (1/5,1/6). There is just one bag with more than one element, then bbf1, f2cc ={bbf1cc@q1,1[] bbf2cc@q1,2|(q1,1, q1,2)∈∆2} Defining δ0= (q1,1, q1,2)∈∆2. So, [[f]] = {(bbf1cc@Qf1[] bbf2cc@Qf2[] bb cc@Qf∅)} where Qf1=1 30(q1,1+ 5), Qf2=1 30(q1,2+ 4), Qf∅=20 30. Finally, [[EmailFightHotel]] ={bbalice f1h1cc@P1[] · · · [] bb cc@P∅| · · · } ={bbalice f1h1cc@2 3Qf1Ph1[] · · · [] bb cc@1 3Ph∅Pf∅)| · · · } ={bbalice f1h1cc@2 31 30q1,1+5 301 24p1,1+3 24p2,1+2 24p3,1+6 24[] · · · [] bb cc@1 3·6 24 ·20 30| · · · } Define p00 as the array associated to the Alice probability of success, p00 = (2/3). Defining (with a small abuse of notation): δ= (δ, δ0) = (p1,1, p1,2, p1,3, p2,1, p2,2, p3,1, p3,3, p4,2, p4,3, q1,1, q1,2) p= (p, p0, p00) = (1/2,1/3,1/4,1/5,1/6,2/3)