Bruce M. Maggs - Publications

BibTeX entries for publications

Conference Publications

Cutting the Electrical Bill for Internet-Scale Systems. A. Qureshi, R. Weber, H. Balakrishnan, J. Guttag, and B. Maggs, Proceedings of the ACM SIGCOMM 2009 Conference (SIGCOMM), August, 2009.
Holistic Query Transformations for Dynamic Web Applications. A. Manji, C. Garrod, B. M. Maggs, T. C. Mowry, and A. Tomasic. Proceedings of the 2009 IEEE 25th International Conference on Data Engineering (ICDE), April 2009, to appear.
Holistic Application Analysis for Update-Independence. C. Garrod, A. Manji, B. Maggs, T. Mowry, and A. Tomasic. Proceedings of the Second IEEE Workshop on Hot Topics in Web Systems and Technologies (HotWeb), October 2008.
Scalable query result caching for Web applications. C. Garrod, A. Manji, A. Ailamaki, B. Maggs, T. Mowry, C. Olson, and A. Tomasic. Proceedings of the 34th International Conference on Very Large Databases (VLDB), August 2008.
On the impact of route monitor selection. Y. Zhang, Z. Zhang, Z. M. Mao, Y. C. Hu, and B. M. Maggs. IMC '07: Proceedings of the Seventh Internet Measurement Conference (IMC), October 2007.
Portcullis: Protecting Connection Setup from Denial-of-Capability Attacks. B. Parno, D. Wendlandt, E. Shi, A. Perrig, B. Maggs, and Y.-C. Hu. Proceedings of the ACM SIGCOMM 2007 Conference (SIGCOMM), August, 2007.
R-BGP: Staying Connected in a Connected World. N. Kushman, S. Kandula, D. Katabi, and B. M. Maggs. Proceedings of the 4th USENIX Symposium on Networked Systems Design & Implementation (NSDI), April 2007.
Invalidation Clues for Database Scalability Services. A. Manjhi, P. B. Gibbons, A. Ailamaki, B. M. Maggs, T. C. Mowry, C. Olston, A. Tomasic, and H. Yu. Proceedings of the 2007 IEEE 23rd International Conference on Data Engineering (ICDE), April 2007.
Quorum Placement in Networks: Minimizing Network Congestion. D. Golovin, A. Gupta, B. Maggs, F. Oprea, and M. Reiter. Proceedings of the 18th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), July 2006.
Simultaneous Scalability and Security for Data-Intensive Web Applications. A. Manjhi, A. Ailamaki, B. M. Maggs, T. C. Mowry, C. Olston, and A. Tomasic. Proceedings of ACM SIGMOD 2006, June 2006.
Finding effective support-tree preconditioners B. M. Maggs, G. L. Miller, O. Parekh, R. Ravi, and S. L. M. Woo. Proceedings of the 17th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), July 2005.
Quorum Placement in Networks to Minimize Access Delays. A. Gupta, B. Maggs, F. Oprea, and M. Reiter. Proceedings of the 17th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), July 2005.
A Scalability Service for Dynamic Web Applications. C. Olston, A. Manjhi, C. Garrod, A. Ailamaki, B. M. Maggs, and T. C. Mowry, Proceedings of the 2nd Biennial Conference on Innovative Data Systems Research (CIDR), January 2005.
On Hierarchical Routing in Doubling Metrics. H. T-H. Chan, A. Gupta, B. M. Maggs, and S. Zhou, Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2005.
A Methodology for Estimating Interdomain Web Traffic Demand. A. Feldmann, N. Kammenhuber, O. Maennel, B. Maggs, R. De Prisco, and R. Sundaram, Proceedings of the Internet Measurement Conference 2004 (IMC), October 2004.
An Analysis of Live Streaming Workloads on the Internet. K. Sripanidkulchai, B. Maggs, and H. Zhang. Proceedings of the Internet Measurement Conference 2004 (IMC), October 2004.
Availability, Usage, and Deployment Characteristics of the Domain Name System. J. Pang, J. Hendricks, A. Akella, R. De Prisco, B. Maggs, and S. Seshan. Proceedings of the Internet Measurement Conference 2004 (IMC), October 2004.
Simultaneous Source Location. K. Andreev, C. Garrod, B. Maggs, and A. Meyerson. Proceedings of the 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), August, 2004.
Locating Internet Routing Instabilities. A. Feldmann, O. Maennel, Z. Morley Mao, A. Berger, and B. Maggs. Proceedings of the ACM SIGCOMM 2004 Conference (SIGCOMM), August, 2004.
A Comparison of Overlay Routing and Multihoming Route Control, A. Akella, J. Pang, A. Shaikh, B. Maggs, and S. Seshan. Proceedings of the ACM SIGCOMM 2004 Conference (SIGCOMM), August, 2004.
The Feasibility of Supporting Large-Scale Live Streaming Applications with Dynamic Application End-Points. K. Sripanidkulchai, A. Ganjam, B. Maggs, and H. Zhang. Proceedings of the ACM SIGCOMM 2004 Conference (SIGCOMM), August, 2004.
A Measurement-Based Analysis of Multihoming. A. Akella, B. Maggs, S. Seshan, A. Shaikh, and R. Sitaraman, Proceedings of the 2003 ACM SIGCOMM Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication (SIGCOMM), August 2003.
Appeared as On the Performance Benefits of Multihoming Route Control. A. Akella, B. Maggs, S. Seshan, A. Shaikh, and R. Sitaraman, IEEE/ACM Transactions on Networking, Vol. 16, No. 1, February 2008.
Designing Overlay Multicast Networks for Streaming. K. Andreev, B. M. Maggs, A. Meyerson, and R. Sitaraman, Proceedings of the Fifteenth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), June 2003.
Efficient content location using interest-based locality in peer-to-peer systems. K. Sripanidkulchai, B. Maggs, and H. Zhang, Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), April, 2003.

