A Dis ibu ed Solu ion oSynch onousMul ipa yIn e ac ion
RAFAELCORCHUELO, DAVIDRUIZ,MIGUEL TORO,JOS´E L. ARJONA, AND JOS´EM. PRIETO
Depa amen o de Lenguajesy Sis emasIn o m´a icos
Facul ad de In o m´a ica y Es ad´ıs ica,Uni e sidadde Se illa
A enida de la Reina Me cedess/n,41.012,Se illa
ESPAN˜ A — SPAIN
Abs ac : Mul ipa y in e ac ionsa e he key odesc ibep oblemswhe e h ee o mo e p ocessesneed ocol-
labo a e simul aneouslyin o de o sol eap oblem, and hispape aims o show hewayweha eimplemen ed
hismechanismina ne wo kcompu e . The main ea u e o ou solu ionis ha i isno boundupwi h he un-
de lying ne wo k, so i ishighly po able. Wealso epo someexpe imen al esul s ha show ha ou p o o ype
pe o msqui e wellonlowcos compu e s.
Key wo ds: Mul ipa yin e ac ion,ne wo kcompu e s, ai ness,IP, SR.
1 In oduc ion
Whendesc ibing hebeha iou o asys emimplies
ha mo e han wop ocessesneed ocollabo a esim-
ul aneouslyino de osol eap oblem,classical
in e –p ocessin e ac ionp imi i essuchas endez–
ouso emo ep ocedu ecallsa eno adequa ebe-
cause hesolu ionisusually oosophis ica ed.These
p imi i esa eexampleso heclassicalclien /se e
model ha emphasises woen i iesexchangingmes-
sages,and heya eclea lyinsu icien in hesesi u-
a ionsbecauseweneed odecomposena u almul i-
pa yin e ac ionsin ose e allow–le elin e ac ions
ha u nou solu ionsin o ickydesc ip ions.
Thismo i a edse e al esea che s oin oduce
mul ipa yin e ac ioncons uc sin olanguages o
hedesc ip iono dis ibu ed, eac i esys ems.
Sc ip s,Raddleo UNITYa egoodexamples,bu
IP(In e ac ingP ocesses)[7]s andsou becausei
isin ended oha eadual ole:on heonehand,i
isin ended obeadis ibu edsys emspeci ica ion
languageequippedwi hsoundseman ics ha u ni
in oalanguageamenable o o mal easoning;on he
o he hand,i isin ended obeanassemble language
suppo ingmo esophis ica edhigh–le elspeci ica-
ionlanguagessuchasLOTOSo ESTELLE.IPis
equippedwi ha ichse o s a emen s,being hemos
impo an hein e ac ions a emen s ha a eused o
desc ibecoo dina ionamongase o p ocesses.
Se e alalgo i hms ha implemen hemul ipa y
in e ac ions a emen sIPinco po a esha ebeende-
sc ibedin heli e a u e[4,8,9],bu heya eclosely
ela ed o heunde lyingne wo ka chi ec u eand
heycanno beeasilyadap ed oo he ne wo ks.This
isp oblema icalbecausei makes hemdi icul o
po ,andinco po a ing heno iono ai nessin o
hemisusuallyqui e icky.Fai nessisanimpo an
p ope y ha ensu es ha e e yin e ac ionisgi en
achance obeexecu ed.Ingene al,se e alin e ac-
ionsmaybe eady o execu iona hesame ime,
bu IPseman icss a es ha onlyonecanbe i eda
eachsynch onisa ionpoin .Thus,whenacon lic oc-
cu s,onein e ac ionisexecu ed o hede imen o
he es .Fai nessen o ces ha noin e ac ionisneg-
lec ed o e e ,bu inco po a ingi in o healgo i hms
weha eci edis a he di icul .Asa esul , ewIP
implemen a ionsa ea ailable.Theonedesc ibedin
[1]is hes a e–o – he–a compile ,bu i isno in
widesp eadusebecausei unsona anspu e andi
isonlyin ended o e mina ingp og ams.
Thispape aims odesc ibeasolu ionweha e
implemen ed o hisin e ac ionmechanismonane -
wo kcompu e ,whichisacollec iono wo ks a ions
whoselinkscanbelogically ea angeda un ime.
Thisallowsus o easydis ibu ion,i ise icien
enough,andmakesinco po a iono ai nessex-
emely easy while p ese ing po abili y. We ha e
o ganised i as ollows: sec ion 2 ecalls he no ion
o mul ipa y in e ac ion by means o well–known
p oblems; sec ion 3 desc ibes ou implemen a ion,
he algo i hm we ha e implemen ed o deal wi h ai
selec ion o con lic ing in e ac ions, and we also e-
po some expe imen al esul s ha show ha ou al-
go i hms pe o m well enough; sec ion 4 glances a
o he au ho s’ wo k and compa es i wi h ou s; i-
nally, sec ion 5 shows ou conclusions and he wo k
we a e planning on doing.
2 Mul ipa y in e ac ions
In his sec ion, we in oduce mul ipa y in e ac ion in
he con ex o IP. We assume ha he eade is a-
milia wi h his language, so we only ecall he main
concep s. I i is no he case, please consul [7].
In IP, sys ems a e unde s ood as collec ions o
co–ope a ing sequen ial p ocesses whose ela ion-
ships a e based on mul ipa y in e ac ions. An in e -
ac ion s a emen is a s a emen o he o m
a
[
x
:=
e
]
,
whe e
a
is e e ed o as he name o he in e ac ion
and
x
:=
e
is a sequence o pa allel assignmen s usu-
ally e e ed o as he communica ion pa . A p ocess
is said o be a pa icipan o in e ac ion
a
i i has
an in e ac ion s a emen in ol ing
a
in i s body, and
when a p ocess has a i ed a a poin whe e execu ing
such in e ac ion is one o i s possible con inua ions
we say ha i is eadying i . When an in e ac ion is
eadied by all o i s pa icipan s, we say ha i is en-
abled, and when se e al in e ac ions a e enabled a
he same ime we say ha a con lic has occu ed.
IP also p o ides gua ded non–de e minis ic
choice s a emen s o he o m
[[]
n
i
=1
G
i
!
S
i
]
, gua d-
ed non–de e minis ic loops

