Find the size of the maximum cycle in a MPS

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
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
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?
• 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)? – narek Bojikian Jan 12 at 3:38