Let us consider an asynchronous system model stronger than CAMPn,t[∅], namely no process
crashes (i.e., t = 0) and the processes can access a global clock CLOCK. Each application
message m has a lifetime defined as the physical time duration during which, after m has been
broadcast, its content is meaningful and can consequently be used by its destination processes.
A message that arrives at its destination process after its lifetime has elapsed becomes useless
and must be discarded (for the destination process, it is as if the message has been lost). A
message that arrives at a destination process before its lifetime has elapsed must be delivered by
the expiration of its lifetime.
It is assumed that all the messages have the same lifetime denoted λ. Let τ be the sending time
of a message m. The physical date τ + λ is consequently the deadline after which the message
m is useless for the processes that have not yet received it. This is illustrated in Fig. 2.16. If m
arrives by its deadline at pi, it must be processed by its deadline by pi. Alternatively, if m arrives
after its deadline at pj it must be discarded by pj . (In practice, a great percentage of messages
arrive by their deadlines, as is usually the case in distributed multimedia applications.)
Design an algorithm implementing a CO-URB-broadcast abstraction defined by the following
properties:
• Validity. If a process co-delivers a message m, then m was previously co-broadcast.
• Integrity. A process co-delivers a message m at most once.
• CO-delivery. For any pair of messages m and m such that m →M m
, which arrive at a
process pi by their deadlines, pi co-delivers m before m
.
• Expiry constraint. No message can be co-delivered by a process after its deadline.
• Termination. Any message that arrives by its deadline at a process pi is co-delivered by pi.
Solutions in [49]. (This message causality-related broadcast problem was introduced in [50].)