2
$\begingroup$

Consider the following problem to be solved in a distributed context:

Find for each processor the size of the biggest cycle of which it is member.

My algorithm is the following (for synchronous MPS):

procedure findMaxCycleSize
cycle_size := 0
send(my_id, 1) to all my neighbors
for i:=1 to n do
    receive(id, size)
    if id = my_id then
        if size > cycle_size then
            cycle_size := size
        end if
    else
        send to all my neighbors except sender (id, size+1)
    end if
done

Analisys

$n+1$ rounds are enough, in fact a cycle can have size at most $n$, so the time complexity is $\Theta(n)$

Message complexity is very high, $O(n*n^n)$, this because every processor is responsible of at most $n^n$ message. The best case is when every processor has degree exactly $2$ (ring topology) and we would have $O(n^2)$ messages.

The problem is that this algorithm is wrong, suppose the following case,

it will return for $p_1$ 5 but this is not true.

improvement #1 The first message has another field "destination node", so the processor can check if the message comes from the processor to which he initially forwarded the message

procedure findMaxCycleSize
cycle_size := 0
send(my_id, v, 1) to all v neighbors
for i:=1 to n do
    receive(id,v, size)
    if id = my_id then
        if sender_id is not v and size > cycle_size then
            cycle_size := size
        end if
    else
        send to all my neighbors except sender (id,v, size+1)
    end if
done

I have 2 questions:

  • Is my analisys correct?
  • How can I fix the algorithm to improve message complexity?
$\endgroup$
  • $\begingroup$ Is the graph undirected? And what assumptions do we have on the memory of each precessor (ist it linear/sublinear in the number of nldes)? $\endgroup$ – narek Bojikian Jan 12 at 3:38

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.