[[]
n
i
=1
G
i
!
S
i
]
and a
dummy s a emen deno ed by he key wo d
sk ip
.
Gua ds a e o he o m
B
&
a
[
x
:=
e
]
,whe e
B
is a
boolean exp ession and he es is an usual in e ac ion
s a emen . A gua d is said o be passable, i.e., hei
co esponding s a emen s can be execu ed, as long as
B
holds and
a
is enabled.
2.1 Synch onisa ion
We illus a e synch onisa ion by means o he din-
ing philosophe s p oblem, which is a classic mul i-
p ocess synch onisa ion p oblem ha consis s o i e
philosophe s si ing a a able who do no hing bu
hink and ea . The e is a single o k be ween each
philosophe , and hey need o pick bo h o ks up in
o de o ea . This p oblem is he co e o a la ge class
o p oblems whe e a p ocess ( he philosophe ) needs
o acqui e a se o esou ces ( he o ks) in mu ual ex-
clusion.
The ob ious solu ion o his p oblem, using wo–
pa y in e ac ions, consis s o picking up o ks in se-
quence. Ne e heless, a p oblem a ises i each philo-
sophe 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 his
case, a deadlock has occu ed, and all philosophe s
will s a e. I we used mul ipa y in e ac ions, each
philosophe would pick up his/he wo o ks a he
same ime so ha no deadlock may a ise. Figu e 1
shows a solu ion o his p oblem in IP. The philosoph-
e s a e ep esen ed by p ocesses
P hil osophe
i
,and
he o ks by
Fo k
i
(
i
=1
;
2
;::: ;n
).
P hil osophe
i
e e nally ies o ge his/he s associa ed o ks by in-
e ac ing in he h ee–pa y in e ac ion
ge o ks
i
o-
ge he wi h
Fo k
i
and
Fo k
i
,
1
(we assume ha in-
dex a i hme ic is cyclic, i.e.,
1
,
1=
n
and
n
+1=1
).
Thus, acqui ing a esou ce is speci ied as synch on-
ising wi h he co esponding p ocesses in an in e ac-
DIN PHIL :: [
k
n
i
=1
Philosophe
i
kk
n
i
=1
Fo k
i
], whe e
Philosophe
i
::
*[ ge o k
i
[]
,!
ea ; elease o k
i
[]; hink ]
Fo k
i
::
*[
ge o k
i
[]
,!
elease o k
i
[]
[]ge o k
i
+1
[]
,!
elease o k
i
+1
[]
].
Figu e 1: A solu ion o he dining philosophe s p oblem in IP.
LEADER :: [
k
n
i
=1
P
i
], whe e
P
i
::
w
i
: na u al; leade
i
: boolean
g
w
i
:= a weigh ;
Elec [leade
i
:= (w
i
=
max
1

j

n
w
j
g
)
];
[ leade
i
!
execu e algo i hm ].
Figu e 2: A solu ion o he leade elec ion p oblem.
EXAMPLE :: [ P
k
Q],whe e
P
i
::
x: na u al
g
*[ A[x := y]
!
skip [] B[x := y]
!
skip]
Q::
y: na u al
g
*[ A[y := x]
!
skip [] B[y := x]
!
skip]
Figu e 3: A global pic u e o ou solu ion.
ion. A e
P hil osophe
i
has picked his/he o ks
up, he o she ea s, eleases he o ks, spends some
mo e ime hinking, and he whole p ocess is epea ed
again.
2.2 Communica ion
We illus a e he no ion o mul ipa y communica ion
by means o he leade elec ion p oblem, which is
a classic mul i-p ocess communica ion p oblem ha
consis s o a numbe o p ocesses ha a e able o ex-
ecu e an algo i hm, bu he e is no a p io i candida e
o un i . The e o e, an elec ion unde he p ocesses
needs o be held. The c i e ion p ocesses use o se-
lec a leade is qui e simple: each o hem is sup-
posed o ha e a di e en na u al weigh
w
i
in he sys-
em, and he leade is he p ocess
P
i
sa is ying ha
w
i
=max
1

