Publications

Conference

 

1.      Gokarna Sharma and Costas Busch.

On the Performance of Window-Based Contention Managers for Transactional Memory.

Proceedings of the 13th Workshop on Advances in Parallel and Distributed Computational Models (APDCM), Anchorage, Alaska, May 2011.

 

2.      Srivathsan Srinivasagopalan, Costas Busch and Sitharama Iyengar.

Oblivious Buy-at-Bulk in Planar Graphs.

Proceedings of the Workshop on Algorithms and Computation (WALCOM), New Delhi, India, February 2011.

 

3.      Costas Busch and Malik Magdon-Ismail.

Optimal Oblivious Routing in Hole-Free Networks. [slides]

Proceedings of the 7th International Conference on Heterogeneous Networking for Quality, Reliability, Security, and Robustness (QShine), Houston, Texas, November 2010. (Invited Paper.)

 

4.      Gokarna Sharma and Costas Busch.

A Competitive Analysis for Balanced Transactional Memory Workloads. [slides]

Proceedings the 14th International Conference on Principles of Distributed Systems (OPODIS), Springer LNCS 6490, pp. 348-363, Tozeur, Tunisia, December 2010.

 

5.      Gokarna Sharma and Costas Busch.

Improving the Competitive Ratios of Transactional Memory Contention Managers. [slides]

2nd Workshop on the Theory of Transactional Memory (WTTM), Boston Massachusetts, September 2010. (Online Abstract.)

 

6.      Gokarna Sharma, Brett Estrade, and Costas Busch.

Window-Based Greedy Contention Management for Transactional Memory. [slides]

Proceedings of the 24 International Symposium on Distributed Computing (DISC), Springer LNCS 6343, pp. 64-78, Boston, Massachusetts, September 2010.

 

7.      Rajgopal Kannan and Costas Busch.

Bottleneck Congestion Games with Logarithmic Price of Anarchy.

Proceedings of the 3rd International Symposium on Algorithmic Game Theory (SAGT), Springer LNCS 6386, pp. 222-233, Athens, Greece, August 2010.

 

8.      Srivathsan Srinivasagopalan, Costas Busch and Sitharama Iyengar.

Universal Data Aggregation Trees for Sensor Networks in Low Doubling Metrics.

Proceedings of the 5th International Workshop on Algorithmic Aspects of Wireless Sensor Networks (ALGOSENSORS), July 2009. (Brief Announcement.)

 

9.      Rajgopal Kannan, Shuangqing Wei, Costas Busch and Athanasios V. Vasilakos.

Online Algorithms for Maximizing Quality of Link Transmissions over a Jammed Wireless Channel.

Proceedings of the IEEE Percom 2009 - Information Quality and Quality of Service Workshop (IQ2S), March 2009.

 

10.   Costas Busch, Rajgopal Kannan, Athanasios V. Vasilakos.
Quality of Routing Congestion Games in Wireless Sensor Networks. [slides]
Proceedings of the 4th International Wireless Internet Conference (WICON), Maui, Hawaii, November 2008. (Invited Paper.)

 

11.   Fikret Sivrikaya, Costas Busch, Malik Magdon-Ismail, Bulent Yener.
ASAND: Asynchronous Slot Assignment and Neighbor Discovery Protocol for Wireless Networks.
OPNETWORK’07, Washington DC, August 2007.

 

12.   Costas Busch, Ryan LaFortune, Srikanta Tirthapura.
Improved Sparse Covers for Graphs Excluding a Fixed Minor.
Proceedings of the 26th annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 61-70, Portland, Oregon, August 2007.

 

13.   Costas Busch, Srikanta Tirthapura.

A Deterministic Algorithm for Summarizing Asynchronous Streams over a Sliding Window. [slides]
Proceedings of the 24th International Symposium on Theoretical Aspects of Computer Science (STACS), LNCS 4393, pp. 465-476, Aachen, Germany, February 2007.

 

14.   Srikanta Tirthapura, Bojan Xu, Costas Busch.
Sketching Asynchronous Streams Over a Sliding Window. [slides]
Proceedings  of the 25th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 82-91, Denver, Colorado, July 2006.

 

