Fairness in systems based on multiparty interactions

Fairness in systems based on multiparty interactions David Ruiz∗,†, Rafael Corchuelo and Miguel Toro ETSI Inform´atica, Avda. de la Reina Mercedes s/n, Sevilla E-41012, Spain SUMMARY In the context of the Multiparty Interaction Model, fairness is used to insure that an interaction that is enabled sufficiently often in a concurrent program will eventually be selected for execution. Unfortunately, this notion does not take conspiracies into account, i.e. situations in which an interaction never becomes enabled because of an unfortunate interleaving of independent actions; furthermore, eventual execution is usually too weak for practical purposes since this concept can only be used in the context of infinite executions. In this article, we present a new fairness notion, k-conspiracy-free fairness, that improves on others because it takes finite executions into account, alleviates conspiracies that are not inherent to a program, and k may be set a priori to control its goodness to address the above-mentioned problems. KEY WORDS: concurrent programs; multiparty interactions; fairness; fair finiteness; conspiracies 1. INTRODUCTION In this article, we focus on fairness in concurrent systems that use the Multiparty Interaction (MI) model. A multiparty interaction is an abstraction that allows several processes to synchronize and exchange information coordinately. Fairness becomes essential in MI-based systems since an MIbased process may offer to participate in several interactions, although it can execute only one at a time [1]. Intuitively, an execution of a program is fair iff every interaction that is ready for execution sufficiently often is executed sufficiently often, which avoids executions in which such interactions are neglected. Notice that ‘sufficiently often’ is a vague term, which implies that there is not a single prevailing definition. However, many researchers agree in that so-called strong fairness deserves attention ∗Correspondence to: David Ruiz, ETSI Inform´atica, Avda. de la Reina Mercedes s/n, Sevilla E-41012, Spain. †E-mail: [email protected].us.es Contract/grant sponsor: Spanish Ministry of Science and Technology; contract/grant numbers: TIC-2000-1106-C02-01; FIT-150100-2001-78; TAMANSI PCB-02-001 because it may induce desirable properties such as termination or eventual response to a request for service [1–3]. Unfortunately, this notion is not restrictive enough since it does not take finite executions into account, and an interaction might never get ready for execution because of an unfortunate interleaving of independent actions that might prevent some of the processes that need it to coordinate from engaging it at the right time. This has motivated several authors to work on stronger fairness notions, but none of them solves both problems simultaneously [4–7]. The main contribution we present in this article is a new fairness notion called k-conspiracy-free fairness that addresses the above-mentioned problems by fine-tuning the value we assign to k.Wealso present a framework we have devised to implement fair MI-based systems and report on the results of an experimental analysis we conducted to compare our proposal with others. From these results, we conclude that our proposal allows one to control conspiracies efficiently and it is easier to apply since our implementation is generic, i.e. it is not a transformational approach and thus needs not transform the source code of the systems to which it is applied. The rest of the article is organized as follows. In Section 2, we report on some related work about multiparty interactions, fairness notions, and summarize how we improve other authors’ work. The foundations of our framework are presented in Section 3and in Section 4, we introduce our fairness notion and define it rigorously. We report on how to implement our fairness notion and on our experimental results in Sections 5and 6, respectively. Finally, some conclusions are drawn from previous parts and summarized in Section 7. 2. RELATED WORK In this section, we first present the MI model. Later, we report on current fairness proposals and argue on their deficiencies. Finally we summarize our contributions. 2.1. Multiparty interactions The MI model provides interactions as the sole means for process synchronization and communication [1,8–10], and it has been proven to achieve optimal concurrency and/or parallelism in some common situations [11]. Contrarily to the usual message-passing model, which emphasizes two processes exchanging messages and, thus, communication, multiparty interactions focus on agreement amongst multiple parties that need to cooperate in order to achieve a common goal, e.g. transferring money from a bank to another by means of a point of sales terminal (three processes) [12], paying taxes on-line (three processes in Spain: a taxpayer, the Exchequer, and Spain’s Certification Authority), filtering in e-commerce [13] (a customer, a filter system, and several service providers), or reaching a virtual agreement in an auction sale (multiple processes). Reference [10] provides a complete taxonomy of languages that support this interaction model, and recent contributions presented in [12,14,15] have extended Java to support multiparty interactions to some extent. In [8], the model was further researched and combined with aspect orientation. Roughly speaking, a multiparty interaction can be viewed as an abstract coordination mechanism that allows a set of processes, each of which must be ready to participate in the interaction so that it can occur, to execute data exchange actions jointly and coordinately. (When this happens, the interaction is said to be ready for execution or enabled.) An attempt to participate in an interaction delays a process until all other participants are available, and after an interaction is executed, the participants exchange some data and continue their local computations separately. Notice that an interaction being enabled does not entail its execution since it may be linked to other interactions in which a common process is willing to participate. Since a process can execute only one interaction at a time, an election under the linked interactions needs to be held. Intuitively, the selection procedure must be fair to avoid executions in which an interaction is never executed or never has a chance to become enabled. A classical problem to illustrate the adequacy of multiparty interactions is the Dining Philosophers Problem. The obvious message-passing solution consists of sending requests to the forks to get them in sequence, but a deadlock may occur if each philosopher grabs the fork on his/her right, and then waits for the fork on his/her left to be released. In [16], it was proven that assuming no means of communication amongst philosophers other than through information attached to their forks, any solution in which all philosophers are programmed identically must have a possibility of deadlock. Thus, correct solutions must rely on some distinction to be made amongst the philosophers. These solutions are usually not scalable or reusable since the distinction a philosopher has to implement depends heavily on the topology of the problem. If we used multiparty interactions, the solution would be simpler since each philosopher would pick up his/her two forks at a time so that no deadlock could arise. Figure 1shows an MI-based dining philosophers system based on the IP language [1]. (A brief introduction to IP is presented in Appendix A.) The philosophers are represented by processes Pi, and the forks by processes Fi(i∈[1...N]). Each Pifirst tries to get its forks by participating in the three-party interaction Getitogether with Fiand Fi−1. (We assume that subindex arithmetic is module N.) Thus, acquiring a resource is specified as synchronizing with the corresponding processes in a multiparty interaction. After Pihas got its forks, it eats, releases the forks, spends some time thinking and the whole process is repeated once again. Notice that interactions Geti−1,Getiand Geti+1 are linked for every i∈[1...N], but only one of them can be executed at the same time. The only way to guarantee that each interaction that is enabled sufficiently often shall eventually be selected for execution consists of assuming that the underlying selection mechanism is fair. (It is known that fairness is mandatory in systems in which processes need mutual exclusion to a resource [17].) 2.2. Fairness In [18], the authors introduced several properties that deserve special attention in the context of concurrent systems. They classified them into two groups, namely: safety properties, which assert that ‘something bad’ does not happen, and liveness properties, which assert that ‘something good’ must happen eventually. In concurrent programming, usual bad things are deadlocks or the violation of critical regions. In contrast, usual good things are the absence of starvation, the response to a request for service or termination. Fairness is sometimes the only way to guarantee these liveness properties, but, unfortunately, there is not a single prevailing definition. Many authors [1–3], however, agree in that strong fairness (SF) deserves attention since it may induce desirable liveness properties. Technically, an execution is strongly fair iff every interaction that is enabled infinitely often is executed infinitely often. This prevents an interaction that is enabled from time to time, not necessarily permanently, from being neglected. For instance, in the system in Figure 1, the only way to guarantee that each philosopher is able to eat as much as the rest is by assuming that the underlying scheduler is fair, i.e. this is the only way to insure that every request for service a philosopher makes to a fork is satisfied eventually. DINNER :: [||N i=1Pi||Fi], where Pi:: *[ Geti → eat;Rel i;think ] Fi:: *[ Geti → Reli Geti+1 → Reli+1 ]. (a) Rel 2 Rel 3 Rel 4 Rel 5 Get 2 Get 3 Get 4 Get 5 P 1 P 2 P 3 P 4 P 5 F 1 F 5 F 4 F 3 F 2 N=5 Rel 1 Get 1 (b) Figure 1. A solution to the dining philosophers problem in IP: (a) the IP code to implement the system; (b) sketch of a system with five philosophers. In spite of its adequacy in the context of MI-based systems, strong fairness suffers from two practical problems that may lead to undesirable executions. Fair finiteness. The first problem lies in the fact that strong fairness is a void property [19]. That is, the strong fairness fulfillment of an execution cannot be checked by performing finite experiments. Thus, there is no way to show that a scheduler produces strongly fair executions by analysing the results of an experiment. Furthermore, every finite execution is strongly fair by default [2]. Figure 2(a) shows an event trace of the system in Figure 1(N=5). Notice that interaction Get2 is enabled ntimes, but it is never selected during this execution. Given that strong fairness is a void property, there is no finite experiment from which we can conclude that the scheduler that produced this execution is not strongly fair. This implies that strong fairness may lead to a situation in which an interaction is never selected in a long-enough finite execution [4]. P1.{Get1},P 2.{Get2},F 2.{Get2,Get 3}, (F 5.{Get5,Get 1},F 1.{Get1,Get2},Get1, P1.{Rel1},F 1.{Rel1},F 5.{Rel1},Rel1,P 1.{Get1})n (a) P1.{Get1},P 2.{Get2},P 3.{Get3}, (F 5.{Get5,Get 1},F 3.{Get3,Get 4},F 1.{Get1,Get 2},Get1, F2.{Get2,Get 3},Get3,P 1.{Rel1},F 1.{Rel1},F 5.{Rel1},Rel1, P3.{Rel3},F 2.{Rel3},F 3.{Rel3},Rel3,P 1.{Get1},P 3.{Get3})∞ (b) Figure 2. Problems with strong fairness: (a) fair finiteness; (b) conspiracies. (p.χ means that process poffers to participate in any interaction in set χ,andxthat interaction xis executed.) S::[P|| Q], where P::*[A → B C → skip ] Q::*[A → [B → skip C → skip] ]. Figure 3. A program with inherent conspiracies. Conspiracies. Furthermore, a scheduler may lead to executions in which all of the processes that may participate in an interaction are ready to participate in it from time to time, but it never becomes enabled because of an unfortunate interleaving that prevents them from offering to participate at the same time, i.e. some participating processes decide to execute another interaction before the former becomes enabled. These situations are commonly referred to as conspiracies [20,21]. Figure 2(b) shows a good example in which interaction Get2is readied by all of its participants infinitely many times, but never gets enabled. Although the execution is strongly fair, this conspiracy is undesirable and should be avoided. There are programs, however, in which conspiracies are inherent. For instance, the event traces of the program in Figure 3are of the form (P.{A,C},Q.{A},A,P.{B},Q.{B,C},B)∞. The conspiracy against Cis unavoidable since it is inherent to this program. Individually, these problems have been studied by several authors [4–7,22], giving rise to new fairness notions. Amongst them, we focus on finitary (strong) fairness [4]and(strong) hyperfairness [5] because these approaches focus on concurrent programming, whereas the others focus on self-stabilizing algorithms [6], classical temporal logic [7] and temporal logic of actions [3,22]. Table I. Comparison with related work. Notion Brief description Fair finiteness Conspiracies SF Every interaction that becomes enabled infinitely No No often is selected infinitely often. HF Every interaction that is offered infinitely often by No Yes all of its participants becomes enabled infinitely often. FF Every interaction that becomes enabled infinitely Yes No often is selected at least once every ktimes it is enabled. CFFkNo interaction is selected more than ktimes Yes Yes without analysing the state of the interactions that are linked to it. Finitary fairness (FF). Alur et al. [4] solved the finiteness problem and provided us with a new notion that needs to be combined with others. If it is combined with strong fairness, then the term ‘infinitely often’ is replaced by ‘at least once every ktimes’, where kis a natural number that must exist, but is not known apriori. Therefore, it is said that an execution is finitarily strong fair iff there exists a natural number ksuch that no interaction is rejected more than ktimes consecutively. This notion has several drawbacks, namely (i) kis known a posteriori, which implies that it cannot be set apriorito regulate a system; (ii) its implementation is transformational; (iii) it does not attempt to solve conspiracies or alleviate them since the authors do not focus on MI-based systems. Hyperfairness (HF). Attie et al. [5] studied conspiracies in the context of the IP language and defined hyperfairness to solve it. It is said that an execution is hyperfair iff every interaction is conspiracyresistant, i.e. it is offered by all of their participants infinitely often. Notice that this notion insures that an interaction that can eventually become enabled, becomes enabled, which does not necessarily entail it is selected for execution; thus, it needs to be combined with other notions. It has some drawbacks, namely (i) the set of interactions that are conspiracy-resistant needs to be pre-computed, but the authors do not provide us with an algorithm to do so; (ii) its implementation is transformational, but the authors do not provide us with a generic algorithm to perform transformations; (iii) the authors combine it with strong fairness only, which does not solve the fair finiteness problem. 2.3. Our contributions The main contribution we present in this article consists of a new fairness notion that is more restrictive than strong fairness and addresses both the fair finiteness problem and conspiracies simultaneously, as we show in Table I. We refer to this notion as k-conspiracy-free fairness or CFFkfor short. We think that previous attempts to solve these problems have not addressed them simultaneously since they focused on different settings. For instance, the work by Alur et al. on finitary fairness focuses on concurrent systems that are not MI-based; thus, no conspiracy situations may occur. The work by Attie et al. focuses on MI-based systems and it laid the foundations of hyperfairness; unfortunately, their ideas were not developed to their full extent but they deserve attention since they were the first to identify the problem and devise a solution. Very recently, Lamport [3,22] considers hyperfairness a corner-stone of action-based concurrent systems and recognizes the need for further research on this topic. Hyperfairness does not focus on fair finiteness since the authors were not interested in solving a practical problem, but in providing a notion to preserve a property called equivalence robustness, which is mandatory for a notion to be fully adequate according to the criteria in [2,23]. Conspiracies constitute a major obstacle to preserving this property, so they should be avoided. Our proposal builds on previous theoretical work by these authors and addresses both problems from a practical standpoint since we are not interested in proving theoretical properties, but on materializing those concepts into a notion that solves practical problems. As we prove in Section 6,the implementation of our notion performs comparably to other researchers’ implementations of strong fairness; however, since our notion depends on the value we assign to kbeforehand, this parameter may help us control how well it addresses both problems. The parameter can thus be seen as a trade-off between effectiveness and efficiency: the smaller the value of k, the better the control of the conspiracies, but the less efficient the implementation; the greater the value of k, the poorer the control of the conspiracies, but the more efficient the implementation. Furthermore, the implementation of our proposal is not transformational, which may be seen as a practical advantage since it can be applied to any MI-based system without requiring us to change its source code to transform it into an equivalent fair system. Roughly speaking, we can produce a generic scheduler that can be used in any MI-based system, whereas other proposals need to be adapted to particular systems and transform their source code to produce ad hoc schedulers. From a theoretical standpoint, both approaches are sound, but from a practical standpoint having a generic scheduler seems to be a better idea; otherwise, we would need to have access to the source code to transform it, which is impossible if we are dealing with processes obtained from a component which is available in binary form only, e.g. a C++ library or a CORBA object. 3. A THEORETICAL FRAMEWORK TO DESCRIBE MI-BASED SYSTEMS In this section, we present the foundations we need to define our notion rigorously, which we think is very important so that other authors can repeat our work. Later, we show that the framework we have designed allows us to describe other authors’ notions. Thus, the implementation we present in Section 5can be seen as a generic harness to implement MI-based systems and fairness notions. 3.1. Definitions The core of the framework is a set of definitions with which we define rigorously the concepts presented previously. We use the dining philosophers system in Figure 1to illustrate some of them. Definition 1. (MI systems) A system is a 2-tuple of the form (P,I)in which P=∅is a finite set of processes and I=∅is a finite set of interactions. We denote the set of processes that may eventually offer to participate in interaction xas P(x), and the set of interactions that process pcan offer as I(p). In our example, we have an MI-based system composed of N=5 philosopher processes called Piand Nfork processes called Fi(i∈[1...N]). These processes are synchronized by means of N interactions called Getito take the forks and five interactions called Relito release them. For instance, the set of processes participating in interaction Getiis P(Geti)={Fi−1,Pi,Fi}, and the set of interactions in which Fimay participate is I(Fi)={Geti,Reli,Geti+1,Reli+1}. Definition 2. (Events) An event is a happening that induces a system to transit from a configuration to another. (A configuration is an object that may be viewed as a snapshot of a system at run time.) In our model, we take the following kinds of events into account. •Offering event. p.χ indicates that process pis offering to participate in an interaction in set χ. Notice that if χ=∅, process parrives at a fixed point that we may interpret as its termination because it can neither perform local computation nor execute any interaction. •Synchronization. xindicates that interaction xhas been selected for execution. For instance, when philosopher Pioffers to participate in interaction Geti, an event of the form Pi.{Geti}occurs; similarly, when Pitakes its forks, an event of the form Getioccurs and synchronizes the execution of Pi,Fiand Fi−1(i∈[1...N]). Definition 3. (Executions) An execution of system is a 3-tuple (C0,α,β) in which C0is the initial configuration, α=[C1,C 2,C 3,...]is a maximal (finite or infinite) sequence of configurations, and β=[e1,e 2,e 3,...]is a maximal (finite or infinite) sequence of events responsible for the transition between every two consecutive configurations. (Obviously, |α|=|β|.) Finally, let λ=(C0,α,β) be an execution of system . We call αits configuration trace and denote it as λα,andβits event trace and denote it as λβ. Consider, for instance, the execution below: λ=(C0,α,β) α=[C1,C 2,C 3,C 4,...] β=[P1.{Get1},F5.{Get5,Get1},F1.{Get1,Get2},Get1,...] Philosopher P1starts offering interaction Get1,forkF5then offers interactions {Get5,Get1},and fork F1interactions {Get1,Get2}. Interaction Get1becomes enabled at configuration C3and, in this case, it is executed and the program continues. Definition 4. (Semantics) We denote the rule that captures the underlying semantics that control the transition between configurations as L. For instance, CeLCindicates that the system may transit from configuration Cto configuration Con occurrence of event e.Thus,givenan execution λ=(C0,[C1,C 2,C 3,...],[e1,e 2,e 3,...]), we usually write it as C0e1LC1e2L C2e3L···. Our example is implemented in IP, thus Lamounts for IP. Please, consult [1] for a complete description of the semantics of the IP language or Appendix Afor a brief introduction. Definition 5. (Processes) Process pis waiting for an interaction in set ϒ=∅at the ith configuration in execution λiff it has arrived at a point in which it may execute any x∈ϒ, i.e. it has offered to participate in a subset of interactions χ⊇ϒand no interaction in ϒhas been selected since that moment. Process pis finished at the ith configuration in execution λiff it has offered to participate in an empty set of interactions, that is, it can neither perform local computations nor interact with other processes. Waiting(λ,p,ϒ,i) ⇐⇒ ∃ χ⊇ϒ,k ∈[1...i)·(λβ(k) =p.χ ∧j∈(k...i]·λβ(j) =x∧x∈ϒ) Finished(λ, p, i) ⇐⇒ ∃ k∈[1...i]·λβ(k) =p.∅ In our example, philosopher Pjis readying the set of interactions {Getj}(j∈[1...N]) at configuration Ci(i∈[1...|λ|])ifaneventPj.{Getj}happened before Ciand interaction Getjwas not selected since that moment. Definition 6. (Interactions) Interaction xis enabled at the ith configuration in execution λiff all of the processes in P(x) are offering xat that configuration, that is, all of its participants are waiting for it to be selected. Interaction xis stable at the ith configuration in execution λiff its participants are finished or waiting for an interaction, whichever it is. Enabled(λ,x,i) ⇐⇒ ∀ p∈P(x) ·Waiting(λ, p, {x},i) Stable(λ, x, i) ⇐⇒ ∀ p∈P(x) ·(Finished(λ,p,i)∨∃ϒ⊆I·Waiting(λ,p,ϒ,i)) Interaction Getjis enabled at the ith configuration iff all of its participants (Pj,Fjand Fj−1)are offering it. Furthermore, Reljis stable because its participants are waiting for Getj. Notice that enablement implies stableness, but the converse is not true in general. Definition 7. (Miscellaneous) Let λbe an execution and xan interaction. We define the following sets at the ith configuration: 1. Interactions linked to x: the set of interactions that share a participant with x. Linked(λ,x,i)={y∈I|P(x) ∩P(y) =∅} 2. Set of enablements: the set of indices up to ithat identify the configurations at which interaction x is enabled. EnaSet(λ, x, i) ={k∈[0...i]|Enabled(λ,x,k)} 3. Set of executions: the set of indices up to ithat identify the configurations at which interaction x is selected. ExeSet(λ,x,i)={k∈[0...i]|λβ(k) =x} 4. Set of offerings: the set of indices up to ithat identify the configurations at which poffers interaction x. OffSet(λ,x,p,i)={k∈[0...i]|λβ(k) =p.χ ∧x∈χ} Dp.∅FW D (D, τ, ρ) p.∅CFFk(D,τ,ρ) (4) Dp.χFW D (D, τ, ρ) p.χCFFk(D,τ,ρ) (5) DxFW D∧ (¬PotentialConsp(ϕ, x) ∧x=Oldest(τ, ϕ) ∧ρ=ResetConsp(ρ, x) ∨ (PotentialConsp(ϕ, x) ∧ρ(x) < k∧ρ=IncreaseConsp(ρ, x)) ∧ τ=MoveRear(τ, x) ∧ (D,τ,ρ) xCFFk(D,τ,ρ) where D=(C,ϕ,ϑ,γ,δ,). (6) Figure 7. An implementation of CFFk. •Function Oldest(τ, ϕ): the implementation of Oldest(λ,x,i) when Ciis the current configuration. It returns the first enabled element in queue τ. •Function IncreaseConsp(ρ, x): increases the potential conspiracy counter of interaction x when it is selected and there is a non-stable, linked interaction. •Function ResetConsp(ρ, x): resets the potential conspiracy counter associated with x. •Predicate PotentialConsp(ϕ, x): a trivial implementation of PotentialConsp(λ,x,i)at the current configuration. Once we have defined these supporting structures, functions and predicates, we can implement CFFkby means of the rules shown in Figure 7. Note that these rules work on configurations of the form E=(D,τ,ρ),whereD=(C,ϕ,ϑ,γ,δ,)is a configuration on which the FW can work. Next, we describe them intuitively. •Rules 4and 5are trivial, since every time the framework reacts to an event of the form p.χ,there is nothing to do except to record the structures that the framework has updated. •Rule 6is also straightforward since it allows us to decide if an enabled interaction fulfills our selection criterion. Note the close correspondence between this rule and the definition in Section 4: an interaction may be selected as long as (i) it is not in a potential conspiracy situation and it is the oldest, or (ii) it is in a potential conspiracy situation but its conspiracy counter has not exceeded k(the conspiracy threshold). In the former case, the conspiracy counter associated with the interaction selected is reset, but increased in the latter. In both cases, the interaction selected is moved to the rear of queue τ. 6. PERFORMANCE In order to evaluate our framework and our notion, we measured their performance and effectiveness using the dining philosophers system in Figure 1. We implemented it using the J#programming language, which is an efficient Java dialect for the .NET platform [26], and we ran our tests on a 2.0 GHz AMD Athlon XP machine equipped with 512 MB of DDR 266 MHz memory. We assumed that the time each philosopher spends at thinking or eating is negligible with respect to the time needed to detect enablements, get mutual exclusion or select interactions, for instance. In this setting, each philosopher should be able to have lunch as much as the others during a long-enough fair execution. Each experiment consisted of a system composed of Nphilosophers and Nforks (N = 10,20,...,100). We terminated the experiments after executing 10 000 interactions, i.e. 5000 Get and 5000 Rel interactions were executed in each experiment. They were run 100 times, and we computed the average value of the following metrics. 1. Execution time: the average time to execute 10 000 interactions. 2. Selection time: the average time an interaction needs to be selected since it was offered for the first time by one of its participants. 3. Rejection ratio: the percentage of rejections with regard to the number of interactions executed, i.e. the number of times an enabled interaction becomes disabled because another interaction linked to it is selected for execution. We compared our proposal with the random selection criterion the framework itself uses to select an enabled interaction, the counter-based proposal by Francez and Forman [1], and the incremental one by Corchuelo et al. [24]. The results using Best’s [20,21] or Olderog and Apt’s algorithms [27] were so similar to the results using Francez and Forman’s algorithm that we decided not to show them explicitly. The proposals by Joung [28,29] are so costly in practice that the times we obtained exceeded the rest by orders of magnitude. Figure 8shows that the random proposal is the fastest one, whereas the slowest one is CFFkwhen k=1. Note that the incremental proposal performs better than Francez and Forman’s since it needs not examine the whole set of interactions before reaching a decision, but not as well as the random proposal since the data structures it needs to maintain are more complex. The execution time of CFFk depends on the value we assign to k.Ifkis small (k=1), it performs slightly worse than Francez and Forman’s proposal because it amounts to a round-robin strategy in which interactions are executed in rounds, but the algorithm is more complex. However, if kis high (k=10 000), its performance is similar to the random proposal, although it cannot keep alleviating conspiracies as well as before. This is the behaviour we expected since kconstrains the number of times that linked interactions have to wait for each other; thus, the smaller the value of k, the more they have to wait for each other. If we have 100 philosophers, the average number of interactions per second ranges from 109 int/s in theworstcase(CFFkwith k=1) to 335 int/s in the best case (the random proposal). Figure 9shows the time the random proposal spends at selecting interactions, which is obviously faster than that of Francez and Forman. The selection time of our algorithm depends on k.Thatis,in the worst case (k=1) it is better than Francez and Forman’s proposal, but its execution time is worse because the cost of updating our data structures is higher. Finally, if k=10 000 our proposal behaves like the random proposal because almost no interaction reaches the conspiracy threshold and those that are linked almost never have to wait for each other. 0 10 20 30 40 50 60 70 80 90 100 10 20 30 40 50 60 70 80 90 100 Philosophers Seconds Random Francez & Forman Incremental CFF(k=1) CFF(k=10 000) Figure 8. Execution times. 0 100 200 300 400 500 600 700 800 10 20 30 40 50 60 70 80 90 100 Philosophers Milliseconds Random Francez & Forman Incremental CFF(k=1) CFF(k=10 000) Figure 9. Selection times. 0 1 2 3 4 5 6 7 10 20 30 40 50 60 70 80 90 100 Philosophers % Random Francez & Forman Incremental CFF(k=1) CFF(k=10 000) Figure 10. Rejection ratios. When we have 100 philosophers, the time needed to select interactions in Francez and Forman’s proposal is slightly greater than 700 ms, i.e. the time that the philosophers need to offer to participate in interactions in which they are interested. Depending on the value of k, the selection time of our algorithm ranges from 186 ms in the best case (k=10 000) to 589 ms in the worst case (k=1). Figure 10 shows how the rejection ratio decreases when the number of philosophers increases. If there are 10 philosophers, the rejection ratio ranges from 0.3% to 6.3%. Note that 0.3% is the minimum rejection ratio because the philosophers need to get mutual exclusion with their neighbours to get their forks. These results corroborate the behaviour of the selection time since a rejection implies that the rejected interaction has to be offered again. We also counted the number of times each philosopher had lunch, i.e. the number of Get interactions that were executed. The data plotted in Figure 11 allow us to detect potential conspiracy situations because philosopher iis almost permanently interested in interaction Geti, which is linked to interactions Geti−1and Geti+1. Therefore, if the variations in the distribution of lunches between every three consecutive philosophers is high, this means that the execution is not equitable. In a scenario such as ours, in which the philosophers eat and think for the same, negligible amount of time, equity is obviously desirable. Figure 11(a) shows the distribution of lunches using the random proposal. There is a large difference between the number of times each philosopher eats. For instance, philosopher P86 had 80 lunches, whereas his/her neighbours had 20 (P85) and 21 (P87), respectively. Note that, from a practical point of view, this algorithm allows P85 to conspire against its neighbours, but we cannot enforce the execution to be conspiracy-free. Figures 11(b) and (c) show the results we obtained when we ran the tests using Francez and Forman’s proposal and the incremental one. These distributions are very similar because the latter proposal is an incremental version of the former which performs better, but does not attempt to produce a better distribution of lunches. The variation is, however, smaller than using the random proposal and it 0 10 20 30 40 50 60 70 80 90 100 0 102030405060708090 Philosopher Lunches (a) 0 10 20 30 40 50 60 70 80 90 100 0 102030405060708090 Philosopher Lunches (b) 0 10 20 30 40 50 60 70 80 90 100 0 102030405060708090 Philosopher Lunches (c) Figure 11. Distributions of lunches: (a) random proposal; (b) Francez and Forman’s proposal and (c) incremental proposal; (d) CFFkwhen k=1 (small); (e) CFFkwhen k=100 (mild); (f) CFFkwhen k=10 000 (large). 0 10 20 30 40 50 60 70 80 90 100 0 102030405060708090 Philosopher Lunches (d) 0 10 20 30 40 50 60 70 80 90 100 0 102030405060708090 Philosopher Lunches (e) 0 10 20 30 40 50 60 70 80 90 100 0 102030405060708090 Philosopher Lunches (f) Figure 11. (Continued). depends on the values produced by the random number generator used. In our implementation, we used the standard implementation provided by J#to produce numbers in the range [0...100]. None of the proposals, except for ours, can tune these variations. Figures 11(d)–(f) show the distribution of lunches using CFFkwith several values of k(k= 1,100,10 000). As the figures show, the variation of lunches amongst neighbouring philosophers is controlled by means of the value we assign to k. From this point of view, the main difference between our proposal and Francez and Forman’s stems from the fact that the latter tends to select every interaction as many times as the others, independently of the number of philosophers, whereas our proposal can control the variation and the speed at which a system performs depending on the value we assign to k. This threshold can thus be viewed as a trade-off between efficiency and conspiracies. 7. CONCLUSIONS Fairness has been researched by many authors in the context of MI-based systems. They have devised several notions that attempt to avoid executions in which an interaction that is enabled sufficiently often is neglected. Strong fairness is quite an adequate notion, but it does not address fair finiteness and conspiracy problems. In this article, we have shown that both problems may be addressed simultaneously by means of a new fairness notion that allows us to control to what extent conspiracies must be controlled and takes finite executions into account. We have defined our notion in the context of a framework we have designed and implemented to support MI-based systems. The experimental results show that our notion can deal with conspiracies while still performing comparably to other proposals that do not attempt to solve this problem. APPENDIX A. IP IN A NUTSHELL Simple IP programs are of the following form: S::[P 1P2...Pn], where P1:: Body1 P2:: Body2 ... Pn:: Bodyn They model systems as collections of cooperating sequential processes whose relationships are based on multiparty interactions. Each process executes a body that is composed of a sequence of instructions. Assignments. As usual, assignments are of the form x:= e,wherexdenotes a local variable and ean expression over the local state of the process that executes this instruction. The null assignment is denoted as skip. Interaction instructions. They are of the form ax:= e,whereais the name of an interaction and x:= eis an optional sequence of assignments referred to as the communication part since it allows a process to retrieve data from other processes. xrefers to variables in the local state of the process executing this instruction, but emay refer to variables in other processes participating in interaction a. Several improvements to this naive communication mechanism have been proposed, cf. [8,9,24]. Multi-choice instructions. They are of the form [n i=1Gi→Si], where each Giis a guard and Siis a list of instructions. Guards are of the form B&ax:= e,whereBis a Boolean expression and the rest is an interaction instruction. They are passable, i.e. their corresponding instructions can be executed, iff the Boolean expression holds and interaction ais enabled. If B& is omitted, it is interpreted as true&; if &ax:= eis omitted, it is interpreted as &,where denotes an anonymous local interaction. Note that both parts of a guard cannot be omitted. Multi-choice loops. They are of the form ∗[n i=1Gi→Si]. Their semantics is similar to a multichoice instruction, except for the fact that the whole instruction is repeated until none of the Boolean expressions that guard the alternatives is true. APPENDIX B. PREVIOUS RESULTS A preliminary version of this work was presented at the Euro-Par 2002 conference [30]. There, we presented a notion called SKF (strong k-fairness), which differs from CFFkin that the set of linked interactions was calculated at runtime, whereas it is now calculated at compile time. That is, two interactions where considered to be linked as long as they had a common participant at runtime, not at compile time. In spite of being so similar, the results are very different. Figure B1 shows that CFFkalleviates conspiracies better than SKF because the variation is smaller. Since philosophers are continuously offering to participate in an interaction, be it a Get interaction or a Rel interaction, CFFkintroduces more delays because the set of interactions linked at compile time is usually greater than the set of interactions linked at runtime, and thus needs more interactions to be stable before selecting one of them, which allows us to control conspiracies better than SKF. 0 10 20 30 40 50 60 70 80 90 100 0 102030405060708090 Philosopher Lunches Figure B1. Distribution of lunches using SKF (k =1). ACKNOWLEDGEMENTS We are thankful to our referees and Professor Mavronicolas for their insightful suggestions and their contributions to improve our results. We would also like to thank the participants to the Euro-Par 2002 Conference for engaging in fruitful discussion on fairness and MI-based systems with us. REFERENCES 1. Francez N, Forman I. Interacting processes: A multiparty approach to coordinated distributed programming. AddisonWesley: Reading, MA, 1996. 2. Francez N. Fairness. Springer: Berlin, 1986. 3. Lamport L. Specifying Systems: The TLA+Language and Tools for Hardware and Software Engineers (Lecture Notes in Computer Science, vol. 1845). Addison-Wesley: Boston, MA, 2002. 4. Alur R, Henzinger TA. Finitary fairness. ACM Transactions on Programming Languages and Systems 1998; 20(6):1171– 1194. 5. Attie PC, Francez N, Grumberg O. Fairness and hyperfairness in multiparty interactions. Distributed Computing 1993; 6(4):245–254. 6. Beauquier J, Datta AK, Gradinariu M, Magniette F. Self-stabilizing local mutual exclusion and daemon refinement. Proceedings of the DISC 2000 International Conference (Lecture Notes in Computer Science, vol. 1914). Springer: Berlin, 2000; 223–237. 7. Jayasimha D, Dershowitz N. Bounded fairness. Technical Report TR-615, Center for Supercomputing Research and Development. University of Illinois, 1986. 8. Corchuelo R, P´erez JA, Ruiz–Cort´es A. Aspect-oriented interaction in multi-organizational Web-based systems. Computer Networks 2003; 41(4):385–406. 9. Corchuelo R, P´erez JA, Toro M. A multiparty coordination aspect language. ACM Sigplan 2000; 35(12):24–32. 10. Joung YJ. A comprehensive study of the complexity of multiparty interaction. Journal of the ACM 1996; 43(1):75–115. 11. Tang P, Muraoka Y. Parallel programming with interacting processes. Proceedings of the 12th International Workshop on Languages and Compilers for Parallel Computing, LCPC’99 (Lecture Notes in Computer Science, vol. 1863). Springer: Berlin, 2000; 201–218. 12. Felber P, Reiter MK. Advanced concurrency control in Java. Concurrency and Computation: Practice and Experience 2002; 14(4):261–285. 13. Fayad M. E–Frame: A process-based, object-oriented framework for e-commerce. Proceedings of the International Conference on Internet Computing IC’2001. CSREA Press: Las Vegas, NV, 2001; 124–128. 14. Keen A, Ge T, Maris J, Olsson R. JR: Flexible distributed programming in an extended Java. Proceedings 21st International Conference on Distributed Computing Systems, ICDCS’01. IEEE Press: Los Alamitos, CA, 2001; 575–584. 15. Lea D. Concurrent Programming Using Java: Design Principles and Pattern. Addison-Wesley: Reading, MA, 1999. 16. Lynch NA, Merritt M, Weihl WE, Fekete A. Atomic Transactions (Lecture Notes in Computer Science, vol. 1845). Morgan Kaufmann: San Mateo, CA, 1994. 17. Kindler E, Walter R. Mutex needs fairness. Information Processing Letters 1997; 62(1):31–39. 18. Schneider FB, Lamport L. Another position paper on ‘fairness’. Software Engineering Notes 1988; 13(3):1–2. 19. Dijkstra EW. Position paper on ‘Fairness’. Software Engineering Notes 1988; 3(2):18–20. 20. Best E. Fairness and conspiracies. Information Processing Letters 1984; 18(3):215–220. 21. Best E. Erratum: Fairness and conspiracies. Information Processing Letters 1984; 19(4):162. 22. Lamport L. Fairness and hyperfairness. Distributed Computing 2000; 13(4):239–245. 23. Apt KR, Francez N, Katz S. Appraising fairness in languages for distributed programming. Distributed Computing 1988; 2(4):226–241. 24. Corchuelo R. Prototyping constraint-based specifications of distributed systems. PhD Thesis, Facultad de Inform´atica y Estad´ıstica, Dpto. de Lenguajes y Sistemas Inform´aticos, University of Sevilla, 1999. 25. Corchuelo R, Ruiz D, Toro M, Ruiz–Cort´es A. Implementing multiparty interactions on a network computer. Proceedings XXVth Euromicro Conference. IEEE Press: Milan, Italy, 1999; 458–465. 26. Sarang PG, Adatia E, Jouhier B. J#. Wrox Press: Birmingham, U.K., 2002. 27. Olderog E, Apt KR. Fairness in parallel programs: The transformational approach. ACM Transactions on Programming Languages and Systems 1988; 10(3):420–255. 28. Joung YJ. Two decentralized algorithms for strong interaction fairness for systems with unbounded speed variability. Theoretical Computer Science 2000; 243(1–2):307–338. 29. Joung YJ. Strong interaction fairness via randomization. IEEE Transactions on Parallel and Distributed Systems 1998; 9(2):137–149. 30. Ruiz D, Corchuelo R, P´erez JA, Toro M. An algorithm for ensuring fairness and liveness in non-deterministic systems based on multiparty interactions. Proceedings of the Euro–Par 2002 International Conference (Lecture Notes in Computer Science, vol. 2400). Springer: Berlin, 2002; 563–572.