j

n
w
j
g
.
The usual solu ion o his p oblem, using wo–
pa y in e ac ions, consis s o a anging he p ocesses
in a unidi ec ional ing whe e only pai s o neighbo -
ing p ocesses can exchange hei weigh s and calcu-
la e a local maximum. These maximums a e p opag-
a ed in he ing so ha a e
n
,
1
ounds he global
maximum has been calcula ed. The p oblem he e is
ha synch onizing he whole se o p ocesses so ha
each one passes i s local maximum a he igh mo-
men is qui e icky. I we used mul ipa y commu-
nica ion, all o he p ocesses would synch onise and
ha e access o he weigh s o he p ocesses ha e sim-
ul aneously. An immedia e solu ion o his p oblem
is shown in igu e 2. He e, he mul ipa y in e ac-
ion
E l ec
synch onises all o he p ocesses, allow-
ing hem o exchange in o ma ion and decide which
one has o be assigned o he ole o leade . When
se e al p ocesses synch onise and in e ac , a empo -
a y global combined s a e is o med by combining he
local s a es o he p ocesses pa icipa ing in ha in e -
ac ion so ha hey can ead in o ma ion in he s a e o
o he pa icipan s. This way, each p ocess synch on-
ising on
E l ec
can ead he weigh s he o he p o-
cesses ha e, compu e he maximum in pa allel, com-
pa e i o i s own weigh and s o e he esul o his
compa ison in i s local a iable
l eade
i
. A e in e -
ac ion, he one ha inds i sel ha ing he maximum
weigh execu es he app op ia e algo i hm.
3 Implemen ing in e ac ions
The bulk o implemen ing mul ipa y in e ac ions
consis s o he so-called p e–synch onisa ion, com-
munica ion and pos –synch onisa ion p oblems. The
o me , consis s o de ec ing which in e ac ions a e
enabled and o esol ing con lic s. The communica-
ion p oblem consis s o ansmi ing he piece o in-
o ma ion each p ocess needs so ha ne wo k load is
minimum. Finally, he pos –synch onisa ion p oblem
consis s o s opping all o he p ocesses pa icipa ing
in an in e ac ion un il he o he s ha e comple ed hei
communica ion pa s.
This sec ion shows he solu ion o hese p oblems
we ha e implemen ed1, and also epo s some expe i-
men al esul s ha show ha ou implemen a ion pe -
o ms qui e well in low cos compu e s.
3.1 Ou solu ion
We ha e implemen ed a dis ibu ed solu ion o mul-
ipa y in e ac ions whe e each IP p ocess uns on
a di e en i ual machine, and he e is a se o
compile –gene a ed p ocesses ha deal wi h he
p oblems we ha e jus men ioned. Ou solu ion asso-
cia es a p ocess called manage wi h each in e ac ion,
and he e is also a cen al schedule . Each manage
is esponsible o de ec ing enablemen o disable-
men o i s co esponding in e ac ion, and he cen al
schedule deals wi h ai selec ion o in e ac ions.
Each IP p ocess is logically connec ed o he
manage s o he in e ac ions i pa icipa es in, and
hey send hem messages in o de o in o m hem
whe he hey a e eadying hei associa ed in e ac-
ions o no . When a manage de ec s enablemen
o disablemen , i sends i s esul o he cen al in e -
ac ion schedule , which, in u n, selec s one enabled
in e ac ion ai ly. In o de o de ail how ou solu ion
wo ks we use he p og am and he ace we show in
igu e 3. I consis s o wo p ocesses
P
and
Q
ha
can exchange he alues o hei local a iables
x
and
y
ei he by pa icipa ing in in e ac ion
A
o
B
,which
a e pe manen ly in con lic .
P ocesses do local compu a ions and, when hey
a i e a a poin whe e hey a e eadying an in e -
ac ion, hey send messages o he in e ac ion man-
age s in o de o in o m hem whe he hey a e eady-
ing he in e ac ion hey manage o no . These mes-
sages a e o he o m
Readies
(
b
)
,being
b
a boolean
alue. Upon ecep ion o hese messages, he in e ac-
ion manage s can de ec enablemen o disablemen
e y easily because hey only need o see i all o he
p ocesses ha a e connec ed o i a e eadying he in-
e ac ion hey manage o no . Once hey ha e his in-
o ma ion, hey send i o he in e ac ion schedule by
means o messages o he o m
E nabl ed
(
b
)
,being
b
a boolean alue. I hen selec s one o he enabled
in e ac ions ai ly and sends messages o he o m
S el ec ed
(
b
)
o he in e ac ion manage s o le hem
know whe he hei associa ed in e ac ion has been
selec ed o no . In any case, he in e ac ion manage s
pass hese messages o he p ocesses ha a e con-
nec ed o i , hus comple ing he p e–synchonisa ion
s age.
A e synch onisa ion, communica ion akes
place. Those p ocesses ha ha e go a message o
he om
S el ec ed
(
ue
)
om an in e ac ion man-
age know ha hey can execu e he co esponding
in e ac ion, so hey s a communica ion by send-
ing i he da a hey a e esponsible o by means o
messages o he o m
W i e
(
)
. A e all he da a
has been collec ed, he in e ac ion manage sends
each pa icipa ing p ocess he piece o in o ma ion i
needs by means o messages o he o m
Read
(
)
.
In ou i s p o o ype, communica ion was mo e ex-
pensi e because we used wo messages o ead da a
om he in e ac ion manage : a message o he o m
Req ues
(
x
)
o o in o m i we we e in e es ed in a i-
able
x
, and a subsequen message o send i s alue
om he manage o he co esponding p ocess. In
ou la es e sion, he manage knows wha piece o
1Due o space limi a ions, we only p esen a de ailed desc ip ion bu no a o malisa ion. The eade who is in e es ed can con ac
he au ho s in o de o ge a copy o ou algo i hm and i s o malisa ion.
in o ma ion each p ocess needs and sends i wi hou
any need o a
Req ues
message.
Acco ding o IP seman ics, no pa icipan in an
in e ac ion can con inue un il hey all ha e comple ed
hei communica ion pa s. We ha e implemen ed he
simples solu ion o en o ce his: we use a commi
p o ocol in which e e y pa icipan sends a message
indica ing i is inished o he co esponding manage ,
which wai s un il he las pa icipan is done and in-
o ms hen he cen al schedule . I hen sends mes-
sages o le he p ocesses know he in e ac ion is in-
ished and hey can con inue.
3.2 Fai ness
Fai ness is an impo an concep ha ensu es ha
e e y elemen o a non–de e minis ic p og am ha is
enabled su icien ly o en, will e en ually p og ess,
i.e., none o hem is neglec ed o e e . In he con-
ex o IP, ai selec ion o enabled in e ac ions is he
only way o ensu e li eliness, e mina ion o e en-
ual esponse o an e en . No ice, o example, ha
in he p og am in igu e 1, in e ac ions
ge o k
i
and
ge o k
i
+1
a e always in con lic when hey a e
bo h enabled, bu only one can be execu ed. The only
way o gua an ee ha each in e ac ion ha is enabled
“su icien ly o en” will e en ually be selec ed o ex-
ecu ion consis s o assuming ha he unde lying con-
lic esolu ion mechanism is ai . Acco ding o he
meaning o “su icien ly o en” we ha e he ollow-
ing le els o ai ness: weak, i e e y elemen con inu-
ously enabled is selec ed in ini ely o en, and s ong,
i e e y elemen ha is in ini ely o en enabled is in-
ini ely o en selec ed.
We ha e implemen ed s ong ai ness by associ-
a ing a p io i y a iable
p
a
wi h each in e ac ion
a
,
as sugges ed in [6]. These a iables a e ini ially as-
signed andom alues, and he cen al schedule se-
lec s among he se o con lic ing in e ac ions ha
whose coun e has he minimum alue (maximum
p io i y). I mo e han one a iable is minimum o e
he se o p io i y a iables, one o hem is uni o mly
selec ed. Upon e mina ion o he selec ed in e ac-
ion, i s associa ed p io i y a iable is ese o an a -
bi a y andom alue while he coun e s associa ed
wi h hose in e ac ions which we e neglec ed a e de-
c eased by 1. This algo i hm has been p o ed co ec
in [6], bu , un o una ely, we ha e p o ed ha i loses
comple eness i coun e s a e ini e, i.e., he e a e ai
execu ions ha canno be gene a ed by his algo i hm.
Please, do con ac he au ho s i you a e in e es ed in
his heo e ical esul .
3.3 Expe imen al esul s
We ha e implemen ed an IP compile , and he a -
ge language we selec ed was SR (Synch onising Re-
sou ces) [2], a well–known, widely–a ailable lan-
guage o w i ing concu en p og ams. Ou p o o-
ype uns on a ne wo k compu e composed o se -
e al compu e s unning Sola is, AIX and Linux, he
pla o ms we ha e in ou labo a o ies.
In his sec ion, we epo he esul s o some em-
pi ical es s we ha e ca ied ou in o de o ind ou
how ou implemen a ion pe o ms. The es s we e
un on a se o 10 low cos IBM 320H compu e s un-
ning a 25 MHz. They a e equipped wi h 16 Mb o
memo y, AIX 3.2.5, SR 2.3.1, GNU C 2.4.7, and hey
a e in e connec ed by means o a 10 Mbps E he ne
LAN. Ou es consis ed o execu ing he ollowing
p og am:
TEST :: [
k
n
i
=1
P
i
], whe e
P
i
::
coun : na u al := 0
g
*[ coun
<
500
!
In []; coun ++; wo k 1 sec. ]
I consis o
n
p ocesses ha jus synch onise on
In
500 imes, and do some wo k ha akes hem 1
second. We execu ed i 15 imes in a single machine
gi ing
n
alues om 2 up o 10, i.e., we inc eased he
numbe o pa icipan s in
In
om 2 up o 10. We
hen execu ed his es assigning a p ocess o each o
ou machines, hus composing a ne wo k compu e .
We ha e also ca ied ou a eg ession analysis
a a 95% con idence le el whose esul s a e epo -
ed in he able below. I shows ha he ime ou al-
go i hms ake inc eases abou 726 seconds each ime
a new pa icipan is added in he case o a single com-
pu e (
T
SC
), whe eas he ise is only 423 seconds
in a ne wo k compu e (
T
NC
). The numbe o in-
e ac ions pe minu e also dec eases as he numbe
o pa icipan s inc eases, bu ou ne wo k compu e
execu es 9.42 mo e in e ac ions pe minu e han ou
single compu e . This app oxima ion is qui e accu -
a e as he coe icien o de e mina ion
R
2
shows. This
coe icien anges in alue om 0 o 1, and he highe
i s alue is, he mo e accu a e he app oxima ion is.
In gene al, hese esul s show ha ou dis ib-
u ed implemen a ion pe o ms qui e well in low cos
wo ks a ions.

