Subject: RE: [manet] How do you justify the assumption of perfect messaging in a distributed protocol?

From: "Mullen, John" <[email-masked]>
Date: Fri, 3 Jun 2005 16:43:03 -0600

Hi Sonny,

All the MANET protocols I'm familiar with anticipate that some packets
will be lost.  What protocols are you referring to? 

John Mullen

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf
Of Sonny Rajagopalan
Sent: Friday, June 03, 2005 12:59 PM
To: [email-masked]
Subject: [manet] How do you justify the assumption of perfect messaging
in a distributed protocol?

Many distributed protocols assume that messaging between nodes in a
MANET is guaranteed -- i.e., so long as the network remains
unpartitioned during the course of the algorithm, the protocol packets
will eventually reach the intended recepient.

<snip>

Cheers,
Sonny.

+-----------
>From the desk of Sonny Rajagopalan,  http://www.cis.udel.edu/~rajagopa
                                                         --------------+

_______________________________________________
manet mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/manet

_______________________________________________
manet mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/manet

---

From: Sonny Rajagopalan <[email-masked]>
Date: Fri, 3 Jun 2005 19:34:10 -0400 (EDT)

> will be lost.  What protocols are you referring to?=20

Yes, I am aware.

How about leader election protocols? Packets may be lost with potentially 
"catastrophic." But then again, how does one designing the leader election 
protocol argue around such a possibility? Once again, I am aware of the 
standard arguments, but this seems like a fundamental issue worth thinking 
about again, yeah?

Cheers,
Sonny.

+-----------
                                                         --------------+

On Fri, 3 Jun 2005, Mullen, John wrote:

> quoted-printable
> MIME-Version: 1.0
> Content-Type: text/plain; charset="us-ascii"
> Content-Transfer-Encoding: quoted-printable
> quoted-printable
>
> Hi Sonny,
>
> will be lost.  What protocols are you referring to?=20
>
> John Mullen
>

---

From: Theodoros Salonidis <[email-masked]>
Date: Fri, 3 Jun 2005 20:19:45 -0400 (EDT)

Sonny,

Operation of various distributed algorithms (from leader election
to routing) under message delays/failures or node failures has been
considered and addressed by the classic algorithmic fault tolerance
literature.

Under certain assumptions, various bounds on performance
can be computed (e.g. what is max number of simultaneously
failing elements that still ensures proper algorithm operation).
Several interesting old and new papers exist on such topics.

Fault-tolerance analysis specific to MANET protocols can use
similar mathematical tools although this is a topic that has
not been systematically explored.

Of course there are limits as to what analysis can provide
with respect to a real life distributed system, be it 
a wired network or a MANET.

Theodoros

--------------------------------------------------
Theodoros Salonidis
Post-doctoral Research Associate

Dept. of Electrical and Computer Engineering
Rice University
2041 Duncan Hall MS-380
Houston, TX 77005

(713) 348-2899
[email-masked]
http://www.ece.rice.edu/~thsalon
---------------------------------------------------------

---

From: Einar Vollset <[email-masked]>
Date: Sat, 4 Jun 2005 16:03:30 +0100

Theodoros,

> considered and addressed by the classic algorithmic fault tolerance

True, but little has been done specifically for ad-hoc networks, and 
it's
probably a fallacy to assume that this work can be directly ported, just
like Internet routing protocols may not work very well in ad-hoc.

> Several interesting old and new papers exist on such topics.

Yes, but the number of failing nodes (or even links) is not what
makes the problem hard. The problem is hard mainly because,
given that failures can occur, you cannot know if a node is slow
(because network is partitioned or whatever) or if the node has
crashed. This is the crux of the classic Fischer,Lynch & Patterson
impossibility from distributed systems theory. A similar result relates
to Halpern et.al.'s ideas of "Common Knowledge" and how the level
of "shared/community" knowledge about certain events a group
  relates to the properties of the communication links between
them.

> with respect to a real life distributed system, be it a wired network 
> or a MANET.

Agreed. I think reliability issues will become more pertinent as MANETs 
mature and
"real-life" group applications become useful.

Cheers,

Einar

----------------------------------------
Einar Vollset
PhD Student
School of Computing Science
University of Newcastle, UK
http://vollset.org
-----------------------------------------