15.   Costas Busch, Malik Magdon-Ismail.
Atomic Routing Games on Maximum Congestion. [slides]
Proceedings of the 2nd International Conference on Algorithmic Aspects in Information and Management (AAIM), pp. 79-91, Hong Kong, China, June 2006.

 

16.   Srikanta Tirthapura, Costas Busch.
Concurrent Counting is Harder than Queuing. [slides]
Proceedings of the 20th IEEE International Parallel and Distributed Processing Symposium (IPDPS), Rhodes Island, Greece, April 2006.

 

17.   Nabhendra Bisnik, Alhousein Abouzeid, Costas Busch.
Load Balanced Link Reversal Routing in Mobile Wireless Ad Hoc Networks. [slides]
Proceedings of the 4th Asian International Mobile Computing Conference (AMOC), pp. 41-50, Kolkata, India, January 2006.

 

18.   Costas Busch, Marios Mavronicolas, Paul Spirakis.
Monotone Operations and Monotone Groups.
Proceedings of the 1st International Conference on Algebraic Informatics, pp. 175-195, Aristotle University of Thessaloniki, Greece, October 2005.

 

19.   Costas Busch, Shailesh Kelkar, Malik Magdon-Ismail.
Efficient Bufferless Routing on Leveled Networks. [slides]
Proceedings of the 11th International Conference on Parallel and Distributed Computing  (EUROPAR),  Springer LNCS 3648, pp. 931-940, Lisboa, Portugal, Augoust-September 2005.

 

20.   Costas Busch, Malik-Magdon Ismail, Jing Xi.
Oblivious Routing on Geometric Networks. [slides]
Proceedings of the 17th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 316-324, Las Vegas, Nevada, July 2005.

 

21.   Costas Busch, Malik Magdon-Ismail, Jing Xi.
Optimal Oblivious Path Selection on the Mesh. [slides]
Proceedings of the 19th IEEE International Parallel & Distributed Processing Symposium (IPDPS), pp. 82-91, Denver, Colorado, April 2005.

 

22.   Costas Busch, Malik Magdon-Ismail, Fikret Sinrikaya, Bülent Yener.
Contention-Free MAC Protocols for Wireless Sensor Networks. [slides]
Proceedings of the 18th Annual Conference on Distributed Computing (DISC), Springer LNCS 3704, pp. 245-259, Trippenhuis, Amsterdam, the Netherlands, October 2004.

 

23.   Costas Busch, Malik Magdon-Ismail, Marios Mavronicolas.
Universal Bufferless Routing. [slides]
Proceedings of the 2nd Workshop on Approximation and Online Algorithms (WAOA), Springer LNCS 3351, pp. 239-252, Bergen, Norway, September 2004.

 

24.   Costas Busch, Malik Magdon-Ismail, Marios Mavronicolas, Paul Spirakis.
Direct Routing: Algorithms and Complexity. [slides]
Proceedings of the 12th Annual European Symposium on Algorithms (ESA), Springer LNCS 3221, pp 134-145, Bergen, Norway, September 2004.

 

25.   Costas Busch, Malik Magdon-Ismail, Marios Mavronicolas, Roger Wattenhofer.
Near-Optimal Hot-Potato Routing on Trees. [slides]
Proceedings of the 10th International Conference on Parallel and Distributed Computing (EUROPAR), Springer LNCS 3149, pp. 820-827, Pisa, Italy, August-September 2004.

 

26.   Costas Busch, Marios Mavronicolas, Paul Spirakis.
The Cost of Concurrent, Low-Contention Read-Modify-Write.
Proceedings of the 10th Colloquium on Structural Information and Communication Complexity (SIROCCO), pp. 57-72, Umeå, Sweden, June 2003.

 

27.   Costas Busch, Srikanth Surapaneni, Srikanta Tirthapura.
Analysis of Link Reversal Routing Algorithms for Mobile Ad Hoc Networks. [slides]
Proceedings of the 15th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 210-219, San Diego, California, June 2003.

 