Magni ude P edic ion
R
2
Time
T
SC
= 725
:
93
n
+ 718
:
78
0.99
T
NC
= 423
:
24
n
+ 140
:
88
0.83
In ./Min.
I
SC
=20
:
30
e
,
0
:
19
n
0.95
I
CN
=43
:
69
e
,
0
:
20
n
0.85
4 Rela ed wo k
The i s algo i hms o dis ibu ed co-o dina ion
we e p oduced in he con ex o CSP, and we e e-
s ic ed o wo–pa y in e ac ions. Ne e heless, mo e
ecen ly, he p oblem o mul ipa y in e ac ions has
become o g ea in e es . Chandy and Mis a [5]
de eloped wo algo i hms ha became he basis o
Bag odia’s algo i hm [4]. In his algo i hm, each in-
e ac ion has an associa ed manage , which is simila
o ou dis ibu ed solu ion because i is sen messages
when p ocesses a e eady o in e ac and de ec s en-
ablemen s. When one o hem de ec s an enabled
in e ac ion, a mu ual exclusion algo i hm is un in
o de o p e en wo di e en in e ac ions om be-
ing execu ed a he same ime. The p oblem he e is
ha Bag odia’s algo i hm assumes ha he unde ly-
ing communica ion ne wo k has only hose links con-
nec ing he p ocesses ha pa icipa e in an in e ac-
ion. This is p oblema ical because i is no always
possible o place p ocesses a adequa e nodes in a eal
ne wo k.
Se e al mo e algo i hms ha e been de eloped by
Ga g [8] o Joung and Smolka [9] o di e en ne -
wo k a chi ec u es. In gene al, hese pape s also o-
cus on a chi ec u al aspec s we a e no in e es ed in.
Ins ead o making ou solu ion dependen on he un-
de lying ne wo k, we ha e decided o ely on SR
o e icien dis ibu ion. This makes ou algo i hms
po able, and inco po a ing s ong ai ness in o hem
has been e y easy, whe eas inco po a ing his no ion
in o he well–known algo i hms is a he di icul .
A p esen , he esea ch is cen ed on implemen ing
s onge ai ness assump ions han hose p o ided by
he unde lying ne wo k [3].
As a as we know, IP has been implemen ed in
he labo a o y [1], and uns on a anspu e –based
compu e . Un o una ely, he implemen a ion is only
in ended o e mina ing IP p og ams. Ou s can
be un in i ually any ne wo k compu e composed
o inexpensi e wo ks a ions and pe sonal compu e s.
Fu he mo e, i can deal wi h bo h e mina ing and
non– e mina ing p og ams.
5 Conclusions and u u e wo k
In his pape , we ha e p esen ed a solu ion o he
p oblem o dis ibu ed mul ipa y in e ac ions. We
ha e also epo ed some expe imen al esul s ha
show i is e ec i e enough o be used in p ac ical ap-
plica ions. We also hink ha he solu ion we ha e
p esen ed is a ac i e because i is no bound up
wi h he unde lying ne wo k, and inco po a ing an
algo i hm o ai selec ion o in e ac ions has been
s aigh o wa d.
A p esen , we a e wo king on in oducing mul i-
pa y in e ac ion in he con ex o CORBA. We ag ee
wi h he au ho s o IP in ha i will no eplace cu en
p og amming languages, bu we hink ha he no-
ion o mul ipa y in e ac ion is qui e impo an and i
would be desi able o languages such as C++ o Ja a
o suppo i . This way, we a e implemen ing mul i-
pa y in e ac ions using CORBA, which is a middle-
wa e ha is e y success ul in he indus ial wo ld.
Re e ences
[1] A. Adi . Compiling P og ams wi h Mul ipa y In e ac ions
and Teams. PhD hesis, Technion, 1994.
[2] G.E. And ews and R.A. Olson. The SR P og amming Lan-
guage. The Benjamin–Cummings Publishing Company,
1993.
[3] P.C. A ie, I.R. Fo man, and E. Le y. On ai ness as an ab-
s ac ion o he design o dis ibu ed sys ems. In P oceeding
o he 10 h In e na ional Con e ence on Dis ibu ed Com-
pu ing Sys ems, Pa is, F ance, June 1990. IEEE.
[4] R. Bag odia. P ocess synch oniza ion: Design and pe o m-
ance e alua ion o dis ibu ed algo i hms. IEEE T ansac-
ions on So wa e Enginee ing, 15(9):1053–1065, Sep em-
be 1989.
[5] K.M. Chandy and J. Mis a. Pa allel P og am Design: A
Founda ion. Addison–Wesley, 1988.
[6] N. F ancez. Fai ness. Sp inge –Ve lag, 1986.
[7] N. F ancez and I. Fo man. In e ac ing p ocesses: A mul-
ipa y app oach o coo dina ed dis ibu ed p og amming.
Addison–Wesley, 1996.
[8] V.K. Ga g and S. Ajmani. An e icien algo i hm o mul i–
p ocess sha ed e en s. In P oceedings o he 2
nd
Symposium
on Pa allel and Dis ibu ed Compu ing, 1990.
[9] Y.J. Joung and S.A. Smolka. A comple ely dis ibu ed
and message-e icien implemen a ion o synch onous mul-
ip ocess communica ion. In Pen-Chung Yew, edi o , P o-
ceedings o he 19
h
In e na ional Con e ence on Pa al-
lel P ocessing. Volume 3: Algo i hms and A chi ec u es,
pages 311–318, U bana-Champaign, Illinois, Augus 1990.
Pennsyl ania S a e Uni e si y P ess.