Title :
Some communication complexity issues in asynchronous algorithms
Author :
Tsitsiklis, John N.
Author_Institution :
Dept. of Electr. Eng. & Comput. Sci., MIT, Cambridge, MA, USA
Abstract :
Summary form only given. The author has studied an asynchronous version of the Bellman-Ford algorithm for computing the shortest distances from all nodes in a network to a fixed destination. It is known that this algorithm has (in the worst case) exponential (in the size of the underlying graph) communication complexity. The author has obtained results indicating that its expected (in a probabilistic sense) communication complexity is actually polynomial, under some reasonable probabilistic assumptions. He has shown that a recently introduced method for asynchronous simulation with rollback contains the Bellman-Ford algorithm as a special case, and he has deduced that the rollback method also has exponential communication complexity. The author has also investigated whether (under certain probabilistic assumptions and/or modifications of the simulation algorithm) the communication complexity becomes polynomial
Keywords :
computational complexity; graph theory; parallel algorithms; probability; Bellman-Ford algorithm; asynchronous algorithms; asynchronous simulation; communication complexity; exponential complexity; network; parallel processing; polynomial expected complexity; probability; rollback; Complexity theory; Computational modeling; Computer networks; Concurrent computing; Context; Delay; Distributed computing; Iterative algorithms; Parallel algorithms; Polynomials;
Conference_Titel :
Decision and Control, 1988., Proceedings of the 27th IEEE Conference on
Conference_Location :
Austin, TX
DOI :
10.1109/CDC.1988.194567
