{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,27]],"date-time":"2025-01-27T05:30:23Z","timestamp":1737955823282,"version":"3.33.0"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2008,1,31]],"date-time":"2008-01-31T00:00:00Z","timestamp":1201737600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2009,8]]},"DOI":"10.1007\/s00224-008-9102-5","type":"journal-article","created":{"date-parts":[[2008,1,30]],"date-time":"2008-01-30T18:30:40Z","timestamp":1201717840000},"page":"280-301","source":"Crossref","is-referenced-by-count":1,"title":["On the Price of Heterogeneity in Parallel Systems"],"prefix":"10.1007","volume":"45","author":[{"given":"P. Brighten","family":"Godfrey","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Richard M.","family":"Karp","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2008,1,31]]},"reference":[{"key":"9102_CR1","unstructured":"Planetlab: http:\/\/www.planet-lab.org\/"},{"key":"9102_CR2","unstructured":"Almeida, V.A.F., Vasconcelos, I.M.M., \u00c1rabe, J.N.C., Menasc\u00e9, D.A.: Using random task graphs to investigave the potential benefits of heterogeneity in parallel systems. In: Proc. ACM\/IEEE Conference on Supercomputing (1992)"},{"key":"9102_CR3","unstructured":"Almeida, V., Menasc\u00e9, D.: Cost-performance analysis of heterogeneity in supercomputer architectures. In: Proc. ACM\/IEEE Conference on Supercomputing (1990)"},{"key":"9102_CR4","doi-asserted-by":"crossref","unstructured":"Chawathe, Y., Ratnasamy, S., Breslau, L., Lanham, N., Shenker, S.: Making Gnutella-like P2P systems scalable. In: Proceedings of ACM SIGCOMM (2003)","DOI":"10.1145\/863955.864000"},{"key":"9102_CR5","unstructured":"Chudak, F.A., Shmoys, D.B.: Approximation algorithms for precedence-constrained scheduling problems on parallel machines that run at different speeds. In: Proc. 8th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 581\u2013590 (1997)"},{"key":"9102_CR6","unstructured":"Comellas, F., Delorme, C.: The (degree, diameter) problem for graphs: http:\/\/www-mat.upc.es\/grup_de_grafs\/grafs\/taula_delta_d.html"},{"key":"9102_CR7","doi-asserted-by":"crossref","unstructured":"Foster, I., Iamnitchi, A.: On death, taxes, and the convergence of peer-to-peer and grid computing. In: Proc. IPTPS (2002)","DOI":"10.1007\/978-3-540-45172-3_11"},{"key":"9102_CR8","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)"},{"key":"9102_CR9","unstructured":"Godfrey, B., Lakshminarayanan, K., Surana, S., Karp, R., Stoica, I.: Load balancing in dynamic structured P2P systems. In: Proc. IEEE INFOCOM, Hong Kong (2004)"},{"key":"9102_CR10","unstructured":"Brighten, P.G., Stoica, I.: Heterogeneity and load balance in distributed hash tables. In: Proc. IEEE INFOCOM (2005)"},{"key":"9102_CR11","doi-asserted-by":"crossref","first-page":"1563","DOI":"10.1002\/j.1538-7305.1966.tb01709.x","volume":"45","author":"R.L. Graham","year":"1966","unstructured":"Graham, R.L.: Bounds on multiprocessing timing anomalies. Bell Syst. Tech. J. 45, 1563\u20131581 (1966)","journal-title":"Bell Syst. Tech. J."},{"key":"9102_CR12","doi-asserted-by":"crossref","unstructured":"Koutsoupias, E.: Coordination mechanisms for congestion games. In: Sigact News, December 2004","DOI":"10.1007\/978-3-540-28629-5_10"},{"key":"9102_CR13","doi-asserted-by":"crossref","unstructured":"Ledlie, J., Seltzer, M.: Distributed, secure load balancing with skew, heterogeneity, and churn. In: Proc. INFOCOM (2005)","DOI":"10.1109\/INFCOM.2005.1498366"},{"key":"9102_CR14","doi-asserted-by":"crossref","unstructured":"Lowney, G.: Invited talk: Why intel is designing multi-core processors. In: Proc. SPAA (2006)","DOI":"10.1145\/1148109.1148126"},{"key":"9102_CR15","volume-title":"Inequalities: Theory of Majorization and its Applications","author":"A.W. Marshall","year":"1979","unstructured":"Marshall, A.W., Olkin, I.: Inequalities: Theory of Majorization and its Applications. Academic Press, New York (1979)"},{"key":"9102_CR16","doi-asserted-by":"crossref","unstructured":"Moreno, J.H.: Invited talk: Chip-level integration: The new frontier for microprocessor architecture. In: Proc. SPAA (2006)","DOI":"10.1145\/1148109.1148165"},{"key":"9102_CR17","unstructured":"Park, K., Pai, V.: Comon: A monitoring infrastructure for PlanetLab. http:\/\/comon.cs.princeton.edu\/"},{"key":"9102_CR18","doi-asserted-by":"crossref","unstructured":"Ratnasamy, S., Shenker, S., Stoica, I.: Routing algorithms for DHTs: Some open questions. In: Proc. IPTPS (2002)","DOI":"10.1007\/3-540-45748-8_4"},{"key":"9102_CR19","doi-asserted-by":"crossref","unstructured":"Saroiu, S., Krishna Gummadi, P., Gribble, S.D.: A measurement study of peer-to-peer file sharing systems. In: Proc. MMCN, San Jose, CA, USA, January 2002","DOI":"10.1117\/12.449977"},{"key":"9102_CR20","doi-asserted-by":"crossref","first-page":"708","DOI":"10.1287\/opre.18.4.708","volume":"18","author":"S. Stidham","year":"1970","unstructured":"Stidham, S.: On the optimality of single-server queueing systems. Oper. Res. 18, 708\u2013732 (1970)","journal-title":"Oper. Res."},{"key":"9102_CR21","doi-asserted-by":"crossref","unstructured":"Suri, S., T\u00f3th, C.D., Zhou, Y.: Selfish load balancing and atomic congestion games. In: Proc. SPAA (2004)","DOI":"10.1145\/1007912.1007941"},{"issue":"12","key":"9102_CR22","doi-asserted-by":"crossref","first-page":"1253","DOI":"10.1016\/j.peva.2005.12.004","volume":"63","author":"A. Wierman","year":"2006","unstructured":"Wierman, A., Osogami, T., Harchol-Balter, M., Scheller-Wolf, A.: How many servers are best in a dual-priority FCFS system? Perform. Eval. 63(12), 1253\u20131272 (2006)","journal-title":"Perform. Eval."},{"key":"9102_CR23","unstructured":"Yang, X., de Veciana, G.: Service capacity of peer to peer networks. In: Proc. INFOCOM (2004)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-008-9102-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-008-9102-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-008-9102-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,26]],"date-time":"2025-01-26T12:59:18Z","timestamp":1737896358000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-008-9102-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,1,31]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2009,8]]}},"alternative-id":["9102"],"URL":"https:\/\/doi.org\/10.1007\/s00224-008-9102-5","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2008,1,31]]}}}