Space-efficient finger search on degree-balanced search trees. G. E. Blelloch, B. M. Maggs, and S. L. M. Woo, Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2003, pp. 374-383.

Tradeoffs between parallelism and fill in nested dissection. C. F. Bornstein, B. M. Maggs, and G. L. Miller, Proceedings of the Eleventh Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), June 1999, pp. 191-200.
Protocols for Asymmetric Communication Channels. M. Adler and B. M. Maggs. Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS), October 1998, pp. 522-533.
Appeared in Journal of Computer and Systems Sciences, Vol. 63, No. 4, December 2001, pp. 573-596.
On Balls and Bins with Deletions. R. Cole, A. Frieze, B. M. Maggs, M. Mitzenmacher, A. W. Richa, R. K. Sitaraman, and E. Upfal, Proceedings of the 2nd International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), October 1998, pp. 145-158.
Randomized protocols for low-congestion circuit routing in multistage interconnection networks. R. Cole, B. M. Maggs, F. Meyer auf der Heide, M. Mitzenmacher, A. W. Richa, K. Schroeder, R. K. Sitaraman, and B. Voecking. Proceedings of the 29th Annual ACM Symposium on the Theory of Computing (STOC), May 1998, pp. 378-388.
On the bisection width and expansion of butterfly networks. C. F. Bornstein, A. Litman, B. M. Maggs, R. K. Sitaraman, and T. Yatzkar. Proceedings of the 12th International Parallel Processing Symposium (IPPS), March 1998, pp. 144-150.
Appeared in Theory of Computing Systems, Vol. 34, No. 6, November 2001, pp. 491-518.
Parallel Gaussian elimination with linear work and fill. C. Bornstein, B. Maggs, G. Miller, and R. Ravi. Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS), October 1997, pp. 274-283.
Exploiting locality for data management in systems of limited bandwidth. B. M. Maggs, F. Meyer auf der Heide, B. Voecking, and M. Westermann. Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS), October 1997, pp. 284-293.
Improved routing and sorting on multibutterflies. B. M. Maggs and B. Voecking. Proceedings of the 29th Annual ACM Symposium on the Theory of Computing (STOC), May 1997, pp. 517-530.
Appeared in Algorithmica, Vol. 28, No. 4, 2000, pp. 438-464.
On the benefit of supporting virtual channels in wormhole routers. R. J. Cole, B. M. Maggs, and R. K. Sitaraman. Proceedings of the 8th ACM Symposium on Parallel Algorithms and Architectures (SPAA), June 1996, pp. 131-141.
Appeared in Journal of Computer and System Sciences, Vol. 62, No. 1, February 2001, pp. 152-177.
Routing on butterfly networks with random faults. R. Cole, B. Maggs, and R. Sitaraman. Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS), October 1995, pp. 558-570.
Tight analyses of two local load balancing algorithms. B. Ghosh, F. T. Leighton, B. M. Maggs, S. Muthukrishnan, C. G. Plaxton, R. Rajaraman, A. W. Richa, R. E. Tarjan, and D. Zuckerman, Proceedings of the 27th Annual ACM Symposium on the Theory of Computing (STOC), May 1995, pp. 548-558.
Appeared in SIAM Journal on Computing, Vol. 29, No. 1, February 1999, pp. 29-64.
Fast algorithms for finding O(congestion+dilation) packet routing schedules. T. Leighton and B. Maggs, Proceedings of the 28th Hawaii International Conference on System Sciences (HICSS), Volume 2, January 1995, pp. 555-563.
Appeared (with minor corrections) as: Fast algorithms for finding O(congestion+dilation) packet routing schedules. F. T. Leighton, B. M. Maggs and A. W. Richa, Combinatorica, Vol. 19, No. 3, 1999, pp. 375-401.
Multi-scale emulation: A technique for reconfiguring arrays with faults. R. Cole, B. Maggs, and R. Sitaraman, Proceedings of the 25th Annual ACM Symposium on the Theory of Computing (STOC), May 1993, pp. 561-572.
Appeared as Reconfiguring arrays with faults part I: worst-case faults, SIAM Journal on Computing, Vol. 26, No.6, December 1997, pp. 1581-1611.
Approximate load balancing on dynamic and asynchronous networks. W. Aiello, B. Awerbuch, B. Maggs, and S. Rao, Proceedings of the 25th Annual ACM Symposium on the Theory of Computing (STOC), May 1993, pp. 632-641.
Sorting-based selection algorithms for hypercubic networks. P. Berthome, A. Ferreira, B. M. Maggs, S. Perennes, and C. G. Plaxton, Proceedings of the 7th International Parallel Processing Symposium (IPPS), April 1993, pp. 89-95.
Appeared in Algorithmica, Vol. 26, No. 2, 2000, pp. 237-254.
On the fault tolerance of some popular bounded-degree networks. T. Leighton, B. Maggs, and R. Sitaraman, Proceedings of the 33rd Annual Symposium on Foundations of Computer Science (FOCS), October 1992, pp. 542-552.
Appeared in SIAM Journal on Computing, Volume 27, Number 5, October 1998, pp. 1303-1333.
Also appeared as A Formal Study on the Fault Tolerance of Parallel and Distributed Systems. C. V. Papadopoulos, Proceedings of the 1st International Conference on Architectures and Algorithms for Parallel Processing (ICAAAPP 95), IEEE, Australia, April 1995.
Simple algorithms for routing on butterfly networks with bounded queues. B. M. Maggs and R. K. Sitaraman, Proceedings of the 24th Annual ACM Symposium on the Theory of Computing (STOC), May 1992, pp. 150-161.
Appeared in SIAM Journal on Computing, Vol. 28, No. 3, June 1999, pp. 984-1003.
A comparison of sorting algorithms for the Connection Machine CM-2 G. E. Blelloch, C. E. Leiserson, B. M. Maggs, C. G. Plaxton, S. Smith, and M. Zagha, Proceedings of the 3rd Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), July 1991, pp. 3-16.
Appeared as An experimental analysis of parallel sorting algorithms, Theory of Computing Systems, Vol. 31, No. 2, March/April 1998, pp. 135-167.
Empirical evaluation of randomly-wired multistage networks. D. Lisinski, T. Leighton, and B. Maggs, Proceedings of the 1990 International Conference on Computer Design (ICCD), September 1990, pp. 380-385.
Fast algorithms for bit-serial routing on a hypercube. B. Aiello, T. Leighton, B. Maggs and M. Newman, Proceedings of the 2nd Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), July 1990, pp. 55-64.
Appeared in Mathematical Systems Theory, Vol. 24, 1991, pp. 253-271.
On-line algorithms for path selection in a nonblocking network. S. Arora, B. M. Maggs and T. Leighton, Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC), May 1990, pp. 149-158.
Appeared in SIAM Journal on Computing, Vol. 25, No. 3, June 1996, pp. 600-625.
Expanders might be practical: fast algorithms for routing around faults on multibutterflies. T. Leighton and B. Maggs, Proceedings of the 30th Annual Symposium on Foundations of Computer Science (FOCS), October 1989, pp. 384-389.
Appeared as Fast algorithms for routing around faults in multibutterflies and randomly-wired splitter networks, IEEE Transactions on Computers, Vol. 41, No. 5, May 1992, pp. 578-587.
Work-preserving emulations of fixed-connection networks. R. Koch, T. Leighton, B. Maggs, S. Rao, and A. Rosenberg, Proceedings of the 21st Annual ACM Symposium on Theory of Computing (STOC), May 1989, pp. 227-240.
Appeared as Work-preserving emulations of fixed-connection networks. R. R. Koch, F. T. Leighton, B. M. Maggs, S. B. Rao, A. L. Rosenberg, and E. J. Schwabe, Journal of the ACM, Vol. 44, No. 1, January 1997, pp. 104-147.
Universal packet routing algorithms. T. Leighton, B. Maggs, and S. Rao, Proceedings of the 29th Annual Symposium on Foundations of Computer Science (FOCS), October 1988, pp. 256-271.
Appeared as Packet routing and job-shop scheduling in O(congestion+dilation) steps, Combinatorica, Vol. 14, No. 2, 1994, pp. 167-180,
and as Randomized routing and sorting on fixed-connection networks. F. T. Leighton, B. M. Maggs, S. B. Rao, and A. G. Ranade, Journal of Algorithms, Vol. 17, No. 1, July 1994, pp. 157-205.
Communication-efficient parallel graph algorithms. C. E. Leiserson and B. M. Maggs, Proceedings of the 1986 International Conference on Parallel Processing (ICPP), August 1986, pp. 861-868.
Appeared as Communication-efficient parallel graph algorithms for distributed random-access machines. Algorithmica, Vol. 3, 1988, pp. 53-77.

