Some communication complexity issues in asynchronous algorithms

Author

Tsitsiklis, John N.

Author_Institution

Dept. of Electr. Eng. & Comput. Sci., MIT, Cambridge, MA, USA

fYear

1988

fDate

7-9 Dec 1988

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;

fLanguage

English

Publisher

ieee

Conference_Titel

Decision and Control, 1988., Proceedings of the 27th IEEE Conference on

Conference_Location

Austin, TX

Type

conf

DOI

10.1109/CDC.1988.194567

Filename

194567