Fai ness in sys ems based on mul ipa y in e ac ions
Da id Ruiz∗,†, Ra ael Co chuelo and Miguel To o
ETSI In o m´a ica, A da. de la Reina Me cedes s/n, Se illa E-41012, Spain
SUMMARY
In he con ex o he Mul ipa y In e ac ion Model, ai ness is used o insu e ha an in e ac ion ha is
enabled su icien ly o en in a concu en p og am will e en ually be selec ed o execu ion. Un o una ely,
his no ion does no ake conspi acies in o accoun , i.e. si ua ions in which an in e ac ion ne e becomes
enabled because o an un o una e in e lea ing o independen ac ions; u he mo e, e en ual execu ion is
usually oo weak o p ac ical pu poses since his concep can only be used in he con ex o in ini e
execu ions. In his a icle, we p esen a new ai ness no ion, k-conspi acy- ee ai ness, ha imp o es on
o he s because i akes ini e execu ions in o accoun , alle ia es conspi acies ha a e no inhe en o a
p og am, and k may be se a p io i o con ol i s goodness o add ess he abo e-men ioned p oblems.
KEY WORDS: concu en p og ams; mul ipa y in e ac ions; ai ness; ai ini eness; conspi acies
1. INTRODUCTION
In his a icle, we ocus on ai ness in concu en sys ems ha use he Mul ipa y In e ac ion (MI)
model. A mul ipa y in e ac ion is an abs ac ion ha allows se e al p ocesses o synch onize and
exchange in o ma ion coo dina ely. Fai ness becomes essen ial in MI-based sys ems since an MI-
based p ocess may o e o pa icipa e in se e al in e ac ions, al hough i can execu e only one a a
ime [1]. In ui i ely, an execu ion o a p og am is ai i e e y in e ac ion ha is eady o execu ion
su icien ly o en is execu ed su icien ly o en, which a oids execu ions in which such in e ac ions a e
neglec ed.
No ice ha ‘su icien ly o en’ is a ague e m, which implies ha he e is no a single p e ailing
de ini ion. Howe e , many esea che s ag ee in ha so-called s ong ai ness dese es a en ion
∗Co espondence o: Da id Ruiz, ETSI In o m´a ica, A da. de la Reina Me cedes s/n, Se illa E-41012, Spain.
†E-mail: [email p o ec ed].us.es
Con ac /g an sponso : Spanish Minis y o Science and Technology; con ac /g an numbe s: TIC-2000-1106-C02-01;
FIT-150100-2001-78; TAMANSI PCB-02-001
because i may induce desi able p ope ies such as e mina ion o e en ual esponse o a eques o
se ice [1–3]. Un o una ely, his no ion is no es ic i e enough since i does no ake ini e execu ions
in o accoun , and an in e ac ion migh ne e ge eady o execu ion because o an un o una e
in e lea ing o independen ac ions ha migh p e en some o he p ocesses ha need i o coo dina e
om engaging i a he igh ime. This has mo i a ed se e al au ho s o wo k on s onge ai ness
no ions, bu none o hem sol es bo h p oblems simul aneously [4–7].
The main con ibu ion we p esen in his a icle is a new ai ness no ion called k-conspi acy- ee
ai ness ha add esses he abo e-men ioned p oblems by ine- uning he alue we assign o k.Wealso
p esen a amewo k we ha e de ised o implemen ai MI-based sys ems and epo on he esul s
o an expe imen al analysis we conduc ed o compa e ou p oposal wi h o he s. F om hese esul s, we
conclude ha ou p oposal allows one o con ol conspi acies e icien ly and i is easie o apply since
ou implemen a ion is gene ic, i.e. i is no a ans o ma ional app oach and hus needs no ans o m
he sou ce code o he sys ems o which i is applied.
The es o he a icle is o ganized as ollows. In Sec ion 2, we epo on some ela ed wo k
abou mul ipa y in e ac ions, ai ness no ions, and summa ize how we imp o e o he au ho s’ wo k.
The ounda ions o ou amewo k a e p esen ed in Sec ion 3and in Sec ion 4, we in oduce ou
ai ness no ion and de ine i igo ously. We epo on how o implemen ou ai ness no ion and on
ou expe imen al esul s in Sec ions 5and 6, espec i ely. Finally, some conclusions a e d awn om
p e ious pa s and summa ized in Sec ion 7.
2. RELATED WORK
In his sec ion, we i s p esen he MI model. La e , we epo on cu en ai ness p oposals and a gue
on hei de iciencies. Finally we summa ize ou con ibu ions.
2.1. Mul ipa y in e ac ions
The MI model p o ides in e ac ions as he sole means o p ocess synch oniza ion and
communica ion [1,8–10], and i has been p o en o achie e op imal concu ency and/o pa allelism
in some common si ua ions [11].
Con a ily o he usual message-passing model, which emphasizes wo p ocesses exchanging
messages and, hus, communica ion, mul ipa y in e ac ions ocus on ag eemen amongs mul iple
pa ies ha need o coope a e in o de o achie e a common goal, e.g. ans e ing money om a
bank o ano he by means o a poin o sales e minal ( h ee p ocesses) [12], paying axes on-line
( h ee p ocesses in Spain: a axpaye , he Excheque , and Spain’s Ce i ica ion Au ho i y), il e ing in
e-comme ce [13] (a cus ome , a il e sys em, and se e al se ice p o ide s), o eaching a i ual
ag eemen in an auc ion sale (mul iple p ocesses). Re e ence [10] p o ides a comple e axonomy
o languages ha suppo his in e ac ion model, and ecen con ibu ions p esen ed in [12,14,15]
ha e ex ended Ja a o suppo mul ipa y in e ac ions o some ex en . In [8], he model was u he
esea ched and combined wi h aspec o ien a ion.
Roughly speaking, a mul ipa y in e ac ion can be iewed as an abs ac coo dina ion mechanism
ha allows a se o p ocesses, each o which mus be eady o pa icipa e in he in e ac ion so ha i can
occu , o execu e da a exchange ac ions join ly and coo dina ely. (When his happens, he in e ac ion is
said o be eady o execu ion o enabled.) An a emp o pa icipa e in an in e ac ion delays a p ocess
un il all o he pa icipan s a e a ailable, and a e an in e ac ion is execu ed, he pa icipan s exchange
some da a and con inue hei local compu a ions sepa a ely. No ice ha an in e ac ion being enabled
does no en ail i s execu ion since i may be linked o o he in e ac ions in which a common p ocess is
willing o pa icipa e. Since a p ocess can execu e only one in e ac ion a a ime, an elec ion unde he
linked in e ac ions needs o be held. In ui i ely, he selec ion p ocedu e mus be ai o a oid execu ions
in which an in e ac ion is ne e execu ed o ne e has a chance o become enabled.
A classical p oblem o illus a e he adequacy o mul ipa y in e ac ions is he Dining Philosophe s
P oblem. The ob ious message-passing solu ion consis s o sending eques s o he o ks o ge hem in
sequence, bu a deadlock may occu i each philosophe g abs he o k on his/he igh , and hen wai s
o he o k on his/he le o be eleased. In [16], i was p o en ha assuming no means o commu-
nica ion amongs philosophe s o he han h ough in o ma ion a ached o hei o ks, any solu ion in
which all philosophe s a e p og ammed iden ically mus ha e a possibili y o deadlock. Thus, co ec
solu ions mus ely on some dis inc ion o be made amongs he philosophe s. These solu ions a e
usually no scalable o eusable since he dis inc ion a philosophe has o implemen depends hea ily
on he opology o he p oblem. I we used mul ipa y in e ac ions, he solu ion would be simple since
each philosophe would pick up his/he wo o ks a a ime so ha no deadlock could a ise.
Figu e 1shows an MI-based dining philosophe s sys em based on he IP language [1]. (A b ie
in oduc ion o IP is p esen ed in Appendix A.) The philosophe s a e ep esen ed by p ocesses Pi,
and he o ks by p ocesses Fi(i∈[1...N]). Each Pi i s ies o ge i s o ks by pa icipa ing in
he h ee-pa y in e ac ion Ge i oge he wi h Fiand Fi−1. (We assume ha subindex a i hme ic is
module N.) Thus, acqui ing a esou ce is speci ied as synch onizing wi h he co esponding p ocesses
in a mul ipa y in e ac ion. A e Pihas go i s o ks, i ea s, eleases he o ks, spends some ime
hinking and he whole p ocess is epea ed once again. No ice ha in e ac ions Ge i−1,Ge iand Ge i+1
a e linked o e e y i∈[1...N], bu only one o hem can be execu ed a he same ime. The only
way o gua an ee ha each in e ac ion ha is enabled su icien ly o en shall e en ually be selec ed
o execu ion consis s o assuming ha he unde lying selec ion mechanism is ai . (I is known ha
ai ness is manda o y in sys ems in which p ocesses need mu ual exclusion o a esou ce [17].)
2.2. Fai ness
In [18], he au ho s in oduced se e al p ope ies ha dese e special a en ion in he con ex o
concu en sys ems. They classi ied hem in o wo g oups, namely: sa e y p ope ies, which asse
ha ‘some hing bad’ does no happen, and li eness p ope ies, which asse ha ‘some hing good’
mus happen e en ually. In concu en p og amming, usual bad hings a e deadlocks o he iola ion o
c i ical egions. In con as , usual good hings a e he absence o s a a ion, he esponse o a eques
o se ice o e mina ion.
Fai ness is some imes he only way o gua an ee hese li eness p ope ies, bu , un o una ely, he e
is no a single p e ailing de ini ion. Many au ho s [1–3], howe e , ag ee in ha s ong ai ness
(SF) dese es a en ion since i may induce desi able li eness p ope ies. Technically, an execu ion
is s ongly ai i e e y in e ac ion ha is enabled in ini ely o en is execu ed in ini ely o en.
This p e en s an in e ac ion ha is enabled om ime o ime, no necessa ily pe manen ly, om being
neglec ed. Fo ins ance, in he sys em in Figu e 1, he only way o gua an ee ha each philosophe is
able o ea as much as he es is by assuming ha he unde lying schedule is ai , i.e. his is he only
way o insu e ha e e y eques o se ice a philosophe makes o a o k is sa is ied e en ually.
DINNER :: [||N
i=1Pi||Fi], whe e
Pi:: *[ Ge i → ea ;Rel
i; hink ]
Fi:: *[ Ge i → Reli Ge i+1 → Reli+1 ].
(a)
Rel
2
Rel
3
Rel
4
Rel
5
Ge
2
Ge
3
Ge
4
Ge
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
Ge
1
(b)
Figu e 1. A solu ion o he dining philosophe s p oblem in IP: (a) he IP code o implemen he sys em;
(b) ske ch o a sys em wi h i e philosophe s.
In spi e o i s adequacy in he con ex o MI-based sys ems, s ong ai ness su e s om wo
p ac ical p oblems ha may lead o undesi able execu ions.
Fai ini eness. The i s p oblem lies in he ac ha s ong ai ness is a oid p ope y [19]. Tha is, he
s ong ai ness ul illmen o an execu ion canno be checked by pe o ming ini e expe imen s.
Thus, he e is no way o show ha a schedule p oduces s ongly ai execu ions by analysing
he esul s o an expe imen . Fu he mo e, e e y ini e execu ion is s ongly ai by de aul [2].
Figu e 2(a) shows an e en ace o he sys em in Figu e 1(N=5). No ice ha in e ac ion Ge 2
is enabled n imes, bu i is ne e selec ed du ing his execu ion. Gi en ha s ong ai ness is
a oid p ope y, he e is no ini e expe imen om which we can conclude ha he schedule
ha p oduced his execu ion is no s ongly ai . This implies ha s ong ai ness may lead o a
si ua ion in which an in e ac ion is ne e selec ed in a long-enough ini e execu ion [4].
P1.{Ge 1},P
2.{Ge 2},F
2.{Ge 2,Ge
3},
(F
5.{Ge 5,Ge
1},F
1.{Ge 1,Ge 2},Ge 1,
P1.{Rel1},F
1.{Rel1},F
5.{Rel1},Rel1,P
1.{Ge 1})n
(a)
P1.{Ge 1},P
2.{Ge 2},P
3.{Ge 3},
(F
5.{Ge 5,Ge
1},F
3.{Ge 3,Ge
4},F
1.{Ge 1,Ge
2},Ge 1,
F2.{Ge 2,Ge
3},Ge 3,P
1.{Rel1},F
1.{Rel1},F
5.{Rel1},Rel1,
P3.{Rel3},F
2.{Rel3},F
3.{Rel3},Rel3,P
1.{Ge 1},P
3.{Ge 3})∞
(b)
Figu e 2. P oblems wi h s ong ai ness: (a) ai ini eness; (b) conspi acies. (p.χ means ha p ocess po e s o
pa icipa e in any in e ac ion in se χ,andx ha in e ac ion xis execu ed.)
S::[P|| Q], whe e
P::*[A → B C → skip ]
Q::*[A → [B → skip C → skip] ].
Figu e 3. A p og am wi h inhe en conspi acies.
Conspi acies. Fu he mo e, a schedule may lead o execu ions in which all o he p ocesses ha may
pa icipa e in an in e ac ion a e eady o pa icipa e in i om ime o ime, bu i ne e becomes
enabled because o an un o una e in e lea ing ha p e en s hem om o e ing o pa icipa e a
he same ime, i.e. some pa icipa ing p ocesses decide o execu e ano he in e ac ion be o e he
o me becomes enabled. These si ua ions a e commonly e e ed o as conspi acies [20,21].
Figu e 2(b) shows a good example in which in e ac ion Ge 2is eadied by all o i s pa icipan s
in ini ely many imes, bu ne e ge s enabled. Al hough he execu ion is s ongly ai , his
conspi acy is undesi able and should be a oided. The e a e p og ams, howe e , in which
conspi acies a e inhe en . Fo ins ance, he e en aces o he p og am in Figu e 3a e o he
o m (P.{A,C},Q.{A},A,P.{B},Q.{B,C},B)∞. The conspi acy agains Cis una oidable since
i is inhe en o his p og am.
Indi idually, hese p oblems ha e been s udied by se e al au ho s [4–7,22], gi ing ise o
new ai ness no ions. Amongs hem, we ocus on ini a y (s ong) ai ness [4]and(s ong)
hype ai ness [5] because hese app oaches ocus on concu en p og amming, whe eas he o he s
ocus on sel -s abilizing algo i hms [6], classical empo al logic [7] and empo al logic o ac ions
[3,22].

