In distributed algorithms, The Max Flood algorithms finds the leader in a network of processes In O(diam) time and with |E|*diam (|E| is the number of edges in the graph) message complexity. With some optimization in the algorithm we can reduce these message complexity. We can improve the algorithm by each process sending the max UID's only when a changed occurs(the process finds a new max UID).
My problem is The no one has mentioned the complexity bounds of these improvement. How ever I faced these problem in Nancy Lynches Distributed Algorithms book:

>     3. For the OptFloodMax algorithm, either prove a smaller upper bound than
>     O (n^3) on the number of messages or exhibit a class of digraphs and cot-
>     responding UID assignments in which the number of messages is omega(n^3)

After lots of searching in the internet and the books I couldn't find any answer to help me. I couldn't. Where does the n^3 bounds come from and which bound is the correct one?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.