EventRecvTimeLocalTieBrkCmp< EventTy > Struct Template Reference

EventRecvTimeLocalTieBrkCmp is used to compare two events and break ties when the receiving time of two events is the same. More...

#include <Event.h>

List of all members.

Public Member Functions
int	compare (const EventTy &left, const EventTy &right) const
	Compares two events 'left' and 'right' based on getRecvTime().
bool	operator() (const EventTy &left, const EventTy &right) const
	returns true if left > right Since std::priority_queue is a max heap, we use > semantics instead of < in order to get a min heap and thus process events in increasing order of recvTime.

---

Detailed Description

template<typename EventTy>
struct EventRecvTimeLocalTieBrkCmp< EventTy >

EventRecvTimeLocalTieBrkCmp is used to compare two events and break ties when the receiving time of two events is the same.

Ties between events with same recvTime need to be borken consistently, i.e. compare(m,n) and compare (n,m) are consistent with each other during the life of events 'm' and 'n'.

There are at least two reasons for breaking ties between events of same time stamps:

• Chandy-Misra's algorithm requires FIFO communication channels on edges between the stations. i.e. On a given input edge, two events with the same time stamp should not be reordered. Therefore ties must be resolved for events received on the same input i.e. when the sender is the same for two events.

• PriorityQueue's are usually implemented using heaps and trees, which rebalance when an item is removed/added. This means if we add two items 'a' and 'b' with the same priority in the time order (a,b), then depending on what other itmes are added and removed, we may end up removing 'a' and 'b' in the order (b,a), i.e. PriorityQueue may reorder elements of same priority. Therefor, If we break ties between events on same input and not break ties between events on different inputs, this may result in reordering events on the same input.

---

Member Function Documentation

template<typename EventTy >

int EventRecvTimeLocalTieBrkCmp< EventTy >::compare	(	const EventTy &	left,
		const EventTy &	right
	)			const [inline]

Compares two events 'left' and 'right' based on getRecvTime().

if recvTime is same, then we compare the sender (using id), because two events from the same sender should not be reordered. If the sender is the same then we use the id on the event to break the tie, since, sender is guaranteed to assign a unique id to events

Parameters:

	left
	right

Returns:

-1 if left < right. 1 if left > right. Should not return 0 unless left and right are aliases

template<typename EventTy >

bool EventRecvTimeLocalTieBrkCmp< EventTy >::operator()	(	const EventTy &	left,
		const EventTy &	right
	)			const [inline]

returns true if left > right Since std::priority_queue is a max heap, we use > semantics instead of < in order to get a min heap and thus process events in increasing order of recvTime.

---

The documentation for this struct was generated from the following file:

• Event.h