28.   Malik Magdon-Ismail, Costas Busch, Mukkai S. Krishnamoorthy.
Cake-Cutting is Not a Piece of Cake. [slides]
Proceedings of the 20th International Symposium on Theoretical Aspects of Computer Science (STACS), Springer LNCS 2607, pp. 596-607, Berlin, Germany, February-March 2003.

 

29.   Costas Busch.
Õ(Congestion+Dilation) Hot-Potato  Routing on Leveled Networks. [slides]
Proceedings of the 14th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 20-29, Winnipeg, Manitoba, Canada, August 2002.

 

30.   Costas Busch, Maurice Herlihy, Roger Wattenhofer.
Routing without Flow Control. [slides]
Proceedings of the 13th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 11-20, Hersonissos, Greece, July 2001.

 

31.   Costas Busch, Neophytos Demetriou, Maurice Herlihy, Marios Mavronicolas.
A Combinatorial Characterization of Properties Preserved by Antitokens.
Proceedings of the 6th International Conference on Parallel Processing (EUROPAR), Springer LNCS 1900, pp. 575--582, Munich, Germany, August/September 2000.

 

32.   Costas Busch, Maurice Herlihy, Roger Wattenhofer.
Hard-Potato Routing. [slides]
Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (STOC), pp. 278-285, Portland, Oregon, May 2000.

 

33.   Costas Busch, Maurice Herlihy, Roger Wattenhofer.
Randomized Greedy Hot-Potato Routing. [slides]
Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 458-466, San Francisco, California, January 2000.

 

34.   Costas Busch, Neophytos Demetriou, Maurice Herlihy, Marios Mavronicolas.
Threshold Counters with Increments and Decrements.
Proceedings of the 6th International Colloquium on Structural Information and Communication Complexity (SIROCCO), pp. 47-61, Lacanau, France,July 1999.

 

35.   Costas Busch, Maurice Herlihy.
Sorting and Counting Networks of Small Depth and Arbitrary Width.
Proceedings of the 11th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 64-73, Saint-Malo, France, June 1999.

 

36.   William Aiello, Costas Busch, Maurice Herlihy, Marios Mavronicolas, Nir Shavit, Dan Touitou.
Supporting Increment and Decrement Operations in Balancing Networks. [slides]
Proceedings of the 16th International Symposium on Theoretical Aspects of Computer Science (STACS), pp. 377-386, Trier, Germany, March 1999.

 

37.   Costas Busch, Marios Mavronicolas.
An Efficient Counting Network. [slides]
Proceedings of the 1st Merged International Parallel Processing Symposium and Symposium on Parallel and Distributed Processing (IPPS/SPDP), pp. 380-384, Orlando, Florida, March/April 1998.

 

38.   Costas Busch, Maurice Herlihy.
A Survey on Counting Networks.
Proceedings of the Workshop on Distributed Data and Structures (WDAS), pp 13-20, Orlando, Florida, March 30, 1998. (Invited Paper.)

 

39.   Costas Busch, Marios Mavronicolas.
The Strength of Counting Networks.
Proceedings of the 15th Annual ACM Symposium on Principles of Distributed Computing (PODC) p. 311, Philadelphia, Pennsylvania, May 1996. (Brief Announcement.)

 

40.   Costas Busch, Marios Mavronicolas.
A Logarithmic Depth Counting Networks.
Proceedings of the 14th Annual ACM Symposium on Principles of Distributed Computing (PODC), p. 274, Ottawa, Ontario, Canada, August 1995. (Brief Announcement.)

 

41.   Costas Busch, Marios Mavronicolas.
A Combinatorial Treatment of Balancing Networks.
Proceedings of the 13th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 206-215, Los Angeles, California, August 1994.

 

42.   Costas Busch, Nikos Hardavellas, Marios Mavronicolas.
Contention in Counting Networks.
Proceedings of the 13th Annual ACM Symposium on Principles of Distributed Computing (PODC), p. 404, Los Angeles, California, August 1994. (Brief Announcement.)

