MIS on the fly

Details MIS on the fly MIS on the fly

2011-06-10

arxiv.org/abs/1106.2126v1

Computer Science

Distributed, Parallel, and Cluster Computing

have been submitted for publication

Scientific paper

Humans are very good at optimizing solutions for specific problems. Biological processes, on the other hand, have evolved to handle multiple constrained distributed environments and so they are robust and adaptable. Inspired by observations made in a biological system we have recently presented a simple new randomized distributed MIS algorithm \cite{ZScience}. Here we extend these results by removing a number of strong assumptions that we made, making the algorithms more practical. Specifically we present an $O(\log^2 n)$ rounds synchronous randomized MIS algorithm which uses only 1 bit unary messages (a beeping signal with collision detection), allows for asynchronous wake up, does not assume any knowledge of the network topology, and assumes only a loose bound on the network size. We also present an extension with no collision detection in which the round complexity increases to $(\log^3 n)$. Finally, we show that our algorithm is optimal under some restriction, by presenting a tight lower bound of $\Omega(\log^2 n)$ on the number of rounds required to construct a MIS for a restricted model.

Affiliated with

Also associated with

No associations

Rating

MIS on the fly does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with MIS on the fly, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and MIS on the fly will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-320871