Advertisement
Published in:
2006 | OriginalPaper | Chapter
On the Complexity of the “Most General” Firing Squad Synchronization Problem
Authors : Darin Goldstein, Kojiro Kobayashi
Published in: STACS 2006
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We show that if a minimal-time solution exists for a fundamental distributed computation primitive, synchronizing a general directed network of finite-state processors, then there must exist an extraordinarily fast
$O(ED log_2 D (log_2 n)^2)$
algorithm in the RAM model of computation for exactly determining the diameter of a general directed graph. The proof is constructive.
This result interconnects two very distinct areas of computer science: distributed protocols on networks of intercommunicating finite-state machines and standard algorithms on the usual RAM model of computation.