Refereed Publications

On the Performance Benefits of Multihoming Route Control. A. Akella, B. Maggs, S. Seshan, A. Shaikh, and R. Sitaraman, IEEE/ACM Transactions on Networking, Vol. 16, No. 1, February 2008.
Globally distributed content delivery. J. Dilley, B. Maggs, J. Parikh, H. Prokop, R. Sitaraman, and B. Weihl, IEEE Internet Computing, September/October 2002, pp. 50-58.
Protocols for Asymmetric Communication Channels. M. Adler and B. M. Maggs, Journal of Computer and Systems Sciences, Vol. 63, No. 4, December 2001, pp. 573-596.
On the bisection width and expansion of butterfly networks. C. F. Bornstein, A. Litman, B. M. Maggs, R. K. Sitaraman, and T. Yatzkar, Theory of Computing Systems Vol. 34, No. 6, November 2001, pp. 491-518.
On the benefit of supporting virtual channels in wormhole routers. R. J. Cole, B. M. Maggs, and R. K. Sitaraman, Journal of Computer and System Sciences, Vol. 62, No. 1, February 2001, pp. 152-177.
Improved routing and sorting on multibutterflies. B. M. Maggs and B. Voecking. Algorithmica, Vol. 28, No. 4, 2000, pp. 438-464.
Sorting-based selection algorithms for hypercubic networks. P. Berthome, A. Ferreira, B. M. Maggs, S. Perennes, and C. G. Plaxton, Algorithmica, Vol. 26, No. 2, 2000, pp. 237-254.
Simple algorithms for routing on butterfly networks with bounded queues. B. M. Maggs and R. K. Sitaraman, SIAM Journal on Computing, Vol. 28, No. 3, June 1999, pp. 984-1003.
Fast algorithms for finding O(congestion+dilation) packet routing schedules. F. T. Leighton, B. M. Maggs and A. W. Richa, Combinatorica, Vol. 19, No. 3, 1999, pp. 375-401.
Tight analyses of two local load balancing algorithms. B. Ghosh, F. T. Leighton, B. M. Maggs, S. Muthukrishnan, C. G. Plaxton, R. Rajaraman, A. W. Richa, R. E. Tarjan, and D. Zuckerman, SIAM Journal on Computing, Vol. 29, No. 1, February 1999, pp. 29-64.
On the fault tolerance of some popular bounded-degree networks. F. T. Leighton, B. M. Maggs, and R. K. Sitaraman, SIAM Journal on Computing, Volume 27, Number 5, October 1998, pp. 1303-1333.
An experimental analysis of parallel sorting algorithms . G. E. Blelloch, C. E. Leiserson, B. M. Maggs, C. G. Plaxton, S. Smith, and M. Zagha, Theory of Computing Systems, Vol. 31, No. 2, March/April 1998, pp. 135-167.
Reconfiguring arrays with faults part I: worst-case faults. R. J. Cole, B. M. Maggs, and R. K. Sitaraman, SIAM Journal on Computing, Vol. 26, No. 6, December, 1997, pp. 1581-1611.
Work-preserving emulations of fixed-connection networks. R. R. Koch, F. T. Leighton, B. M. Maggs, S. B. Rao, A. L. Rosenberg, and E. J. Schwabe, Journal of the ACM, Vol. 44, No. 1, January 1997, pp. 104-147.
On-line algorithms for path selection in a nonblocking network. S. Arora, B. M. Maggs, and F. T. Leighton, SIAM Journal on Computing, Vol. 25, No. 3, June 1996, pp. 600-625.
Randomized routing and sorting on fixed-connection networks. F. T. Leighton, B. M. Maggs, S. B. Rao, and A. G. Ranade, Journal of Algorithms, Vol. 17, No. 1, July 1994, pp. 157-205.
Packet routing and job-shop scheduling in O(congestion+dilation) steps. F. T. Leighton, B. M. Maggs, and S. B. Rao, Combinatorica, Vol. 14, No. 2, 1994, pp. 167-180.
A parallel algorithm for reconfiguring a multibutterfly network with faulty switches. A. V. Goldberg, B. M. Maggs, and S. A. Plotkin, IEEE Transactions on Computers, Vol. 43, No. 3, March 1994, pp. 321-326.
Fast algorithms for routing around faults in multibutterflies and randomly-wired splitter networks. F. T. Leighton and B. M. Maggs, IEEE Transactions on Computers, Vol. 41, No. 5, May 1992, pp. 578-587.
Fast algorithms for bit-serial routing on a hypercube. W. A. Aiello, F. T. Leighton, B. M. Maggs, and M. Newman, Mathematical Systems Theory, Vol. 24, 1991, pp. 253-271.
Communication-efficient parallel algorithms for distributed random-access machines. C. E. Leiserson and B. M. Maggs, Algorithmica, Vol. 3, 1988, pp. 53-77.
Minimum-cost spanning tree as a path-finding problem. B. M. Maggs and S. A. Plotkin, Information Processing Letters, Vol. 26, No. 6, January 1988, pp. 291-293.

