Simple, efficient asynchronous parallel algorithms for maximization

Albert G. Greenberg; Boris D. Lubachevsky; Andrew M. Odlyzko

doi:10.1145/323596.323625

Simple, efficient asynchronous parallel algorithms for maximization

Albert G. Greenberg, Boris D. Lubachevsky, Andrew M. Odlyzko

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

1 Scopus citations

Abstract

The problem of computing the maximum of n inputs on an asynchronous parallel computer is considered. In general, the inputs may arrive staggered in time, the number of processors available to the maximization algorithm may vary during its execution, and the number of inputs, n, may be initially unknown. Two simple, efficient algorithms to compute the maximum are presented. The algorithms may be invoked asynchronously, as new inputs and processors arrive. Performance measures that account for the response times of the invocations are introduced, and the algorithms are analyzed under these measures.

Original language	English (US)
Title of host publication	Proceedings of the 4th Annual ACM Symposium on Principles of Distributed Computing, PODC 1985
Editors	Ray Strong, Michael Malcolm
Publisher	Association for Computing Machinery
Pages	300-308
Number of pages	9
ISBN (Electronic)	0897911687
DOIs	https://doi.org/10.1145/323596.323625
State	Published - Aug 1 1985
Externally published	Yes
Event	4th Annual ACM Symposium on Principles of Distributed Computing, PODC 1985 - Minaki, Canada Duration: Aug 5 1985 → Aug 7 1985

Publication series

Name	Proceedings of the Annual ACM Symposium on Principles of Distributed Computing

Other

Other	4th Annual ACM Symposium on Principles of Distributed Computing, PODC 1985
Country/Territory	Canada
City	Minaki
Period	8/5/85 → 8/7/85

Publisher link

10.1145/323596.323625

Find It

Find It at U of M Libraries

Cite this

Greenberg, A. G., Lubachevsky, B. D., & Odlyzko, A. M. (1985). Simple, efficient asynchronous parallel algorithms for maximization. In R. Strong, & M. Malcolm (Eds.), Proceedings of the 4th Annual ACM Symposium on Principles of Distributed Computing, PODC 1985 (pp. 300-308). (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing). Association for Computing Machinery. https://doi.org/10.1145/323596.323625

Simple, efficient asynchronous parallel algorithms for maximization. / Greenberg, Albert G.; Lubachevsky, Boris D.; Odlyzko, Andrew M.

Proceedings of the 4th Annual ACM Symposium on Principles of Distributed Computing, PODC 1985. ed. / Ray Strong; Michael Malcolm. Association for Computing Machinery, 1985. p. 300-308 (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Greenberg, AG, Lubachevsky, BD & Odlyzko, AM 1985, Simple, efficient asynchronous parallel algorithms for maximization. in R Strong & M Malcolm (eds), Proceedings of the 4th Annual ACM Symposium on Principles of Distributed Computing, PODC 1985. Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, pp. 300-308, 4th Annual ACM Symposium on Principles of Distributed Computing, PODC 1985, Minaki, Canada, 8/5/85. https://doi.org/10.1145/323596.323625

Greenberg AG, Lubachevsky BD, Odlyzko AM. Simple, efficient asynchronous parallel algorithms for maximization. In Strong R, Malcolm M, editors, Proceedings of the 4th Annual ACM Symposium on Principles of Distributed Computing, PODC 1985. Association for Computing Machinery. 1985. p. 300-308. (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing). doi: 10.1145/323596.323625

Greenberg, Albert G. ; Lubachevsky, Boris D. ; Odlyzko, Andrew M. / Simple, efficient asynchronous parallel algorithms for maximization. Proceedings of the 4th Annual ACM Symposium on Principles of Distributed Computing, PODC 1985. editor / Ray Strong ; Michael Malcolm. Association for Computing Machinery, 1985. pp. 300-308 (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing).

@inproceedings{2aa50887ad5f49afbc3a0a2f7fde1c8f,

title = "Simple, efficient asynchronous parallel algorithms for maximization",

abstract = "The problem of computing the maximum of n inputs on an asynchronous parallel computer is considered. In general, the inputs may arrive staggered in time, the number of processors available to the maximization algorithm may vary during its execution, and the number of inputs, n, may be initially unknown. Two simple, efficient algorithms to compute the maximum are presented. The algorithms may be invoked asynchronously, as new inputs and processors arrive. Performance measures that account for the response times of the invocations are introduced, and the algorithms are analyzed under these measures.",

author = "Greenberg, {Albert G.} and Lubachevsky, {Boris D.} and Odlyzko, {Andrew M.}",

year = "1985",

month = aug,

day = "1",

doi = "10.1145/323596.323625",

language = "English (US)",

series = "Proceedings of the Annual ACM Symposium on Principles of Distributed Computing",

publisher = "Association for Computing Machinery",

pages = "300--308",

editor = "Ray Strong and Michael Malcolm",

booktitle = "Proceedings of the 4th Annual ACM Symposium on Principles of Distributed Computing, PODC 1985",

note = "4th Annual ACM Symposium on Principles of Distributed Computing, PODC 1985 ; Conference date: 05-08-1985 Through 07-08-1985",

}

TY - GEN

T1 - Simple, efficient asynchronous parallel algorithms for maximization

AU - Greenberg, Albert G.

AU - Lubachevsky, Boris D.

AU - Odlyzko, Andrew M.

PY - 1985/8/1

Y1 - 1985/8/1

N2 - The problem of computing the maximum of n inputs on an asynchronous parallel computer is considered. In general, the inputs may arrive staggered in time, the number of processors available to the maximization algorithm may vary during its execution, and the number of inputs, n, may be initially unknown. Two simple, efficient algorithms to compute the maximum are presented. The algorithms may be invoked asynchronously, as new inputs and processors arrive. Performance measures that account for the response times of the invocations are introduced, and the algorithms are analyzed under these measures.

AB - The problem of computing the maximum of n inputs on an asynchronous parallel computer is considered. In general, the inputs may arrive staggered in time, the number of processors available to the maximization algorithm may vary during its execution, and the number of inputs, n, may be initially unknown. Two simple, efficient algorithms to compute the maximum are presented. The algorithms may be invoked asynchronously, as new inputs and processors arrive. Performance measures that account for the response times of the invocations are introduced, and the algorithms are analyzed under these measures.

UR - http://www.scopus.com/inward/record.url?scp=85034785447&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85034785447&partnerID=8YFLogxK

U2 - 10.1145/323596.323625

DO - 10.1145/323596.323625

M3 - Conference contribution

AN - SCOPUS:85034785447

T3 - Proceedings of the Annual ACM Symposium on Principles of Distributed Computing

SP - 300

EP - 308

BT - Proceedings of the 4th Annual ACM Symposium on Principles of Distributed Computing, PODC 1985

A2 - Strong, Ray

A2 - Malcolm, Michael

PB - Association for Computing Machinery

T2 - 4th Annual ACM Symposium on Principles of Distributed Computing, PODC 1985

Y2 - 5 August 1985 through 7 August 1985

ER -

Simple, efficient asynchronous parallel algorithms for maximization

Abstract

Publication series

Other

Publisher link

Find It

Other files and links

Fingerprint

Cite this