Journal

 

1.      Costas Busch and Srikanta Tirthapura.

Concurrent Counting is Harder than Queuing.

Theoretical Computer Science, Vol. 411, No. 43, pp. 3823-3833, October 2010.

 

2.      Costas Busch and Marios Mavronicolas.

An Efficient Counting Network.

Theoretical Computer Science, Vol. 411, No. 34-36, pp. 3001-3030, July 2010.

 

3.      Costas Busch and Malik Magdon-Ismail.

Atomic Routing Games on Maximum Congestion.

Theoretical Computer Science, Vol. 410, No. 36, pp. 3337-3975, August 2009.

 

4.      Costas Busch, Malik Magdon-Ismail, Fikret Sivrikaya, Bulent Yener.
Contention-free MAC Protocols for Asynchronous Wireless Sensor Networks.
Distributed Computing, Vol. 21, No. 1, pp. 23-42, June 2008.

5.      Costas Busch, Malik Magdon-Ismail, Jing Xi.
Optimal Oblivious Path Selection on the Mesh.
IEEE Transactions on Computers, Vol. 57, No. 5, pp. 660-671, May 2008.

6.      Bojan Xu, Srikanta Tirthapura, Costas Busch.
Sketching Asynchronous Data Streams over Sliding Windows.
Distributed Computing, Vol. 20, No. 5, pp. 359-374, February 2008.

7.      Costas Busch, Magdon-Ismail, Marios Mavronicolas.
Efficient Bufferless Packet Switching on Trees and Leveled Networks.
Journal on Parallel and Distributed Computing, Vol. 67, No. 11, pp. 1168-1186, November 2007.

8.      Costas Busch, Malik Magdon-Ismail, Marios Mavronicolas.
Universal Bufferless Packet Switching.
Siam Journal on Computing, Vol. 37, No. 4, pp. 1139-1162, November 2007.

9.      James Aspnes, Costas Busch, Shlomi Dolev, Panagiota Fatourou, Chryssis Georgiou, Alex Shvartsman, Paul Spirakis, Roger Wattenhofer. 
Eight Open problems in Distributed Computing.
Bulletin of the European Association for Theoretical Computer Science, No. 90, pp. 109-126, October 2006. (Invited Paper.)

10.   Costas Busch, Malik Magdon Ismail, Marios Mavronicolas, Paul Spirakis.
Direct Routing: Algorithms and Complexity.
Algorithmica, Vol. 45, No. 1, pp. 45-68, June 2006.
(Special issue with invited papers from ESA 2004.)

11.   Costas Busch, Srikanta Tirthapura.
Analysis of Link Reversal Routing Algorithms.
Siam Journal on Computing, Vol. 35, No. 2, pp. 305-326, October 2005.

12.   Costas Busch, Mukkai S. Krishnamoorthy, Malik Magdon-Ismail.
Hardness Results for Cake Cutting.
Bulletin of the European Association for Theoretical Computer Science, No. 86, pp. 85-106, June 2005.

13.   Costas Busch, Marios Mavronicolas, Paul Spirakis.
The Cost of Concurrent, Low-Contention Read&Modify&Write.
Theoretical Computer Science, Vol. 333, No. 3, pp. 373-400, March 2005.
(Special issue with invited papers from SIROCCO 2003.)
(Abstract also published in Computer & Information Systems Abstracts from CSA, September 2006.)

14.   Costas Busch, Marios Mavronicolas, Paul Spirakis.
An Application of the Monotone Linearizability Lemma.
Bulletin of the European Association for Theoretical Computer Science, No. 85, pp. 70-80, February 2005.

15.   Costas Busch.
Õ(Congestion + Dilation) Hot-Potato Routing on Leveled Networks.
Theory of Computing Systems, Vol 37, No. 3, pp. 371-396, May 2004.
(Special issue with invited papers from SPAA 2002.)

16.   Costas Busch, Maurice Herlihy.
Sorting and Counting Networks of Arbitrary Width and Small Depth.
Theory of Computing Systems, Vol 35, No. 2, pp. 99-128, January 2002.
(Special issue with invited papers from SPAA 1999.)

