partial ordering of events

[Radha]

Hello all,
I was reading the file "02-Chapter_02.ppt" downloaded from the book's
companion website .
It contains the ppt slides corresponding to chapter 2. In slide #23
I see that the relation "A -> B" ( read as A happens before B or A
precedes B ) is a partial order.

I was reading through a discrete math text book as well as
http://en.wiktionary.org/wiki/partial_order
In both it says that

"A partial order is a relation that is reflexive, antisymmetric and
transitive".

Since A -> A is false , the relation defined by -> is not reflexive.
Since -> is antisymmetric and transitive and not reflexive , I dont
think
-> is a partial order. But the slide#23 and the book "The Art of
multiprocessor programming" says that
relation -> is a partial order.

May be I m missing something here due to my poor math knowledge.
Please clarify.
-
Radhakrishnan

[Joe Bowbeer]

Interesting question you raise.  I'm no set-theory expert either, but I did find some language that is consistent with the statement that happens-before is "a" partial order.

In the following, for example, a distinction is made between "weak" and "strict" partial orders:

 http://www.economicexpert.com/a/Partially:ordered:set.html

Given this distinction, happens-before is of the strict variety:

 http://en.wikipedia.org/wiki/Partially_ordered_set#Strict_and_non-strict_partial_orders

In some contexts, the partial order defined above is called a non-strict (or reflexive, or weak) partial order. In these contexts a strict (or irreflexive) partial order "<" is a binary relation that is irreflexive and transitive, and therefore asymmetric. In other words, asymmetric (hence irreflexive) and transitive.

Joe

[Bartosz Milewski]

My take on this is that we may as well define "happens before" to be
reflexive. I don't think the lack of reflexivity is assumed in any of the
definitions or proofs (correct me if I'm wrong). Strictly speaking then,
"happens before" would have to be renamed to "happens before or is equal",
which is a mouthful.
-Bartosz

[Maurice Herlihy]

Forgot to send this to the group ...

---------- Forwarded message ----------
From: Maurice Herlihy <maurice...@gmail.com>
Date: Fri, Jul 17, 2009 at 9:01 AM
Subject: Re: partial ordering of events
To: trkri...@gmail.com
Cc: nir shavit <sha...@cs.tau.ac.il>


Dear Radhakrishnan,

Some books define "partial order" to be reflexive, some irreflexive. I suppose we should say "irreflexive partial order" to be unambiguous.

  best,

  Maurice

--
Maurice Herlihy
Professor
Computer Science
Brown University

--
Maurice Herlihy
Professor
Computer Science
Brown University

[Radhakrishnan]

The responses were useful and helped my understanding. Thanks for All
who responded.

-Radhakrishnan

On Jul 17, 11:12 pm, Maurice Herlihy <maurice.herl...@gmail.com>
wrote:

> Forgot to send this to the group ...
>
> ---------- Forwarded message ----------
> From: Maurice Herlihy <maurice.herl...@gmail.com>
> Date: Fri, Jul 17, 2009 at 9:01 AM
> Subject: Re: partial ordering of events
> To: trkrish...@gmail.com
>
> Cc: nir shavit <sha...@cs.tau.ac.il>
>
> Dear Radhakrishnan,
> Some books define "partial order" to be reflexive, some irreflexive. I
> suppose we should say "irreflexive partial order" to be unambiguous.
>
>    best,
>   Maurice
>

[jianning]

it should be a strict partial order. In fact, you can think partial
order as ordinary "<=", ">=", except that this relation exist between
only some of the elements in this set (if the relation can be set up
between each two of the elements, then it is a total order).

Partial order in this context reflects the fact that some events can
happen parallel, so there is no happens-before-relationship between
these evens.

P.S. About more information of happens-before, you can refer to some
articles written by SARITA V. ADVE.

On Jul 17, 3:35 pm, Radha <trkrish...@gmail.com> wrote:
> Hello all,
>  I was reading the file "02-Chapter_02.ppt" downloaded from the book's
> companion website .
> It contains the  ppt slides corresponding to chapter 2.  In slide #23
> I see that the relation "A -> B"  ( read as A happens before B or A
> precedes B ) is a partial order.
>

> I was reading through a discrete math text book as well ashttp://en.wiktionary.org/wiki/partial_order

[Sina Momken]

I was reading the book and also noticed that partial order should be reflexive too. Thanks for clarification Prof. Herlihy.