Conferences, Journals, Books, Technical Reports, Theses
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.)
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.
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.
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.
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.
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.