A Positive Acknowledgment Protocol for Causal Broadcasting.
AbstractCausal broadcasting has been introduced to reduce the asynchrony of communication channels inside groups of processes. It states that if two broadcast messages are causally related by the happened-before relation, these messages are delivered in their sending order to each process of the group. Even though protocols implementing causal broadcasting do not add control messages, they suffer from the typical pitfall of the timestamping technique: To ensure causal ordering, application messages have to piggyback a vector time of counters whose range of variation is unbounded. In this paper, we investigate such a range and define the concept of causal window of a process in which all counters of a vector time of a just arrived message at that process fall. We prove that, by using a causal broadcasting (one-to-all) protocol that follows a positive acknowledgment method, the width of the causal window of each process is limited. This allows a modulo k implementation of vector times when considering k greater than the width of the causal window of each process. The protocol is applicable to data link or transport layers using acknowledge messages to ensure reliable transfer of data. The paper also proposes two variants of the protocol based on causal windows. Both of them increase the concurrency of the protocol at the expense of wider causal windows.
Introduction
Asynchrony of communication channels is one of the major causes of nondeterminism in distributed
systems. The concept of causal ordering of messages has been introduced in the context of broadcasting
communication by Birman and Joseph [8] in order to reduce such an asynchrony. Causal
ordering means if two broadcast messages are causally related [14], they are delivered in their sending
order to each process. In light of this, when a message is delivered to a process, all messages
that causally precede it have been already delivered to that process.
To master asynchrony, other communication modes have been defined such as FIFO, Rendezvous
and logical instantaneous ordering [20]. From the user viewpoint, causal ordering increases
the control of a distributed application compared to a simple FIFO ordering, at the cost of a reduction
of the potential concurrency of the distributed application. Compared with logically instantaneous
communication, causal ordering provides more concurrency and simplicity of implementation.
Moreover, causal ordering is not prone to deadlock as Rendezvous, being an asynchronous paradigm
of communication. Actually, causal ordering extends the concept of FIFO channels connecting one
sender and one receiver to systems connecting several senders and one receiver.
Causal ordering has been proved to be very useful in taking snapshots of distributed applications,
in controlling distributed applications, in managing replicated data and in allowing consistent
observations of distributed computations [10, 18]. Recently, extensions of causal ordering have
been proposed to cope with mobile computing environments [16] and with unreliable networks and
distributed applications whose messages have limited time validity [5, 6]. Moreover, the concept of
causal ordering is not limited to message-passing environments. In the context of shared-memory
systems, a causal memory has been introduced by Ahamad et al. in [1] as a consistency criterion.
Such a criterion does not introduce latencies while executing read and write operations.
Even though several interesting protocols implementing causal ordering appeared in the literature
[8, 9, 18, 21], this communication mode is not yet widely used in commercial platforms because
such protocols suffer from the typical pitfall of the timestamping (logical or physical) technique:
to ensure causal ordering, in the context of broadcasting, application messages have to piggyback
a vector time of unbounded integers (counters) whose size is given by the number of processes [15],
this vector represents actually the control information of a protocol.
However, data-link and transport layers of communication systems use messages, called acknowledgments
(acks, for short), to indicate the successful reception of data. Ack messages, produced
by such layers, are actually a source of information about the causal relations among application
messages that could be used to reduce the amount of control information of causal ordering pro-
tocols. In this paper we introduce the notion of causal window and propose a causal broadcasting
protocol which exploits the implicit information provided by ack messages 1 . A causal window of
a process represents the range of variation in which all counters of a vector time of a just arrived
message at that process fall. We prove that, by using a causal broadcasting protocol that follows
a positive acknowledgment (PAK) method [17, 23], the width of the causal window of each process
is bounded. This allows a modulo k implementation of vector times when considering k greater
than the width of the causal window of each process. We first propose a PAK causal broadcasting
protocol in which a process can send a message only when acks of the previous message, sent by
the same process, have been received. We analyze then the general case in which a credit ct - 1
is associated with each sending process; in this case, a process can send ct consecutive messages
before receiving the corresponding acks. Finally, we investigate the case in which a process employs
a positive/negative (PAK/NAK) scheme, i.e., a process can send a sequence of ct messages
without being acknowledged and then an ack message is required from the other processes after the
receipt of the ct-th message sent by the same process. Credits and the use of PAK/NAK scheme
allow an increase of the concurrency of the protocol (decreasing the number of the internal protocol
synchronizations), but enlarge the dimension of the causal window.
The protocol we propose could be employed as a part of the flow control of a transport layer 2
providing causal communication to the above layer. For example, current group communication systems
(e.g., ISIS [10]) implement causal protocols on the top of a FIFO flow control by piggybacking
on each application message a vector of unbounded integer.
The remainder of this paper is organized as follows. In Section 2 the general model of a
distributed computation, the concept of causal relation among events, vector times and the causal
ordering communication mode are introduced. Section 3 presents the causal window notion. Section
4 shows a causal broadcasting protocol based on causal windows when considering the credit of the
sender equal to one. At this end, in the same section, the positive acknowledgment method and
the modulo k implementation of vector times are introduced. Section 5 proposes the two variations
of the protocol of Section 4 based on a credit and a PAK/NAK scheme respectively.
1 Some interesting algorithms that exploit the implicit information provided by ack messages to guarantee FIFO
and reliable channels can be found in [7, 11, 22].
2 Examples of transport layers that use ack messages for data transferring are, among others, TCP, OSI/TP4,
VTMP and Delta-t [13].
2 Model of Distributed Computations
2.1 Distributed System
A distributed system is a finite set P of n processes fP that communicate only by
broadcasting messages 3 . The underlying system, where processes execute, is composed of n processors
(for simplicity's sake, we assume one process per processor) that can exchange messages.
We assume that each pair of processes is connected by a reliable 4 , asynchronous and FIFO logical
channel (transmission delays are unpredictable). Processors do not have a shared memory and
there is no bound for their relative speeds.
2.2 Distributed executions
Execution of a process P i produces a sequence of events which can be classified as: broadcast (bcast)
events, deliver (dlv) events and internal events. An internal event may change only local variables,
broadcast or delivery events involve communication. In particular, each broadcast event produces
delivery events, one for each process. Let a and b be two events occurred in a process P i , a
precedes b in P i , denoted aOE i b, iff a has been produced before b. Let m be a message and a and b
two events, a precedes b, denoted a OE m b, iff a is the bcast(m) event and b is the dlv(m) event.
A distributed computation can be represented as a partial order of events b
E is the set of all events and ! is the happened-before relation [14]. This relation is the transitive
closure of the union of OE i n) and OE m , it is denoted by !, i.e.,
Hereafter, we call M( b
E) the set of all messages exchanged in b
E and we do not consider internal
events as they do not affect the interprocess ordering of events. Let us, finally, introduce the notion
of the immediate predecessor of a message m.
Definition 2.1 A message m 1 is an immediate predecessor of a message
paper, we consider a message the atomic unit of data movement in the system. Results of the following
Sections apply even though we consider packets or byte streams as atomic data unit.
4 A detailed description of the protocol proposed in Section 4 in the case of unreliable channel is out of the aims
of this paper. The interested reader can refer to [3] for such a description.
E);
It is to be noted that a message m can have n immediate predecessors one for each process.
As an example the message m 1 depicted in Figure 4 is not an immediate predecessor of m 2 due to
message m x .
2.3 Vector Times
To capture the causality relation between relevant events of a distributed computation, vector times
were introduced simultaneously and independently by Fidge [12] and Mattern [15]. A vector time
for a process P i , denoted V T i , is a vector of counters whose dimension is equal to the number of
knowledge of the number of relevant events produced by P j .
Each relevant event a is associated with a vector time (V T a ) and a process P i updates its vector
time according to the following rules:
1. When P i starts its execution, each component of V T i is initialized to zero;
2. When a relevant event is produced by
3. When a message m is sent by
A copy of V T i is piggybacked on message m (denoted V Tm );
4. When a message m, sent by P j , arrives at P i , it updates its vector time in the following way:
Let a and b be two relevant events and V T a and V T b the vector times associated with, according
to properties of vector times [12, 15], we have:
when considering V T a
As we are interested in a broadcast environment, in the following, we assume broadcast events as
the only relevant events, actually P i 's knowledge of the number of messages
broadcast by P j . In this particular setting, and when considering causal communication, the above
protocol can be simplified as shown in the next section.
2.4 Causal Ordering
Causal ordering states that the order in which messages are delivered to the application cannot
violate the happened-before relation of the corresponding broadcast events [8]. More formally,
Definition 2.2 A distributed computation b
respects causal ordering if for any two broadcast messages
E) we have:
ng :: dlv(m 1
A first implementation of such an abstraction has been embedded in the ISIS system [8, 10].
It consists of adding a protocol over a reliable underlying system such that events of a distributed
computation be causally ordered at the process level 5 . At this end, deliveries are done by delaying,
by means of a delivery condition, those messages arrived too early at the underlying system.
A simple broadcast protocol, similar to the one presented by Birman et al. in [9], is shown in

Figure

1. It shows the behavior of process P i when sending and upon the arrival of a message.
The algorithm includes some vector time management rules (line S1,S2,S3 and R2) plus a delivery
condition DC(m) (line R1) associated with a message m. A message m is delivered to a process P i
as soon as the vector time, it carries (V Tm ) does not contain knowledge of messages sent to, but
not delivered by, process P i 6 . Formally,
ng
3 The Causal Window
In this section we investigate the range of variation of the values stored in the counters of vector
times during the evaluation of the delivery condition of a generic destination process. Upon the
arrival of a message m at process P i , the value of vector time counters, V Tm and V T i , involved in
the delivery condition DC(m) generate three cases:
1. V Tm
1. There are
consecutive messages, sent by process P j , that
causally precede m and that have not arrived at P i as shown in Figure 2.a. Message m, if
delivered, violates causal ordering.
5 Other interesting point-to-point implementations of causal ordering can be found in [18, 21].This fact makes a part of the rule 3 of Section 2.3 (i.e., (8h 6= useless in
a causal broadcasting protocol.
init for each h 2
procedure BCAST(m; is the message, P i is the sender %
begin
for each h 2 ng do send (m; V Tm) to P h ; od % event bcast(m) % (S2)
end.
when (m;V Tm) arrives at P i from
begin
ng
event dlv(m) % (R3)
end.

Figure

1: A simple causal broadcasting protocol
2.
1. There are CO j
consecutive messages, sent by process P j and
delivered to P i , that are concurrent to message m, as shown in Figure 2.b. Message m can
be delivered to P i without violating causal ordering.
3. sent by P j and delivered to P i , is an immediate
predecessor of m as shown in Figure 2.c. Message m can then be delivered to P i without
violating causal ordering.
(a) (b)
CO j
messages
messages
(c)

Figure

2: Values of vector times in the delivery condition.

Figure

3: The Causal Window CW j
If all counters of V Tm fall either in the case 3 or in the case 2, message m can be delivered.
Hence, upon the arrival of message m at process P i , counters of V Tm fall in a range of variation
that spans between V T
A causal window CW i is composed of a set of windows CW j
i one for each process P j . The
number
i represents the width of the window CW j

Figure

3). To implement a
causal broadcasting protocol employing modulo k vector times, we have to show the boundedness
of the width of the causal windows. In the general setting, as the one described in the previous
section, where transmission times are unpredictable, the width of CW i are non-limited.
4 A PAK Protocol based on Causal Windows
4.1 Positive Acknowledgement Method
To get a limited causal window, we assume processes follow a stop-and-wait approach. A process
broadcasts a message ( bcast(m) event) and waits for all the acks (n a:ack(m) events) before
executing any other broadcast event. Once all acks have arrived, such a broadcast message is said
to be "fully acknowledged" (f:ack(m) event). On the other side, each time a process receives a
broadcast message (arr(m) and then dlv(m) events), it sends an ack (s:ack(m)). Hence, at the
underlying system level six types of events occur and only bcast and dlv events are visible to the
application. So the processing of a broadcast message m, sent by P i , produces the following poset
of events, denoted PO(m):
OEm arr(m) OE1 dlv(m) OE1 s:ack(m) OEm
OEm arr(m) OEn dlv(m) OEn s:ack(m) OEm
the stop-and-wait approach implies a send condition SC 1 between any two successive messages sent
by the same process P i . Formally,
This synchronization is local and can be easily implemented by a boolean variable
processing broadcast (initialised to FALSE) in each process. The value TRUE indicates that the
process has broadcast a message m and it is waiting for f:ack(m) event. As soon as the event
occurs processing broadcast toggles enabling other broadcast of messages.
A remark on group communication. In a group communication system (e.g. ISIS [10],
TRANSIS [2] etc.) the occurrence of the event fully:ack of a message m corresponds to the
notion of stability of that message [4, 9], i.e., the sender of m learns that all the members of the
group have delivered m. In fact the use of ack messages is one of the methods to diffuse stability
information in a group of processes (other methods employ "gossiping" and piggybacking). The
notion of stability is a key point in many group communication problems such as security [19] and
large scale settings [4] just to name a few. So, informally, the condition SC 1 can be restated as
follows: a process cannot broadcast a message in a group till the previous one, it sent, is declared
stable. This condition is very conservative and implies a strong synchronization between each pair
of successive messages sent by the same process. In Section 5 we present two variations that weaken
that synchronization.
4.2 Causal Windows with Limited Width
In this subsection we prove that, the causal window of a PAK causal broadcasting protocol based
on the send condition SC 1 is limited:
Lemma 4.1 Let b
E be a distributed computation and m 1 and
E) be messages such that
protocol based on SC 1 ensures
if there is a causal ordering violation between m 1 and m 2 then
Proof (by contradiction) As shown in Figure 4, suppose there is a causal ordering violation between
two messages m 1 and m 2 sent by P i and P j (i 6= respectively (i.e., bcast(m 1
that is, there exists a message m x sent by P i such
that
From PO(m 1 ), PO(m x ) and the send condition SC 1 (m
dlv(m x ). Due to SC 1 (m Due to
assumption bcast(m x
mx

Figure

4: Proof of Lemma 3.1.
From the previous Lemma and from the definition of the width of a causal window given in
Section 3 we have:
Theorem 4.2 In a PAK causal broadcasting protocol based on SC 1 ,
i of CW j
i is equal to 1 for
any P i and P j .
Proof
i represents the number of consecutive messages m
, sent by process P j
(i.e., bcast(m x
which have not arrived at process
causally precede a message m just arrived at P i (i.e., bcast(m x
would violate causal ordering with each message of the
sequence
. From the Lemma 4.1 if there is a causal ordering violation between m 0
and so the number of consecutive messages, sent by P j , that may violate causal
ordering is at most one. Hence the claim follows. 2
Now, by considering the FIFO property of channels, we have the following Lemma:
Lemma 4.3 Let b
E be a distributed computation and m 2 M( b
E) be a message sent by process P i .
There is at most one message m x 2 M( b
E) concurrent to m for each process P j (i 6= j).
Proof If m and m x are concurrent follows that bcast(m x
From PO(m x ), PO(m) and the channel FIFO property, the following sequence of events occurs
in P j and P i as shown in Figure 5.a:
Suppose there is another message m x 0 sent by P j and concurrent to m. From the send condition
and from the definition of concurrent messages given above we have: bcast(m x 0
(a) (b)
ackm
ackm
mx
ackmx
ackmx

Figure

5: Proof of Lemma 3.3.
shown in Figure 5.b. From FIFO property and PO(m x 0 ),
on process process P j we have: dlv(m) OE j a:ack(m x 0 ), it follows that: bcast(m x
which contradicts the send condition SC 1 (m x at most one message, sent by each distinct
process, can be concurrent to m. 2
From the previous Lemma and the definition of the width of a causal window given in Section
3 we have:
Theorem 4.4 In a PAK causal broadcasting protocol based on SC 1 , CO j
i is equal to 1 for any P i
and P j .
Proof CO 2
i represents the number of consecutive messages m
, sent by process P j
which have been delivered to P i and are concurrent to a message m just arrived at P i . From
Lemma 4.3, there is at most one message m x concurrent to m for each process P j (i 6= j), so
is equal to one and the claim follows. 2
Hence, the range of variation of all the causal windows is limited and the step by which each
vector time counter increases is 1 (due to the FIFO property of channels). So we have the following
invariant:
This allows a modulo k implementation of counters of vector times by choosing k greater than
the maximum difference between any two counters i.e., k - 3. An example of such a window is
shown in Figure 6 with k equal to 4.
A remark on sliding windows. From Figure 6 it can been devised that a causal window is a
particular type of sliding window. The sliding window is a technique widely used for flow-control
in point-to-point data transfer protocols to avoid loss of messages and to ensure FIFO deliveries
message delivered
message delayed

Figure

over asynchronous and unreliable communication systems (e.g., TCP) [11, 17, 23]. This technique
induces a closed loop between sender and receiver which allows not to overload buffer spaces of the
receiver and to avoid network congestion by controlling the transmission rate of the sender. So the
interest of a causal window lies also in the fact that it could be used as a part of a flow-control
layer of a group communication system to provide causal communication to the above layer.
4.3 The Protocol
The behavior of a process P i when executing the PAK protocol is described in Figure 7. When
requesting to broadcast a message m, process P i first waits till a previous broadcast message, if any,
is fully acknowledged (line S1) and then sets the variable processing broadcast to TRUE, stores
the current vector time V T i in V Tm and sends m with attached V Tm as an atomic action (lines
S2-S3). Afterwards, it waits till message m be fully acknowledged (i.e., an ack m message arrives
from each member of P ) and, then, the local timestamp V T i [i] is increased by one module k (line
S5) and finally successive broadcast messages are enabled by resetting processing broadcast (line
S6).
Upon arrival at process P i of message m, its delivery is determined by its delivery condition
ng
In this particular case, CP h
i is equal to one. Message m is delivered as soon as the predicate
DC(m) is true (line R1). When a broadcast message m, sent by P j , is delivered (line R2) to P i ,
the vector time V T i [j] is updated (line R3) and an ack m message is sent to P j (line R4). Lines
up to R4 are executed atomically.
7 Note that (\Gammah) mod and that by definition of causal window k ? h.
init processing broadcast := FALSE; for each h 2
procedure BCAST(m; is the message, P i is the sender %
begin
wait (:processing broadcast); (S1)
processing broadcast := TRUE; V Tm
for each h 2 ng do send (m; V Tm) to P h ; od % event bcast(m) % (S3)
wait (for each h 2 ng do (ack m ) arrives from P h ; od); (S4)
processing broadcast := FALSE; % event f:ack(m) % (S6)
end.
when (m;V Tm) arrives at P i from event arr(m) %
begin
ng
event s:ack(m) % (R4)
end.

Figure

7: The PAK broadcasting protocol based on causal windows
4.4 Correctness Proof
Theorem 4.5 Delivery events respect causal ordering (Safety).
Proof Let us consider two messages m 1 and m 2 sent by processes P i and P j respectively and
delivered to P h out of causal order (i.e., bcast(m 1
Lemma 4.1 we have that line of the protocol, we get: V Tm2
Upon the delivery of m 2 to P h , the delivery condition DC(m 2 ) (line R1) requires one of the
following conditions be true:
1.
[i], that is V Tm 1
2. V Tm2 k, that is V Tm1
By definition and line R2, V T h [i] contains the number of messages sent by P i and delivered
to P h . Successive messages, sent by P i , are delivered in FIFO order by the assumption on FIFO
channels and by the send condition SC 1 .
As m 1 is delivered (by hypothesis) we have either V Tm1
mod k. In both cases, by considering conditions 1 and 2, m 1 has already been delivered; this
contradicts the hypothesis that m 1 was delivered after m 2 . 2
Theorem 4.6 Each message will be eventually delivered (Liveness).
Proof Let m x be the x-th message sent by P i and arrived at P j but never delivered. Given the
delivery condition DC(m x ) of line R1, it follows:
Two cases have to be considered:
From the send condition SC(m upon the arrival of message
m x at process P j , all messages m sent by P i were delivered to P j . So by line
R2, after the delivery of m is equal to x \Gamma 1 which contradicts (P1).
There must be at least one message m, causally preceding m x , sent by P k that either has
not arrived at process P j or is arrived and delayed, so the delivery of m x would violate the
causal ordering. From Lemma 4.1, we have Considering the reliable and broadcast
nature of channels and messages respectively, sooner or later m arrives at P j . Now, two cases
are possible:
8 This part of the proof is similar to the one in [9].
1. m is delivered. This causes, by line R2, the delivery of m x .
2. m is delayed. The same argument can be applied to a message m x 0 , sent by Pw (with
h), such that m x 0 ;m. Due to the finite number of processes and messages,
sooner or later we fall either in case 1 or in the case we have a contradiction.5 Variants of the Protocol
This section shows two variants of the previous protocol. The first one allows a process to have a
certain number of outstanding unacknowledged messages at any time (credit). The second assumes
that only a subset of messages be acknowledged (positive/negative acknowledgement approach).
The aim of both variants is to reduce the number of local synchronizations of the protocol due to
the send condition.
5.1 A PAK Broadcast Protocol using Credits
Here we suppose that processes have a credit of ct - 1, i.e., a process P i can send up to ct - 1
consecutive broadcast messages m before receiving the corresponding acks. So, the send
condition SC 1 can be extended as follows:
ct (m
Credits potentially reduce the number of synchronization in the send condition, but increase
the width of the causal window 9 . Indeed, as shown in Figure 8.a, upon the arrival of a message m
sent by P j , there could be at most ct consecutive messages sent by P k that causally
precede m (bcast(m x ct \Gamma 1g)) and such that dlv(m) OE i dlv(m x ) (with
ct \Gamma 1g). Let us assume m ct be a message sent by P k that causally precedes message m and
that dlv(m) OE i dlv(m ct ). It follows dlv(m ct ), bcast(m ct
and, because of, dlv(m) OE i dlv(m 0 ), we have bcast(m ct ct ), an absurdity. So upon the
arrival of message m at process P i , we have V Tm
ct. In figure 8.a, for clarity's
sake, only the ack messages that produce the fully:ack events are depicted.
9 The local synchronization SC ct only weakens SC1 . In fact the number of local synchronizations is the same. How-
ever, if the credit is appropriately chosen (as a function of the network latency), broadcast of very few messages will
be prohibited because acks will be received before the credit is exhausted. So the number of "real" synchronizations
is actually reduced.
ct
ct
(a) (b)
ct ct

Figure

8: An example of message scheduling of a protocol with credits.
On the other hand, as shown in Figure 8.b, upon the arrival of a message m sent by P j , there can
be at most ct consecutive messages sent by P k and such that bcast(m y
(with y ct \Gamma 1g). Indeed, due to the FIFO property, message m will be delivered to P k
before the arrival at P j of the ack message related to m 0 . So bcast(m) ! bcast(m ct ). Hence, upon
the arrival of message m at process P i , we have
Hence, concerning the width of the causal windows, we have the following invariant:
So a modulo k implementation of vector times with k - 2ct allowed and the size of such
vectors is ndlog bits.
To manage credits the protocol of Figure 7 needs some modification. In particular, to implement
the send condition SC ct , the boolean variable processing broadcast becomes an integer one
(initialized to zero) and lines S1 and S2 should be replaced with the following lines:
wait (processing broadcast ! ct);
processing broadcast := processing broadcast
and lines S6 becomes:
processing broadcast := processing broadcast \Gamma
Finally, for the delivery condition, line R1 will be replaced
ng
ct
ct

Figure

9: Impossibility of a causal violation with more than ct consecutive messages.
A remark on memory requirements. Up to now we have considered the causal window width
as a function of the credit of the sender. Thus, the protocol delays all messages arrived too early
at a process (the maximum number of pending messages is ct(n \Gamma 1)). If the buffer of the receiver
has not enough space, it overflows dropping incoming messages. This situation can be mastered by
associating a credit with the receiver. Let us define for a process P i a width of a causal window
ct (being wt the credit of the receiver) such that 1 - wr - ct. An arriving message m,
whose V Tm [j] fall in the interval [V T will be stored, delayed, delivered and
acknowledged by P i . If its V Tm [j] falls in the interval [V T will be
discarded by P i without sending the ack message. Managing a credit associated with the receiver
requires, then, that each receiver has mechanisms to remove message duplication and each sender
has a timer which triggers retransmission of messages if no ack is received within a deadline. A
discussion about the use of previous mechanisms to support causal windows can be found in [3].
5.2 A PAK/NAK Broadcast Protocol
The protocol of Section 4.3 can be easily adapted for a solution using a PAK/NAK acknowledgment
reducing the number of synchronization among messages due to the send condition compared to
a PAK one. We assume that a process P i can send a sequence of ct messages without being
acknowledged and then an ack message is required from the other processes after the receipt of the
ct-th message sent by P i . A process is allowed to send the ct 1-st message only when the ct-st
message has been fully acknowledged. In this case, the send condition becomes:
if ct
As for the protocol using credits, the width of the causal windows is 2ct. A violation of causal
ordering will be always in the current range of the causal window since a message m sent by P i
can create a causality violation in process P k at most with ct consecutive messages sent by P j . The
acks required by the (i mod ct ct \Gamma 1)-st messages avoid a causality violation including more than
ct consecutive messages. In particular, Figure 9 shows that if a message m, sent by P j , creates a
causality violation in process P k with ct consecutive messages sent by P i then an absurdity follows,
(depicted by thick arrows).
Using the same argument of Section 5.1, no more of ct messages can be concurrent to any
message of the computation due to FIFO property of channels. To implement a PAK/NAK protocol,
the delivery condition is the same as the one of the protocol of Section 5.1 and the protocol of Figure
7 needs the following modifications. Lines S1 and S2 should be replaced with the following ones:
(:processing broadcast);
ct processing broadcast := TRUE;
and line S6 becomes:
processing broadcast := FALSE;
6 Conclusion
In this paper a PAK causal broadcasting protocol based on causal windows have been proposed.
A causal window actually represents the range of variation of vector time counters in the delivery
condition of a causal ordering protocol. This protocol allow a modulo k implementation of vector
times when considering k greater than the width of any causal window. This has been achieved by
exploiting the causal information implicitly carried by ack messages.
Compared with protocols that does not use control messages [5, 9, 18], the cost we pay is a little
computational overhead and the presence of local synchronizations between messages, sent by the
same process, due to the send condition (which reduces the potential concurrency of the protocol).
To reduce the number of local synchronizations, we have discussed two variations of the pro-
tocol. In both variations the reduction of the number of local synchronizations is payed by wider
causal windows. The first variation allows a process to transmit a certain number of successive
messages before receiving the corresponding acknowledgements (credit). This solution only potentially
reduces the number of local synchronizations. However, if the credit is appropriately chosen,
broadcast of very few messages will be prohibited because acks will be received before the credit
is exhausted. At the same time, if the credit is not too high, the difference between sending n
integer as a vector clok and ndlog ke bits as vector clock will be significant. So a proper choice
of a credit value will lead to overhead reduction and insignificant loss of concurrency. The second
variation employs a positive/negative method, i.e., it requires a local synchronizations between
a message m x and the succesive message, sent by the same process, only if x is a multiple of a
predefined parameter. This solution reduces the number of local synchronization and the message
traffic generated by the protocol. Compared to the first variation, this seems to be well suited for
high latencies networks.
In the paper we also showed how the notion of causal window is related to the one of sliding
windows used for FIFO flow control, a local synchronization due to the send condition is strictly
connected to the concept of stability of a message in a group of processes and how this protocol
can be adapted to avoid buffer overflow.
The interested reader can find a causal broadcasting protocol based on causal window well suited
for unreliable network in [3]. The description includes additional data structures and mechanisms,
a process has to endow, in order to avoid lost of messages and message duplications.

Acknowledgments

The author would like to thank Ken Birman, Bruno Ciciani, Roy Friedman, Achour Mostefaoui,
Michel Raynal, Ravi Prakash, Mukesh Singhal and Robbert Van Renesse for comments and many
useful conversations on the work described herein. The author also thanks the anonymous referees
for their detailed comments and suggestions that improved the content of the paper.



--R

"Causal Memory: Definitions, Implementation, and Programming"
"Transis; a Communication Subsystem for High Availability"
"A Positive Acknowledgement Protocol for Causal Broadcasting"
"The Hierarchical Daisy Architecture for Causal Delivery"
"Causal Deliveries of Messages with Real-Time Data in Unreliable Networks"
"Efficient \Delta-causal Broadcasting"
"A Note on Reliable Full-Duplex Transmission Over Half-Duplex Links"
"Reliable Communication in the Presence of Failures"
"Lightweight Causal Order and Atomic Group Multicast"
"Reliable Distributed Computing with the ISIS Toolkit"
"A Protocol for Packet Network Interconnection"
"Logical Time in Distributed Computing Systems"
"A Survey of Light-Weight Protocols for High-Speed Networks"
"Time, Clocks and the Ordering of Events in a Distributed System"
"Virtual Time and Global States of Distributed Systems"
"AnAdaptive Causal Ordering Algorithm Suited to Mobile Computing Environments"
"Networks and Distributed Computation"
"The Causal Ordering Abstraction and a Simple Way to Implement It"
"Securing Causal Relationship in Distributed Systems"
"Logically Instantaneous Message-Passing in Asynchronous Distributed Systems"
"A New Algorithm Implementing Causal Ordering"
"A Data Transfer Protocol"
"Computer Networks"
--TR

--CTR
Roberto Baldoni, Response to Comment on "A Positive Acknowledgment Protocol for Causal Broadcasting", IEEE Transactions on Computers, v.53 n.10, p.1358, October 2004
Giuseppe Anastasi , Alberto Bartoli , Giacomo Giannini, On Causal Broadcasting with Positive Acknowledgments and Bounded-Length Counters, IEEE Transactions on Computers, v.53 n.10, p.1355-1358, October 2004
sliding windows;causal broadcasting;happened-before relation;distributed systems;group communication;asynchrony;vector times