Surveys

Real-time emulations of bounded-degree networks. B. M. Maggs and E. J. Schwabe, Information Processing Letters, Vol. 6, No. 5, June 1998, pp. 269-276.
Parallel algorithms. G. E. Blelloch and B. M. Maggs. In M. J. Atallah, editor, Handbook of Algorithms and Theory of Computation CRC Press, Boca Raton, FL, 1998.
Parallel algorithms. G. E. Blelloch and B. M. Maggs. In A. B. Tucker, Jr., editor, The Computer Science and Engineering Handbook, CRC Press, Boca Raton, FL, 1997, pp. 277-315.
A revised version of this chapter (available below) will appear in M. J. Atallah, editor, Handbook of Algorithms and Theory of Computation, CRC Press, Boca Raton, FL, 1998.
Parallel algorithms. G. E. Blelloch and B. M. Maggs. ACM Computing Surveys, Vol. 28, No. 1, March 1996, pp. 51-54.
Models of parallel computation: a survey and synthesis. B. M. Maggs, L. R. Matheson, and R. E. Tarjan, Proceedings of the 28th Hawaii International Conference on System Sciences (HICSS), Vol. 2, January 1995, pp. 61-70.
Randomly wired multistage networks. B. M. Maggs, Statistical Science, Vol. 8, No. 1, February, 1993, pp. 70-75.

Position Papers

A critical look at three of parallel computing's maxims. B. M. Maggs. Proceedings of the 1996 International Symposium on Parallel Architectures, Algorithms, and Networks (I-SPAN '96), June 1996, pp. 1-7.
The hidden cost of low bandwidth communication. G. E. Blelloch, B. M. Maggs, and G. L. Miller. In U. Vishkin, ed., Developing a Computer Science Agenda for High-Performance Computing, ACM press, 1994, pp. 22-25.
Beyond parallel random-access machines. B. M. Maggs. In J. L. C. Sanz, ed., Opportunities and Constraints of Parallel Computing, Springer-Verlag, 1989, pp. 83-84.

Other Manuscripts

Competitive analysis of call admission algorithms that allow delay. A. Feldmann, B. M. Maggs, J. Sgall, D. D. Sleator, and A. Tomkins, Technical Report CMU-CS-95-102, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213, January 1995.