[cs63201] Re: semantics of broadcasting

[Mikhail Nesterenko]

> When a process broadcasts messages to N neighbors (such as the initiator
> in the Polling Wave Algorithm), in the interleaving semantic, is this
> considered N separate events, with a time complexity of N?
>
> Or does a broadcast send get special recognition and can be considered one
> event (the broadcast is one atomic command, and all the separate outgoing
> channels can be enqueued simultaneously)

Assuming the guarded command model, this depends on the atomicity.
Recall that the guarded command is always executed atomically
regardless of the number of individual lines of code in it.  Thus, if
there is a broadcast in the (single) guarded command then it is always
atomic.

	Potentially, a finer atomicity can be considered where
	broadcast is separated in single individual message
	transmissions. That is, the guarded commands guard single
	message transmissions.

	However, We proved that in case of message passing systems, the
        finer atomicity is not necessary as the computation that a
	fine-atomicity program produces are equivalent to the
	computations of a more coarse atomicity program.

thanks,
--
Mikhail