17.   Costas Busch, Neophytos Demetriou, Maurice Herlihy, Marios Mavronicolas.
Threshold Counters with Increments and Decrements.
Theoretical Computer Science, Vol. 270, No. 1-2, pp. 811-826, January 2002.

18.   William Aiello, Costas Busch, Maurice Herlihy, Marios Mavronicolas, Nir Shavit, Dan Touitou.
Supporting Increment and Decrement Operations in Balancing Networks.
Chicago Journal of Theoretical Computer Science, Vol. 2000, Article 4, December 2000, MIT press.
Electronic journal, web link of paper: http://cjtcs.cs.uchicago.edu/articles/2000/4/contents.html.

19.   Costas Busch, Neophytos Demetriou, Maurice Herlihy, Marios Mavronicolas.
A Combinatorial Characterization of Properties Preserved by Antitokens.
Bulletin of the European Association for Theoretical Computer Science, No. 71, pp. 114-132, June 2000.

20.   Costas Busch, Marios Mavronicolas.
Impossibility Results for Weak Threshold Networks.
Information Processing Letters, Vol. 63, No. 2, pp. 85-90, July 1997.

21.   Costas Busch, Marios Mavronicolas.
A Combinatorial Treatment of Balancing Networks.
Journal of the ACM, Vol. 43, No. 5, pp. 749-839, September 1996.

22.   Costas Busch, Marios Mavronicolas.
Proving Correctness for Balancing Networks.
DIMACS Series in Discrete Mathematics and Theoretical Computer Science, ``Parallel Processing of Discrete Optimization Problems,'' American Mathematical Society, Vol. 22, pp. 1-32, 1995.

Book Chapter

1.      Costas Busch, Malik Magdon-Ismail, Jing Xi.

Oblivious Routing for Sensor Network Topologies.

Chapter 13 in Theoretical Aspects of Distributed Computing in Sensor Networks, S. Nikoletseas and J. Rolim editors, Monographs in Theoretical Computer Science, Springer, EATCS series, 1st Edition, 2011, ISBN 978-3-642-14848-4. 

2.      Costas Busch
Direct Routing.
Encyclopedia of Algorithms, Springer-Verlag, 2008; ISBN 978-0-387-30162-4.

3.      Costas Busch, Neophytos Demetriou, Maurice Herlihy, Marios Mavronicolas.
A Combinatorial Characterization of Properties Preserved by Antitokens.
Book chapter in Current Trends in Theoretical Computer Science - The Challenge of the New Century, G. Päun, G. Rozenberg and A. Salomaa editors, Vol. 1 (Algorithms and Complexity), pp. 296-313, World Scientific Publishing Co., April 2004; ISBN 9812387838.
(Previously appeared in the Bulletin of the European Association for Theoretical Computer Science.)

Book Translation

1.      Costas Busch, Dimitris Grammenos.
Translation into the Greek language of the book: Elements of Discrete Mathematics, C. L. Liu, McGraw-Hill, 2nd edition.
Th. Feidas and A. Laurentzos editors, University Press of Crete, Greece,1999; ISBN 9605240726.

Technical Report

1.      Eric N. Klein, Costas Busch, David R. Musser.
An Experimental Analysis of Counting Networks.
Technical Report, TR 06-13, Department of Computer Science, Rensselaer Polytechnic Institute, Troy, New York, September 2006.

ThesIS

1.      Costas Busch.
A Study on Distributed Structures. [slides]
PhD Thesis, Supervisor Maurice Herlihy, Department of Computer Science, Brown University, May 2000.

2.      Costas Busch.
Counting Networks of width pk.
Master’s Thesis, Supervisor Maurice Herlihy, Department of Computer Science, Brown University, Fall 1997.

3.      Costas Busch.
Design and Development of a Frame Grabber  for Still High Resolution Images.
Master’s Thesis, Supervisor Apostolos Traganitis, Department of Computer Science, University of Crete, Greece, August 1995.