Table I. Compa ison wi h ela ed wo k.
No ion B ie desc ip ion Fai ini eness Conspi acies
SF E e y in e ac ion ha becomes enabled in ini ely No No
o en is selec ed in ini ely o en.
HF E e y in e ac ion ha is o e ed in ini ely o en by No Yes
all o i s pa icipan s becomes enabled in ini ely
o en.
FF E e y in e ac ion ha becomes enabled in ini ely Yes No
o en is selec ed a leas once e e y k imes i is
enabled.
CFFkNo in e ac ion is selec ed mo e han k imes Yes Yes
wi hou analysing he s a e o he in e ac ions ha
a e linked o i .
Fini a y ai ness (FF). Alu e al. [4] sol ed he ini eness p oblem and p o ided us wi h a new no ion
ha needs o be combined wi h o he s. I i is combined wi h s ong ai ness, hen he e m
‘in ini ely o en’ is eplaced by ‘a leas once e e y k imes’, whe e kis a na u al numbe ha
mus exis , bu is no known ap io i. The e o e, i is said ha an execu ion is ini a ily s ong
ai i he e exis s a na u al numbe ksuch ha no in e ac ion is ejec ed mo e han k imes
consecu i ely.
This no ion has se e al d awbacks, namely (i) kis known a pos e io i, which implies ha i
canno be se ap io i o egula e a sys em; (ii) i s implemen a ion is ans o ma ional; (iii) i does
no a emp o sol e conspi acies o alle ia e hem since he au ho s do no ocus on MI-based
sys ems.
Hype ai ness (HF). A ie e al. [5] s udied conspi acies in he con ex o he IP language and de ined
hype ai ness o sol e i . I is said ha an execu ion is hype ai i e e y in e ac ion is conspi acy-
esis an , i.e. i is o e ed by all o hei pa icipan s in ini ely o en. No ice ha his no ion
insu es ha an in e ac ion ha can e en ually become enabled, becomes enabled, which does no
necessa ily en ail i is selec ed o execu ion; hus, i needs o be combined wi h o he no ions.
I has some d awbacks, namely (i) he se o in e ac ions ha a e conspi acy- esis an needs
o be p e-compu ed, bu he au ho s do no p o ide us wi h an algo i hm o do so; (ii) i s
implemen a ion is ans o ma ional, bu he au ho s do no p o ide us wi h a gene ic algo i hm
o pe o m ans o ma ions; (iii) he au ho s combine i wi h s ong ai ness only, which does no
sol e he ai ini eness p oblem.
2.3. Ou con ibu ions
The main con ibu ion we p esen in his a icle consis s o a new ai ness no ion ha is mo e es ic i e
han s ong ai ness and add esses bo h he ai ini eness p oblem and conspi acies simul aneously, as
we show in Table I. We e e o his no ion as k-conspi acy- ee ai ness o CFFk o sho .
We hink ha p e ious a emp s o sol e hese p oblems ha e no add essed hem simul aneously
since hey ocused on di e en se ings. Fo ins ance, he wo k by Alu e al. on ini a y ai ness ocuses
on concu en sys ems ha a e no MI-based; hus, no conspi acy si ua ions may occu . The wo k by
A ie e al. ocuses on MI-based sys ems and i laid he ounda ions o hype ai ness; un o una ely,
hei ideas we e no de eloped o hei ull ex en bu hey dese e a en ion since hey we e he i s
o iden i y he p oblem and de ise a solu ion. Ve y ecen ly, Lampo [3,22] conside s hype ai ness a
co ne -s one o ac ion-based concu en sys ems and ecognizes he need o u he esea ch on his
opic. Hype ai ness does no ocus on ai ini eness since he au ho s we e no in e es ed in sol ing
a p ac ical p oblem, bu in p o iding a no ion o p ese e a p ope y called equi alence obus ness,
which is manda o y o a no ion o be ully adequa e acco ding o he c i e ia in [2,23]. Conspi acies
cons i u e a majo obs acle o p ese ing his p ope y, so hey should be a oided.
Ou p oposal builds on p e ious heo e ical wo k by hese au ho s and add esses bo h p oblems
om a p ac ical s andpoin since we a e no in e es ed in p o ing heo e ical p ope ies, bu on
ma e ializing hose concep s in o a no ion ha sol es p ac ical p oblems. As we p o e in Sec ion 6, he
implemen a ion o ou no ion pe o ms compa ably o o he esea che s’ implemen a ions o s ong
ai ness; howe e , since ou no ion depends on he alue we assign o kbe o ehand, his pa ame e
may help us con ol how well i add esses bo h p oblems. The pa ame e can hus be seen as a
ade-o be ween e ec i eness and e iciency: he smalle he alue o k, he be e he con ol o
he conspi acies, bu he less e icien he implemen a ion; he g ea e he alue o k, he poo e he
con ol o he conspi acies, bu he mo e e icien he implemen a ion.
Fu he mo e, he implemen a ion o ou p oposal is no ans o ma ional, which may be seen as a
p ac ical ad an age since i can be applied o any MI-based sys em wi hou equi ing us o change i s
sou ce code o ans o m i in o an equi alen ai sys em. Roughly speaking, we can p oduce a gene ic
schedule ha can be used in any MI-based sys em, whe eas o he p oposals need o be adap ed o
pa icula sys ems and ans o m hei sou ce code o p oduce ad hoc schedule s. F om a heo e ical
s andpoin , bo h app oaches a e sound, bu om a p ac ical s andpoin ha ing a gene ic schedule
seems o be a be e idea; o he wise, we would need o ha e access o he sou ce code o ans o m i ,
which is impossible i we a e dealing wi h p ocesses ob ained om a componen which is a ailable in
bina y o m only, e.g. a C++ lib a y o a CORBA objec .
3. A THEORETICAL FRAMEWORK TO DESCRIBE MI-BASED SYSTEMS
In his sec ion, we p esen he ounda ions we need o de ine ou no ion igo ously, which we hink
is e y impo an so ha o he au ho s can epea ou wo k. La e , we show ha he amewo k we
ha e designed allows us o desc ibe o he au ho s’ no ions. Thus, he implemen a ion we p esen in
Sec ion 5can be seen as a gene ic ha ness o implemen MI-based sys ems and ai ness no ions.
3.1. De ini ions
The co e o he amewo k is a se o de ini ions wi h which we de ine igo ously he concep s p esen ed
p e iously. We use he dining philosophe s sys em in Figu e 1 o illus a e some o hem.
De ini ion 1. (MI sys ems) A sys em is a 2- uple o he o m (P,I)in which P=∅is a ini e
se o p ocesses and I=∅is a ini e se o in e ac ions. We deno e he se o p ocesses ha may
e en ually o e o pa icipa e in in e ac ion xas P(x), and he se o in e ac ions ha p ocess pcan
o e as I(p).
In ou example, we ha e an MI-based sys em composed o N=5 philosophe p ocesses called
Piand N o k p ocesses called Fi(i∈[1...N]). These p ocesses a e synch onized by means o N
in e ac ions called Ge i o ake he o ks and i e in e ac ions called Reli o elease hem. Fo ins ance,
he se o p ocesses pa icipa ing in in e ac ion Ge iis P(Ge i)={Fi−1,Pi,Fi}, and he se o
in e ac ions in which Fimay pa icipa e is I(Fi)={Ge i,Reli,Ge i+1,Reli+1}.
De ini ion 2. (E en s) An e en is a happening ha induces a sys em o ansi om a con igu a ion o
ano he . (A con igu a ion is an objec ha may be iewed as a snapsho o a sys em a un ime.) In ou
model, we ake he ollowing kinds o e en s in o accoun .
•O e ing e en . p.χ indica es ha p ocess pis o e ing o pa icipa e in an in e ac ion in se χ.
No ice ha i χ=∅, p ocess pa i es a a ixed poin ha we may in e p e as i s e mina ion
because i can nei he pe o m local compu a ion no execu e any in e ac ion.
•Synch oniza ion. xindica es ha in e ac ion xhas been selec ed o execu ion.
Fo ins ance, when philosophe Pio e s o pa icipa e in in e ac ion Ge i, an e en o he o m
Pi.{Ge i}occu s; simila ly, when Pi akes i s o ks, an e en o he o m Ge ioccu s and synch onizes
he execu ion o Pi,Fiand Fi−1(i∈[1...N]).
De ini ion 3. (Execu ions) An execu ion o sys em is a 3- uple (C0,α,β) in which C0is he ini ial
con igu a ion, α=[C1,C
2,C
3,...]is a maximal ( ini e o in ini e) sequence o con igu a ions, and
β=[e1,e
2,e
3,...]is a maximal ( ini e o in ini e) sequence o e en s esponsible o he ansi ion
be ween e e y wo consecu i e con igu a ions. (Ob iously, |α|=|β|.) Finally, le λ=(C0,α,β) be
an execu ion o sys em . We call αi s con igu a ion ace and deno e i as λα,andβi s e en ace
and deno e i as λβ.
Conside , o ins ance, he execu ion below:
λ=(C0,α,β)
α=[C1,C
2,C
3,C
4,...]
β=[P1.{Ge 1},F5.{Ge 5,Ge 1},F1.{Ge 1,Ge 2},Ge 1,...]
Philosophe P1s a s o e ing in e ac ion Ge 1, o kF5 hen o e s in e ac ions {Ge 5,Ge 1},and
o k F1in e ac ions {Ge 1,Ge 2}. In e ac ion Ge 1becomes enabled a con igu a ion C3and, in his
case, i is execu ed and he p og am con inues.
De ini ion 4. (Seman ics) We deno e he ule ha cap u es he unde lying seman ics ha con ol he
ansi ion be ween con igu a ions as L. Fo ins ance, CeLCindica es ha he sys em
may ansi om con igu a ion C o con igu a ion Con occu ence o e en e.Thus,gi enan
execu ion λ=(C0,[C1,C
2,C
3,...],[e1,e
2,e
3,...]), we usually w i e i as C0e1LC1e2L
C2e3L···.
Ou example is implemen ed in IP, hus Lamoun s o IP. Please, consul [1] o a comple e
desc ip ion o he seman ics o he IP language o Appendix A o a b ie in oduc ion.
De ini ion 5. (P ocesses) P ocess pis wai ing o an in e ac ion in se ϒ=∅a he i h con igu a ion
in execu ion λi i has a i ed a a poin in which i may execu e any x∈ϒ, i.e. i has o e ed o
pa icipa e in a subse o in e ac ions χ⊇ϒand no in e ac ion in ϒhas been selec ed since ha
momen . P ocess pis inished a he i h con igu a ion in execu ion λi i has o e ed o pa icipa e in
an emp y se o in e ac ions, ha is, i can nei he pe o m local compu a ions no in e ac wi h o he
p ocesses.
Wai ing(λ,p,ϒ,i) ⇐⇒ ∃ χ⊇ϒ,k ∈[1...i)·(λβ(k) =p.χ ∧j∈(k...i]·λβ(j) =x∧x∈ϒ)
Finished(λ, p, i) ⇐⇒ ∃ k∈[1...i]·λβ(k) =p.∅
In ou example, philosophe Pjis eadying he se o in e ac ions {Ge j}(j∈[1...N]) a con igu a ion
Ci(i∈[1...|λ|])i ane en Pj.{Ge j}happened be o e Ciand in e ac ion Ge jwas no selec ed since
ha momen .
De ini ion 6. (In e ac ions) In e ac ion xis enabled a he i h con igu a ion in execu ion λi all o he
p ocesses in P(x) a e o e ing xa ha con igu a ion, ha is, all o i s pa icipan s a e wai ing o i o
be selec ed. In e ac ion xis s able a he i h con igu a ion in execu ion λi i s pa icipan s a e inished
o wai ing o an in e ac ion, whiche e i is.
Enabled(λ,x,i) ⇐⇒ ∀ p∈P(x) ·Wai ing(λ, p, {x},i)
S able(λ, x, i) ⇐⇒ ∀ p∈P(x) ·(Finished(λ,p,i)∨∃ϒ⊆I·Wai ing(λ,p,ϒ,i))
In e ac ion Ge jis enabled a he i h con igu a ion i all o i s pa icipan s (Pj,Fjand Fj−1)a e
o e ing i . Fu he mo e, Reljis s able because i s pa icipan s a e wai ing o Ge j. No ice ha
enablemen implies s ableness, bu he con e se is no ue in gene al.
De ini ion 7. (Miscellaneous) Le λbe an execu ion and xan in e ac ion. We de ine he ollowing se s
a he i h con igu a ion:
1. In e ac ions linked o x: he se o in e ac ions ha sha e a pa icipan wi h x.
Linked(λ,x,i)={y∈I|P(x) ∩P(y) =∅}
2. Se o enablemen s: he se o indices up o i ha iden i y he con igu a ions a which in e ac ion x
is enabled.
EnaSe (λ, x, i) ={k∈[0...i]|Enabled(λ,x,k)}
3. Se o execu ions: he se o indices up o i ha iden i y he con igu a ions a which in e ac ion x
is selec ed.
ExeSe (λ,x,i)={k∈[0...i]|λβ(k) =x}
4. Se o o e ings: he se o indices up o i ha iden i y he con igu a ions a which po e s
in e ac ion x.
O Se (λ,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∧
(¬Po en ialConsp(ϕ, x) ∧x=Oldes (τ, ϕ) ∧ρ=Rese Consp(ρ, x) ∨
(Po en ialConsp(ϕ, x) ∧ρ(x) < k∧ρ=Inc easeConsp(ρ, x)) ∧
τ=Mo eRea (τ, x) ∧
(D,τ,ρ) xCFFk(D,τ,ρ)
whe e D=(C,ϕ,ϑ,γ,δ,).
(6)
Figu e 7. An implemen a ion o CFFk.
•Func ion Oldes (τ, ϕ): he implemen a ion o Oldes (λ,x,i) when Ciis he cu en
con igu a ion. I e u ns he i s enabled elemen in queue τ.
•Func ion Inc easeConsp(ρ, x): inc eases he po en ial conspi acy coun e o in e ac ion x
when i is selec ed and he e is a non-s able, linked in e ac ion.
•Func ion Rese Consp(ρ, x): ese s he po en ial conspi acy coun e associa ed wi h x.
•P edica e Po en ialConsp(ϕ, x): a i ial implemen a ion o Po en ialConsp(λ,x,i)a he
cu en con igu a ion.
Once we ha e de ined hese suppo ing s uc u es, unc ions and p edica es, we can implemen
CFFkby means o he ules shown in Figu e 7. No e ha hese ules wo k on con igu a ions o he
o m E=(D,τ,ρ),whe eD=(C,ϕ,ϑ,γ,δ,)is a con igu a ion on which he FW can wo k.
Nex , we desc ibe hem in ui i ely.
•Rules 4and 5a e i ial, since e e y ime he amewo k eac s o an e en o he o m p.χ, he e
is no hing o do excep o eco d he s uc u es ha he amewo k has upda ed.
•Rule 6is also s aigh o wa d since i allows us o decide i an enabled in e ac ion ul ills
ou selec ion c i e ion. No e he close co espondence be ween his ule and he de ini ion in
Sec ion 4: an in e ac ion may be selec ed as long as (i) i is no in a po en ial conspi acy si ua ion
and i is he oldes , o (ii) i is in a po en ial conspi acy si ua ion bu i s conspi acy coun e has
no exceeded k( he conspi acy h eshold). In he o me case, he conspi acy coun e associa ed
wi h he in e ac ion selec ed is ese , bu inc eased in he la e . In bo h cases, he in e ac ion
selec ed is mo ed o he ea o queue τ.

6. PERFORMANCE
In o de o e alua e ou amewo k and ou no ion, we measu ed hei pe o mance and e ec i eness
using he dining philosophe s sys em in Figu e 1. We implemen ed i using he J#p og amming
language, which is an e icien Ja a dialec o he .NET pla o m [26], and we an ou es s on a
2.0 GHz AMD A hlon XP machine equipped wi h 512 MB o DDR 266 MHz memo y. We assumed
ha he ime each philosophe spends a hinking o ea ing is negligible wi h espec o he ime needed
o de ec enablemen s, ge mu ual exclusion o selec in e ac ions, o ins ance. In his se ing, each
philosophe should be able o ha e lunch as much as he o he s du ing a long-enough ai execu ion.
Each expe imen consis ed o a sys em composed o Nphilosophe s and N o ks (N =
10,20,...,100). We e mina ed he expe imen s a e execu ing 10 000 in e ac ions, i.e. 5000 Ge and
5000 Rel in e ac ions we e execu ed in each expe imen . They we e un 100 imes, and we compu ed
he a e age alue o he ollowing me ics.
1. Execu ion ime: he a e age ime o execu e 10 000 in e ac ions.
2. Selec ion ime: he a e age ime an in e ac ion needs o be selec ed since i was o e ed o he
i s ime by one o i s pa icipan s.
3. Rejec ion a io: he pe cen age o ejec ions wi h ega d o he numbe o in e ac ions execu ed,
i.e. he numbe o imes an enabled in e ac ion becomes disabled because ano he in e ac ion
linked o i is selec ed o execu ion.
We compa ed ou p oposal wi h he andom selec ion c i e ion he amewo k i sel uses o selec
an enabled in e ac ion, he coun e -based p oposal by F ancez and Fo man [1], and he inc emen al
one by Co chuelo e al. [24]. The esul s using Bes ’s [20,21] o Olde og and Ap ’s algo i hms [27]
we e so simila o he esul s using F ancez and Fo man’s algo i hm ha we decided no o show hem
explici ly. The p oposals by Joung [28,29] a e so cos ly in p ac ice ha he imes we ob ained exceeded
he es by o de s o magni ude.
Figu e 8shows ha he andom p oposal is he as es one, whe eas he slowes one is CFFkwhen
k=1. No e ha he inc emen al p oposal pe o ms be e han F ancez and Fo man’s since i needs
no examine he whole se o in e ac ions be o e eaching a decision, bu no as well as he andom
p oposal since he da a s uc u es i needs o main ain a e mo e complex. The execu ion ime o CFFk
depends on he alue we assign o k.I kis small (k=1), i pe o ms sligh ly wo se han F ancez
and Fo man’s p oposal because i amoun s o a ound- obin s a egy in which in e ac ions a e execu ed
in ounds, bu he algo i hm is mo e complex. Howe e , i kis high (k=10 000), i s pe o mance is
simila o he andom p oposal, al hough i canno keep alle ia ing conspi acies as well as be o e.
This is he beha iou we expec ed since kcons ains he numbe o imes ha linked in e ac ions
ha e o wai o each o he ; hus, he smalle he alue o k, he mo e hey ha e o wai o each o he .
I we ha e 100 philosophe s, he a e age numbe o in e ac ions pe second anges om 109 in /s in
hewo s case(CFFkwi h k=1) o 335 in /s in he bes case ( he andom p oposal).
Figu e 9shows he ime he andom p oposal spends a selec ing in e ac ions, which is ob iously
as e han ha o F ancez and Fo man. The selec ion ime o ou algo i hm depends on k.Tha is,in
he wo s case (k=1) i is be e han F ancez and Fo man’s p oposal, bu i s execu ion ime is wo se
because he cos o upda ing ou da a s uc u es is highe . Finally, i k=10 000 ou p oposal beha es
like he andom p oposal because almos no in e ac ion eaches he conspi acy h eshold and hose ha
a e linked almos ne e ha e o wai o each o he .
0
10
20
30
40
50
60
70
80
90
100
10 20 30 40 50 60 70 80 90 100
Philosophe s
Seconds
Random
F ancez & Fo man
Inc emen al
CFF(k=1)
CFF(k=10 000)
Figu e 8. Execu ion imes.
0
100
200
300
400
500
600
700
800
10 20 30 40 50 60 70 80 90 100
Philosophe s
Milliseconds
Random
F ancez & Fo man
Inc emen al
CFF(k=1)
CFF(k=10 000)
Figu e 9. Selec ion imes.
0
1
2
3
4
5
6
7
10 20 30 40 50 60 70 80 90 100
Philosophe s
%
Random
F ancez & Fo man
Inc emen al
CFF(k=1)
CFF(k=10 000)
Figu e 10. Rejec ion a ios.
When we ha e 100 philosophe s, he ime needed o selec in e ac ions in F ancez and Fo man’s
p oposal is sligh ly g ea e han 700 ms, i.e. he ime ha he philosophe s need o o e o pa icipa e
in in e ac ions in which hey a e in e es ed. Depending on he alue o k, he selec ion ime o ou
algo i hm anges om 186 ms in he bes case (k=10 000) o 589 ms in he wo s case (k=1).
Figu e 10 shows how he ejec ion a io dec eases when he numbe o philosophe s inc eases.
I he e a e 10 philosophe s, he ejec ion a io anges om 0.3% o 6.3%. No e ha 0.3% is he
minimum ejec ion a io because he philosophe s need o ge mu ual exclusion wi h hei neighbou s
o ge hei o ks. These esul s co obo a e he beha iou o he selec ion ime since a ejec ion implies
ha he ejec ed in e ac ion has o be o e ed again.
We also coun ed he numbe o imes each philosophe had lunch, i.e. he numbe o Ge in e ac ions
ha we e execu ed. The da a plo ed in Figu e 11 allow us o de ec po en ial conspi acy si ua ions
because philosophe iis almos pe manen ly in e es ed in in e ac ion Ge i, which is linked o
in e ac ions Ge i−1and Ge i+1. The e o e, i he a ia ions in he dis ibu ion o lunches be ween
e e y h ee consecu i e philosophe s is high, his means ha he execu ion is no equi able. In a scena io
such as ou s, in which he philosophe s ea and hink o he same, negligible amoun o ime, equi y is
ob iously desi able.
Figu e 11(a) shows he dis ibu ion o lunches using he andom p oposal. The e is a la ge di e ence
be ween he numbe o imes each philosophe ea s. Fo ins ance, philosophe P86 had 80 lunches,
whe eas his/he neighbou s had 20 (P85) and 21 (P87), espec i ely. No e ha , om a p ac ical poin o
iew, his algo i hm allows P85 o conspi e agains i s neighbou s, bu we canno en o ce he execu ion
o be conspi acy- ee.
Figu es 11(b) and (c) show he esul s we ob ained when we an he es s using F ancez and Fo man’s
p oposal and he inc emen al one. These dis ibu ions a e e y simila because he la e p oposal is an
inc emen al e sion o he o me which pe o ms be e , bu does no a emp o p oduce a be e
dis ibu ion o lunches. The a ia ion is, howe e , smalle han using he andom p oposal and i
0
10
20
30
40
50
60
70
80
90
100
0 102030405060708090
Philosophe
Lunches
(a)
0
10
20
30
40
50
60
70
80
90
100
0 102030405060708090
Philosophe
Lunches
(b)
0
10
20
30
40
50
60
70
80
90
100
0 102030405060708090
Philosophe
Lunches
(c)
Figu e 11. Dis ibu ions o lunches: (a) andom p oposal; (b) F ancez and Fo man’s p oposal and (c) inc emen al
p oposal; (d) CFFkwhen k=1 (small); (e) CFFkwhen k=100 (mild); ( ) CFFkwhen k=10 000 (la ge).
0
10
20
30
40
50
60
70
80
90
100
0 102030405060708090
Philosophe
Lunches
(d)
0
10
20
30
40
50
60
70
80
90
100
0 102030405060708090
Philosophe
Lunches
(e)
0
10
20
30
40
50
60
70
80
90
100
0 102030405060708090
Philosophe
Lunches
( )
Figu e 11. (Con inued).

depends on he alues p oduced by he andom numbe gene a o used. In ou implemen a ion, we
used he s anda d implemen a ion p o ided by J# o p oduce numbe s in he ange [0...100]. None o
he p oposals, excep o ou s, can une hese a ia ions.
Figu es 11(d)–( ) show he dis ibu ion o lunches using CFFkwi h se e al alues o k(k=
1,100,10 000). As he igu es show, he a ia ion o lunches amongs neighbou ing philosophe s
is con olled by means o he alue we assign o k. F om his poin o iew, he main di e ence
be ween ou p oposal and F ancez and Fo man’s s ems om he ac ha he la e ends o selec
e e y in e ac ion as many imes as he o he s, independen ly o he numbe o philosophe s, whe eas
ou p oposal can con ol he a ia ion and he speed a which a sys em pe o ms depending on he alue
we assign o k. This h eshold can hus be iewed as a ade-o be ween e iciency and conspi acies.
7. CONCLUSIONS
Fai ness has been esea ched by many au ho s in he con ex o MI-based sys ems. They ha e de ised
se e al no ions ha a emp o a oid execu ions in which an in e ac ion ha is enabled su icien ly
o en is neglec ed. S ong ai ness is qui e an adequa e no ion, bu i does no add ess ai ini eness and
conspi acy p oblems.
In his a icle, we ha e shown ha bo h p oblems may be add essed simul aneously by means o
a new ai ness no ion ha allows us o con ol o wha ex en conspi acies mus be con olled and
akes ini e execu ions in o accoun . We ha e de ined ou no ion in he con ex o a amewo k we
ha e designed and implemen ed o suppo MI-based sys ems. The expe imen al esul s show ha
ou no ion can deal wi h conspi acies while s ill pe o ming compa ably o o he p oposals ha do no
a emp o sol e his p oblem.
APPENDIX A. IP IN A NUTSHELL
Simple IP p og ams a e o he ollowing o m:
S::[P
1P2...Pn], whe e
P1:: Body1
P2:: Body2
...
Pn:: Bodyn
They model sys ems as collec ions o coope a ing sequen ial p ocesses whose ela ionships a e based
on mul ipa y in e ac ions. Each p ocess execu es a body ha is composed o a sequence o ins uc ions.
Assignmen s. As usual, assignmen s a e o he o m x:= e,whe exdeno es a local a iable and ean
exp ession o e he local s a e o he p ocess ha execu es his ins uc ion. The null assignmen
is deno ed as skip.
In e ac ion ins uc ions. They a e o he o m ax:= e,whe eais he name o an in e ac ion and
x:= eis an op ional sequence o assignmen s e e ed o as he communica ion pa since
i allows a p ocess o e ie e da a om o he p ocesses. x e e s o a iables in he local
s a e o he p ocess execu ing his ins uc ion, bu emay e e o a iables in o he p ocesses
pa icipa ing in in e ac ion a. Se e al imp o emen s o his nai e communica ion mechanism
ha e been p oposed, c . [8,9,24].
Mul i-choice ins uc ions. They a e o he o m [n
i=1Gi→Si], whe e each Giis a gua d and Siis a
lis o ins uc ions. Gua ds a e o he o m B&ax:= e,whe eBis a Boolean exp ession and
he es is an in e ac ion ins uc ion. They a e passable, i.e. hei co esponding ins uc ions can
be execu ed, i he Boolean exp ession holds and in e ac ion ais enabled. I B& is omi ed, i
is in e p e ed as ue&; i &ax:= eis omi ed, i is in e p e ed as &,whe e deno es an
anonymous local in e ac ion. No e ha bo h pa s o a gua d canno be omi ed.
Mul i-choice loops. They a e o he o m ∗[n
i=1Gi→Si]. Thei seman ics is simila o a mul i-
choice ins uc ion, excep o he ac ha he whole ins uc ion is epea ed un il none o he
Boolean exp essions ha gua d he al e na i es is ue.
APPENDIX B. PREVIOUS RESULTS
A p elimina y e sion o his wo k was p esen ed a he Eu o-Pa 2002 con e ence [30]. The e, we
p esen ed a no ion called SKF (s ong k- ai ness), which di e s om CFFkin ha he se o linked
in e ac ions was calcula ed a un ime, whe eas i is now calcula ed a compile ime. Tha is, wo
in e ac ions whe e conside ed o be linked as long as hey had a common pa icipan a un ime, no a
compile ime.
In spi e o being so simila , he esul s a e e y di e en . Figu e B1 shows ha CFFkalle ia es
conspi acies be e han SKF because he a ia ion is smalle . Since philosophe s a e con inuously
o e ing o pa icipa e in an in e ac ion, be i a Ge in e ac ion o a Rel in e ac ion, CFFkin oduces
mo e delays because he se o in e ac ions linked a compile ime is usually g ea e han he se o
in e ac ions linked a un ime, and hus needs mo e in e ac ions o be s able be o e selec ing one o
hem, which allows us o con ol conspi acies be e han SKF.
0
10
20
30
40
50
60
70
80
90
100
0 102030405060708090
Philosophe
Lunches
Figu e B1. Dis ibu ion o lunches using SKF (k =1).
ACKNOWLEDGEMENTS
We a e hank ul o ou e e ees and P o esso Ma onicolas o hei insigh ul sugges ions and hei con ibu ions
o imp o e ou esul s. We would also like o hank he pa icipan s o he Eu o-Pa 2002 Con e ence o engaging
in ui ul discussion on ai ness and MI-based sys ems wi h us.
REFERENCES
1. F ancez N, Fo man I. In e ac ing p ocesses: A mul ipa y app oach o coo dina ed dis ibu ed p og amming. Addison-
Wesley: Reading, MA, 1996.
2. F ancez N. Fai ness. Sp inge : Be lin, 1986.
3. Lampo L. Speci ying Sys ems: The TLA+Language and Tools o Ha dwa e and So wa e Enginee s (Lec u e No es in
Compu e Science, ol. 1845). Addison-Wesley: Bos on, MA, 2002.
4. Alu R, Henzinge TA. Fini a y ai ness. ACM T ansac ions on P og amming Languages and Sys ems 1998; 20(6):1171–
1194.
5. A ie PC, F ancez N, G umbe g O. Fai ness and hype ai ness in mul ipa y in e ac ions. Dis ibu ed Compu ing 1993;
6(4):245–254.
6. Beauquie J, Da a AK, G adina iu M, Magnie e F. Sel -s abilizing local mu ual exclusion and daemon e inemen .
P oceedings o he DISC 2000 In e na ional Con e ence (Lec u e No es in Compu e Science, ol. 1914). Sp inge : Be lin,
2000; 223–237.
7. Jayasimha D, De showi z N. Bounded ai ness. Technical Repo TR-615, Cen e o Supe compu ing Resea ch and
De elopmen . Uni e si y o Illinois, 1986.
8. Co chuelo R, P´e ez JA, Ruiz–Co ´es A. Aspec -o ien ed in e ac ion in mul i-o ganiza ional Web-based sys ems. Compu e
Ne wo ks 2003; 41(4):385–406.
9. Co chuelo R, P´e ez JA, To o M. A mul ipa y coo dina ion aspec language. ACM Sigplan 2000; 35(12):24–32.
10. Joung YJ. A comp ehensi e s udy o he complexi y o mul ipa y in e ac ion. Jou nal o he ACM 1996; 43(1):75–115.
11. Tang P, Mu aoka Y. Pa allel p og amming wi h in e ac ing p ocesses. P oceedings o he 12 h In e na ional Wo kshop on
Languages and Compile s o Pa allel Compu ing, LCPC’99 (Lec u e No es in Compu e Science, ol. 1863). Sp inge :
Be lin, 2000; 201–218.
12. Felbe P, Rei e MK. Ad anced concu ency con ol in Ja a. Concu ency and Compu a ion: P ac ice and Expe ience
2002; 14(4):261–285.
13. Fayad M. E–F ame: A p ocess-based, objec -o ien ed amewo k o e-comme ce. P oceedings o he In e na ional
Con e ence on In e ne Compu ing IC’2001. CSREA P ess: Las Vegas, NV, 2001; 124–128.
14. Keen A, Ge T, Ma is J, Olsson R. JR: Flexible dis ibu ed p og amming in an ex ended Ja a. P oceedings 21s In e na ional
Con e ence on Dis ibu ed Compu ing Sys ems, ICDCS’01. IEEE P ess: Los Alami os, CA, 2001; 575–584.
15. Lea D. Concu en P og amming Using Ja a: Design P inciples and Pa e n. Addison-Wesley: Reading, MA, 1999.
16. Lynch NA, Me i M, Weihl WE, Feke e A. A omic T ansac ions (Lec u e No es in Compu e Science, ol. 1845). Mo gan
Kau mann: San Ma eo, CA, 1994.
17. Kindle E, Wal e R. Mu ex needs ai ness. In o ma ion P ocessing Le e s 1997; 62(1):31–39.
18. Schneide FB, Lampo L. Ano he posi ion pape on ‘ ai ness’. So wa e Enginee ing No es 1988; 13(3):1–2.
19. Dijks a EW. Posi ion pape on ‘Fai ness’. So wa e Enginee ing No es 1988; 3(2):18–20.
20. Bes E. Fai ness and conspi acies. In o ma ion P ocessing Le e s 1984; 18(3):215–220.
21. Bes E. E a um: Fai ness and conspi acies. In o ma ion P ocessing Le e s 1984; 19(4):162.
22. Lampo L. Fai ness and hype ai ness. Dis ibu ed Compu ing 2000; 13(4):239–245.
23. Ap KR, F ancez N, Ka z S. App aising ai ness in languages o dis ibu ed p og amming. Dis ibu ed Compu ing 1988;
2(4):226–241.
24. Co chuelo R. P o o yping cons ain -based speci ica ions o dis ibu ed sys ems. PhD Thesis, Facul ad de In o m´a ica y
Es ad´ıs ica, Dp o. de Lenguajes y Sis emas In o m´a icos, Uni e si y o Se illa, 1999.
25. Co chuelo R, Ruiz D, To o M, Ruiz–Co ´es A. Implemen ing mul ipa y in e ac ions on a ne wo k compu e . P oceedings
XXV h Eu omic o Con e ence. IEEE P ess: Milan, I aly, 1999; 458–465.
26. Sa ang PG, Ada ia E, Jouhie B. J#. W ox P ess: Bi mingham, U.K., 2002.
27. Olde og E, Ap KR. Fai ness in pa allel p og ams: The ans o ma ional app oach. ACM T ansac ions on P og amming
Languages and Sys ems 1988; 10(3):420–255.
28. Joung YJ. Two decen alized algo i hms o s ong in e ac ion ai ness o sys ems wi h unbounded speed a iabili y.
Theo e ical Compu e Science 2000; 243(1–2):307–338.
29. Joung YJ. S ong in e ac ion ai ness ia andomiza ion. IEEE T ansac ions on Pa allel and Dis ibu ed Sys ems 1998;
9(2):137–149.
30. Ruiz D, Co chuelo R, P´e ez JA, To o M. An algo i hm o ensu ing ai ness and li eness in non-de e minis ic sys ems
based on mul ipa y in e ac ions. P oceedings o he Eu o–Pa 2002 In e na ional Con e ence (Lec u e No es in Compu e
Science, ol. 2400). Sp inge : Be lin, 2002; 563–572.