Publications

Conferences, Journals, Books, Technical Reports, Theses

Conference Papers

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

2.       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.

3.       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.

4.       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.

5.       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.

6.       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.

7.       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.

8.       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.

9.       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.

10.    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), LNCS 3648, pp. 931-940, Lisboa, Portugal, Augoust-September 2005.

11.    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.

12.    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.

13.    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), LNCS 3704, pp. 245-259, Trippenhuis, Amsterdam, the Netherlands, October 2004.

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

15.    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), LNCS 3221, pp 134-145, Bergen, Norway, September 2004.

16.    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), LNCS 3149, pp. 820-827, Pisa, Italy, August-September 2004.

17.    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.

18.    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.

19.    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), LNCS 2607, pp. 596-607, Berlin, Germany, February-March 2003.

20.    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.

21.    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.

22.    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), Vol. 1900, pp. 575--582, Lecture Notes in Computer Science, Springer-Verlag, Munich, Germany, August/September 2000.

23.    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.

24.    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.

25.    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.

26.    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.

1.       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.

2.       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.

3.       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.)

4.       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.)

5.       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.)

6.       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.

7.       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 Papers

1.       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.

2.       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.

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

4.       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.

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

6.       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.)

7.       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.)

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

9.       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.

10.    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.)

11.    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.

12.    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.)

13.    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.)

14.    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.

15.    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.

16.    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.

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

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

19.    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 Chapters and Book Translation

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

2.       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.)

3.       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 Reports

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.

Theses

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.