Publications

Conference Papers, Journal Papers, Other Publications

Conference Papers

1.      Costas Busch, Maurice Herlihy, Miroslav Popovic and Gokarna Sharma,

Fast Scheduling in Distributed Transactional Memory,

Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA),

To appear, Washington D.C., July 2017.

 

2.      Gokarna Sharma, Costas Busch and Supratik Mukhopadhyay,

Complete Visibility for Oblivious Robots in Linear Time,

Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA),

Brief announcement, to appear, Washington D.C., July 2017.

 

3.      Basem Assiri and Costas Busch,

Approximate Count and Queue Objects in Transactional Memory,

Proceedings of the 19th Workshop on Advances in Parallel and Distributed Computational Models (APDCM), IPDPS Workshops,

To appear, Orlando, Florida, May 2017.

 

4.      Gokarna Sharma, Ramachandran Vaidyanathan, Jerry L. Trahan, Costas Busch, and Suresh Rai,

O(log N)-Time Complete Visibility for Asynchronous Robots with Lights,

Proceedings of the 31th International Parallel and Distributed Processing Symposium (IPDPS),

To appear, Orlando, Florida, May 2017.

 

5.      Gokarna Sharma, Ramachandran Vaidyanathan, Jerry L. Trahan, Costas Busch, and Suresh Rai,

Complete Visibility for Robots with Lights in O(1) Time,

Proceedings of the 18th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS),

LNCS 10083, pp. 327-345, Lyon, France, November 2016.

 

6.      Limeng Pu, Hsiao-Chun Wu, Chiapin Wang, Shih-Hau Fang, Supratik Mukhopadhyay, and Costas Busch,

Novel Fast User-Placement Ushering Algorithms for Indoor Femtocell Networks,

Proceedings of IEEE Global Communications Conference (GLOBECOM),

6 pages, Washington, DC, December 2016.

 

7.      Basem Assiri and Costas Busch,

Approximately Opaque Multi-version Permissive Transactional Memory,

Proceedings of the 12th Intl. Workshop on Scheduling and Resource Mgmt. for Parallel and Distributed Systems (SRMPDS), ICPP Workshops,

pp. 393-402, Philadelphia, August 2016.

[slides]

 

8.      Basem Assiri and Costas Busch,

Approximately Opaque Multi-version Transactional Memory,

8th Workshop on the Theory of Transactional Memory (WTTM),

Appears as online pdf extended abstract (6 pages), Chicago, August 2016.

 

9.      Basem Assiri and Costas Busch,

Transactional Memory Scheduling Using Machine Learning Techniques,

Proceedings of the 24th Euromicro International Conference on Parallel, Distributed, and Network-Based Processing (PDP),

pp. 718-725, Heraklion, Crete, Greece, February 2016.

 

10.   Gokarna Sharma, Costas Busch, and Supratik Mukhopadhyay,

Mutual Visibility with an Optimal Number of Colors,

Proceedings of the 11th International Symposium on Algorithms for Sensor Systems (ALGOSENSORS),

LNCS 9536, pp. 196-210, Patras, Greece, September 2015.

[slides]

 

11.   Gokarna Sharma, Costas Busch, Supratik Mukhopadhyay, and Charles Malveaux,

Tight Analysis of a Collisionless Robot Gathering Algorithm,

Proceedings of the 2015 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS),

pp. 5189-5194, Hamburg, Germany, September 2015.

 

12.   Gokarna Sharma, Costas Busch, and Supratik Mukhopadhyay,

Bounds on Mutual Visibility Algorithms,

Proceedings of the 27th Canadian Conference on Computational Geometry (CCCG),

pp. 268-274, Kingston, Ontario, Canada, August 2015.

 

13.   Costas Busch, Maurice Herlihy, Miroslav Popovic, and Gokarna Sharma,

Impossibility Results for Distributed Transactional Memory,

Proceedings of the 34th Annual ACM Symposium on Principles of Distributed Computing (PODC),

pp. 207-215, Donostia-San Sebastian, Spain, July 2015.

 

14.   Ramachandran Vaidyanathan, Costas Busch, Jerry Trahan, Gokarna Sharma, and Suresh Rai,

Logarithmic-Time Complete Visibility for Robots with Lights,

Proceedings of the 29th IEEE International Parallel and Distributed Processing Symposium (IPDPS),

pp. 375-384, Hyderabad, India, May 2015.

     

15.   Costas Busch, Maurice Herlihy, Miroslav Popovic, and Gokarna Sharma,

Scheduling Multiple Objects in Distributed Transactional Memory,

Proceedings of the 28th International Symposium on Distributed Computing (DISC),

Brief announcement, pp. 538-539, Austin, TX, USA, October 2014.

[slides]

 

16.   Gokarna Sharma, Suresh Rai, Costas Busch, Jerry L. Trahan, and Ramachandran Vaidyanathan,

Work-Efficient Load Balancing,

Proceedings of the 10th Intl. Workshop on Scheduling and Resource Mgmt. for Parallel and Distributed Systems (SRMPDS), ICPP Workshops,

pp. 27-36, Minneapolis, MN, USA, September 2014.

 

17.   Gokarna Sharma and Costas Busch,

A Note on Online Steiner Tree Problems,

Proceedings of the 26th Canadian Conference on Computational Geometry (CCCG),

pp. 107-112, Halifax, Nova Scotia, Canada, August 2014.

[slides]

 

18.   Steven R. Brandt, Hari Krishnan, Gokarna Sharma, and Costas Busch,

Concurrent, Parallel Garbage Collection in Linear Time,

Proceedings of the 2014 ACM SIGPLAN International Symposium on Memory Management (ISMM),

pp. 47-58, Edinburgh, Scotland, UK, June 2014.

 

19.   Gokarna Sharma and Costas Busch,

Near-Optimal Deterministic Steiner Tree Maintenance in Sensor Networks,

Proceedings of the 10th IEEE International Conference on Distributed Computing in Sensor Systems (DCOSS),

pp. 201-208, Marina Del Rey, CA, USA, May 2014.

 

20.   Gokarna Sharma, Hari Krishnan, Costas Busch, and Steven R. Brandt.

Near-Optimal Location Tracking Using Sensor Networks,

Proceedings of the 16th Workshop on Advances in Parallel and Distributed Computational Models (APDCM), IPDPS Workshops,

pp. 737-746, Phoenix, Arizona, USA, May 2014.

 

21.   Gokarna Sharma and Costas Busch,

Distributed Queuing in Dynamic Networks,

Proceedings of the 9th International Workshop on Foundations of Mobile Computing (FOMC),

pp. 1-19, Jerusalem, Israel, October 2013.

[slides]

 

22.   Gokarna Sharma and Costas Busch,

Optimal Nearest Neighbor Queries in Sensor Networks,

Proceedings of the 9th International Symposium on Algorithms and Experiments for Sensor Systems (ALGOSENSORS),

LNCS 8243, pp. 260-277, Sophia Antipolis, France, September 2013.

[slides]

 

23.   Gokarna Sharma and Costas Busch, 

An Analysis Framework for Distributed Hierarchical Directories,

Proceedings of the 14th International Conference on Distributed Computing and Networking (ICDCN),

pp.  378-392, Mumbai, India, January 2013.

 

24.   Gokarna Sharma and Costas Busch, 

An Analysis Framework for Distributed Hierarchical Directories,

Proceedings of the 26th International Symposium on Distributed Computing (DISC 2012),

Brief announcement, pp. 415-416, Salvador-Bahia, Brazil, October 2012.

 

25.   Costas Busch, Chinmoy Dutta, Jaikumar Radhakrishnan, Rajmohan Rajaraman and Srivathsan Srinivasagopalan,

Split and Join: Strong Partitions and Universal Steiner Trees for Graphs,

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS),

pp. 81-90, New Brunswick, New Jersey, October 2012.

 

26.   Gokarna Sharma and Costas Busch,

Towards Load Balanced Distributed Transactional Memory,

Proceedings of the 18th International European Conference on Parallel and Distributed Computing (EUROPAR),

LNCS 7484, pp. 403-414, Rhodes Island, Greece, August 2012.

[slides]

 

27.   Gokarna Sharma, Costas Busch, Ramachandran Vaidyanathan, Suresh Rai, and Jerry L. Trahan,

An Efficient Transformation for the Klee's Measure Problem in the Streaming Model,

Proceedings of the 24th Canadian Conference on Computational Geometry (CCCG),

pp. 91-96, Charlottetown, Prince Edward Island, Canada, August 2012.

 

28.   Costas Busch and Rajgopal Kannan,

Stretch in Bottleneck Games,

Proceedings of the 18th Annual International Computing and Combinatorics Conference (COCOON),

LNCS 7434, pp. 592-603, Sydney, Australia, August 2012.

[slides]

 

29.   Gokarna Sharma, Costas Busch, and Srivathsan Srinivasagopalan,

Distributed Transactional Memory for General Networks,

Proceedings of the 26th IEEE International Parallel and Distributed Processing Symposium (IPDPS),

pp. 1045-1056, Shanghai, China, May 2012.

[slides]

30.   Costas Busch, Rajgopal Kannan, and Alfred Samman,

Bottleneck Routing Games on Grids,

Proceedings of the 2nd International ICST Conference on Game Theory for Networks (GameNets),

LNICST 75, pp. 294-307, Shanghai, China, April 2011.

[slides]

 

31.   Rajgopal Kannan, Costas Busch, and Athanasios V. Vasilakos,

Optimal Price of Anarchy of Polynomial and Super-Polynomial Bottleneck Congestion Games,

Proceedings of the 2nd International ICST Conference on Game Theory for Networks (GameNets),

Springer LNICST 75, pp. 308-320, Shanghai, China, April 2011.

 

32.   Gokarna Sharma and Costas Busch,

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

Proceedings of the 13th IPDPS Workshop on Advances in Parallel and Distributed Computational Models (APDCM), IPDPS Workshops,

pp. 559-568, Anchorage, Alaska, May 2011.

[slides]

 

33.   Srivathsan Srinivasagopalan, Costas Busch, and Sitharama Iyengar,

Oblivious Buy-at-Bulk in Planar Graphs,

Proceedings of the Workshop on Algorithms and Computation (WALCOM),

LNCS 6552, pp. 33-44, New Delhi, India, February 2011.

[slides]

 

34.   Gokarna Sharma and Costas Busch,

A Competitive Analysis for Balanced Transactional Memory Workloads,

Proceedings the 14th International Conference on Principles of Distributed Systems (OPODIS),

Springer LNCS 6490, pp. 348-363, Tozeur, Tunisia, December 2010.

[slides]

 

35.   Costas Busch and Malik Magdon-Ismail,

Optimal Oblivious Routing in Hole-Free Networks,

Proceedings of the 7th International Conference on Heterogeneous Networking for Quality, Reliability, Security, and Robustness (QShine),

Springer LNICST 74, pp. 421-437, Houston, Texas, November 2010.

[slides]

 

36.   Gokarna Sharma and Costas Busch,

Improving the Competitive Ratios of Transactional Memory Contention Managers,

2nd Workshop on the Theory of Transactional Memory (WTTM 2010),

Online abstract, Boston Massachusetts, September 2010.

[slides]

 

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

Window-Based Greedy Contention Management for Transactional Memory,

Proceedings of the 24 International Symposium on Distributed Computing (DISC),

LNCS 6343, pp. 64-78, Boston, Massachusetts, September 2010.

[slides]

 

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

 

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

Brief announcement, pp. 151-152, Rhodes Island, Greece, July 2009.

 

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

6 pages, March 2009.

 

41.   Costas Busch, Rajgopal Kannan, and Athanasios V. Vasilakos,
Quality of Routing Congestion Games in Wireless Sensor Networks,
Proceedings of the 4th International Wireless Internet Conference (WICON),

6 pages, Maui, Hawaii, November 2008.

[slides]

 

42.   Fikret Sivrikaya, Costas Busch, Malik Magdon-Ismail, and Bülent Yener,
ASAND: Asynchronous Slot Assignment and Neighbor Discovery Protocol for Wireless Networks,
OPNETWORK,

Washington DC, August 2007.

 

43.   Costas Busch, Ryan LaFortune, and 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.

[slides]

 

44.   Costas Busch, and Srikanta Tirthapura,

A Deterministic Algorithm for Summarizing Asynchronous Streams over a Sliding Window,
Proceedings of the 24th International Symposium on Theoretical Aspects of Computer Science (STACS),

LNCS 4393, pp. 465-476, Aachen, Germany, February 2007.

[slides]

 

45.   Srikanta Tirthapura, Bojan Xu, and Costas Busch,
Sketching Asynchronous Streams Over a Sliding Window,
Proceedings of the 25th Annual ACM Symposium on Principles of Distributed Computing (PODC),

pp. 82-91, Denver, Colorado, July 2006.

[slides]

 

46.   Costas Busch and Malik Magdon-Ismail,
Atomic Routing Games on Maximum Congestion,
Proceedings of the 2nd International Conference on Algorithmic Aspects in Information and Management (AAIM),

pp. 79-91, Hong Kong, China, June 2006.

[slides]

 

47.   Srikanta Tirthapura and Costas Busch,
Concurrent Counting is Harder than Queuing,
Proceedings of the 20th IEEE International Parallel and Distributed Processing Symposium (IPDPS),

10 pages, Rhodes Island, Greece, April 2006.

[slides]

 

48.   Nabhendra Bisnik, Alhousein Abouzeid, and Costas Busch,
Load Balanced Link Reversal Routing in Mobile Wireless Ad Hoc Networks,
Proceedings of the 4th Asian International Mobile Computing Conference (AMOC),

pp. 41-50, Kolkata, India, January 2006.

[slides]

 

49.   Costas Busch, Marios Mavronicolas, and Paul Spirakis,
Monotone Operations and Monotone Groups,
Proceedings of the 1st International Conference on Algebraic Informatics,

pp. 175-195, Thessaloniki, Greece, October 2005.

 

50.   Costas Busch, Shailesh Kelkar, and Malik Magdon-Ismail,
Efficient Bufferless Routing on Leveled Networks,
Proceedings of the 11th International Conference on Parallel and Distributed Computing (EUROPAR),

LNCS 3648, pp. 931-940, Lisboa, Portugal, August-September 2005.

[slides]

 

51.   Costas Busch, Malik-Magdon Ismail, and Jing Xi,
Oblivious Routing on Geometric Networks,
Proceedings of the 17th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA),

pp. 316-324, Las Vegas, Nevada, July 2005.

[slides]

 

52.   Costas Busch, Malik Magdon-Ismail, and Jing Xi,
Optimal Oblivious Path Selection on the Mesh,
Proceedings of the 19th IEEE International Parallel & Distributed Processing Symposium (IPDPS),

pp. 82-91, Denver, Colorado, April 2005.

[slides]

 

53.   Costas Busch, Malik Magdon-Ismail, Fikret Sinrikaya, and Bülent Yener,
Contention-Free MAC Protocols for Wireless Sensor Networks,
Proceedings of the 18th Annual Conference on Distributed Computing (DISC),

LNCS 3704, pp. 245-259, Amsterdam, the Netherlands, October 2004.

[slides]

 

54.   Costas Busch, Malik Magdon-Ismail, and Marios Mavronicolas,
Universal Bufferless Routing,
Proceedings of the 2nd Workshop on Approximation and Online Algorithms (WAOA),

LNCS 3351, pp. 239-252, Bergen, Norway, September 2004.

[slides]

 

55.   Costas Busch, Malik Magdon-Ismail, Marios Mavronicolas, and Paul Spirakis,
Direct Routing: Algorithms and Complexity,
Proceedings of the 12th Annual European Symposium on Algorithms (ESA),

LNCS 3221, pp 134-145, Bergen, Norway, September 2004.

[slides]

 

56.   Costas Busch, Malik Magdon-Ismail, Marios Mavronicolas, and Roger Wattenhofer,
Near-Optimal Hot-Potato Routing on Trees,
Proceedings of the 10th International Conference on Parallel and Distributed Computing (EUROPAR),

LNCS 3149, pp. 820-827, Pisa, Italy, August-September 2004.

[slides]

 

57.   Costas Busch, Marios Mavronicolas, and 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.

 

58.   Costas Busch, Srikanth Surapaneni, and Srikanta Tirthapura,
Analysis of Link Reversal Routing Algorithms for Mobile Ad Hoc Networks,
Proceedings of the 15th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA),

pp. 210-219, San Diego, California, June 2003.

[slides]

 

59.   Malik Magdon-Ismail, Costas Busch, and Mukkai S. Krishnamoorthy,
Cake-Cutting is Not a Piece of Cake,
Proceedings of the 20th International Symposium on Theoretical Aspects of Computer Science (STACS),

LNCS 2607, pp. 596-607, Berlin, Germany, February-March 2003.

[slides]

 

60.   Costas Busch,
Õ(Congestion+Dilation) Hot-Potato Routing on Leveled Networks,
Proceedings of the 14th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA),

pp. 20-29, Winnipeg, Manitoba, Canada, August 2002.

[slides]

 

61.   Costas Busch, Maurice Herlihy, and Roger Wattenhofer.
Routing without Flow Control,
Proceedings of the 13th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA),

pp. 11-20, Hersonissos, Crete, Greece, July 2001.

[slides]

 

62.   Costas Busch, Neophytos Demetriou, Maurice Herlihy, and 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.

 

63.   Costas Busch, Maurice Herlihy, and Roger Wattenhofer,
Hard-Potato Routing,
Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (STOC),

pp. 278-285, Portland, Oregon, May 2000.

[slides]

 

64.   Costas Busch, Maurice Herlihy, and Roger Wattenhofer,
Randomized Greedy Hot-Potato Routing,
Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA),

pp. 458-466, San Francisco, California, January 2000.

[slides]

 

65.   Costas Busch, Neophytos Demetriou, Maurice Herlihy, and 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.

 

66.   Costas Busch and 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.

 

67.   William Aiello, Costas Busch, Maurice Herlihy, Marios Mavronicolas, Nir Shavit, and Dan Touitou,
Supporting Increment and Decrement Operations in Balancing Networks,
Proceedings of the 16th International Symposium on Theoretical Aspects of Computer Science (STACS),

LNCS 1563, pp. 377-386, Trier, Germany, March 1999.

[slides]

 

68.   Costas Busch, and Marios Mavronicolas,
An Efficient Counting Network,
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.

[slides]

 

69.   Costas Busch and 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.

 

70.   Costas Busch and Marios Mavronicolas,
The Strength of Counting Networks,
Proceedings of the 15th Annual ACM Symposium on Principles of Distributed Computing (PODC),

Brief announcement, pp. 311, Philadelphia, Pennsylvania, May 1996.

 

71.   Costas Busch and Marios Mavronicolas,
A Logarithmic Depth Counting Network,
Proceedings of the 14th Annual ACM Symposium on Principles of Distributed Computing (PODC),

Brief announcement, pp. 274, Ottawa, Ontario, Canada, August 1995.

 

72.   Costas Busch and 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.

 

73.   Costas Busch, Nikos Hardavellas, and Marios Mavronicolas,
Contention in Counting Networks,
Proceedings of the 13th Annual ACM Symposium on Principles of Distributed Computing (PODC),

Brief announcement, pp. 404, Los Angeles, California, August 1994.

Journal Papers

 

1.      Gokarna Sharma and Costas Busch,

The Bursty Steiner Tree Problem,

International Journal of Foundations of Computer Science,

To appear.

 

2.      Gokarna Sharma, Costas Busch, Supratik Mukhopadhyay, and Charles Malveaux,

Tight Analysis of a Collisionless Robot Gathering Algorithm,

ACM Transactions on Autonomous and Adaptive Systems,

To appear.

 

3.      Gokarna Sharma and Costas Busch,

Near-Optimal Deterministic Steiner Tree Maintenance in Sensor Networks,

ACM Transactions on Sensor Networks,

Vol. 12, No. 1, pp. 4:1--4:29, March 2016.

 

4.      Gokarna Sharma and Costas Busch,

Optimal Nearest Neighbor Queries in Sensor Networks,

Theoretical Computer Science,

Vol. 608, Issue P2, pp. 146-165, December 2015.

(Special issue with invited papers from ALGOSENSORS 2013.)

 

5.      Gokarna Sharma, Costas Busch, Ramachandran Vaidyanathan, Suresh Rai, and Jerry L. Trahan,

Efficient Transformations for Klee`s Measure Problem in the Streaming Model,

Computational Geometry: Theory and Applications,

Vol. 48, No. 9, pp. 688-702, October 2015.

 

6.      Gokarna Sharma and Costas Busch,

Distributed Queuing in Dynamic Networks,

Parallel Processing Letters,

Vol. 25, No. 2, pages 1550005 (17 pages), June 2015.

 

7.      Gokarna Sharma and Costas Busch,

A Load Balanced Directory for Distributed Shared Memory Objects,

Journal of Parallel and Distributed Computing,

Vol. 78, Issue C, pp. 6-24, April 2015.

 

8.      Gokarna Sharma and Costas Busch,

An Analysis Framework for Distributed Hierarchical Directories,

Algorithmica,

Vol. 71, No. 2, pp. 377-408, February 2015.

 

9.      Gokarna Sharma, Hari Krishnan, Costas Busch, and Steven R. Brandt,

Near-Optimal Location Tracking Using Sensor Networks,

International Journal of Networking and Computing,

Vol. 5, No. 1, pp. 122-158, January 2015.

(Special issue with invited papers from APDCM 2014.)

 

10.   Gokarna Sharma and Costas Busch,

Distributed Transactional Memory for General Networks,

Distributed Computing,

Vol. 27, No. 5, pp. 329-362, October 2014.

 

11.   Costas Busch, Ryan LaFortune, Srikanta Tirthapura,

Sparse Covers for Planar Graphs and Graphs that Exclude a Fixed Minor,

Algorithmica,

Vol. 69, No. 3, pp. 658-684, July 2014.

 

12.   Gokarna Sharma and Costas Busch,

Transactional Memory: Models and Algorithms,

ACM SIGACT News,

Vol. 45, No. 2, pp. 74-103, June 2014.

 

13.   Costas Busch, Rajgopal Kannan, and Athanasios V. Vasilakos,

Approximating Congestion + Dilation in Networks via 'Quality of Routing' Games,

IEEE Transactions on Computers,

Vol 61, No. 9, pp. 1270-1283, September 2012.

 

14.   Gokarna Sharma and Costas Busch,

A Competitive Analysis for Balanced Transactional Memory Workloads,

Algorithmica,

Vol. 63, No. 1-2, pp. 296-322, June 2012.

 

15.   Srivathsan Srinivasagopalan, Costas Busch, and S.S. Iyengar,

An Oblivious Spanning Tree for Single-Sink Buy-at-Bulk in Low Doubling-Dimension Graphs,

IEEE Transactions on Computers,

Vol. 61, No. 5, pp. 700-712, May 2012.

16.   Gokarna Sharma and Costas Busch,

Window-Based Greedy Contention Management for Transactional Memory: Theory and Practice,

Distributed Computing,

Vol. 25, No. 3, pp. 225-248, February 2012.

17.   Costas Busch and Srikanta Tirthapura,

Concurrent Counting is Harder than Queuing,

Theoretical Computer Science,

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

 

18.   Costas Busch and Marios Mavronicolas,

An Efficient Counting Network,

Theoretical Computer Science,

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

 

19.   Costas Busch and Malik Magdon-Ismail,

Atomic Routing Games on Maximum Congestion,

Theoretical Computer Science,

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

 

20.   Costas Busch, Malik Magdon-Ismail, Fikret Sivrikaya, and Bulent Yener,
Contention-free MAC Protocols for Asynchronous Wireless Sensor Networks,
Distributed Computing,

Vol. 21, No. 1, pp. 23-42, June 2008.

 

21.   Costas Busch, Malik Magdon-Ismail, and Jing Xi,
Optimal Oblivious Path Selection on the Mesh,
IEEE Transactions on Computers,

Vol. 57, No. 5, pp. 660-671, May 2008.

 

22.   Bojan Xu, Srikanta Tirthapura, and Costas Busch,
Sketching Asynchronous Data Streams over Sliding Windows,
Distributed Computing,

Vol. 20, No. 5, pp. 359-374, February 2008.

 

23.   Costas Busch, Magdon-Ismail, and 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.

 

24.   Costas Busch, Malik Magdon-Ismail, and Marios Mavronicolas,
Universal Bufferless Packet Switching,
Siam Journal on Computing,

Vol. 37, No. 4, pp. 1139-1162, November 2007.

 

25.   James Aspnes, Costas Busch, Shlomi Dolev, Panagiota Fatourou, Chryssis Georgiou, Alex Shvartsman, Paul Spirakis, and Roger Wattenhofer, 
Eight Open problems in Distributed Computing,
Bulletin of the European Association for Theoretical Computer Science,

No. 90, pp. 109-126, October 2006.

 

26.   Costas Busch, Malik Magdon Ismail, Marios Mavronicolas, and 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.)

 

27.   Costas Busch and Srikanta Tirthapura,

Analysis of Link Reversal Routing Algorithms,
Siam Journal on Computing,

Vol. 35, No. 2, pp. 305-326, October 2005.

 

28.   Costas Busch, Mukkai S. Krishnamoorthy, and Malik Magdon-Ismail,

Hardness Results for Cake Cutting,
Bulletin of the European Association for Theoretical Computer Science,

No. 86, pp. 85-106, June 2005.

 

29.   Costas Busch, Marios Mavronicolas, and 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.)

 

30.   Costas Busch, Marios Mavronicolas, and 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.

 

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

 

32.   Costas Busch, Neophytos Demetriou, Maurice Herlihy, and Marios Mavronicolas,
Threshold Counters with Increments and Decrements,
Theoretical Computer Science,

Vol. 270, No. 1-2, pp. 811-826, January 2002.

 

33.   Costas Busch and 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.)

 

34.   William Aiello, Costas Busch, Maurice Herlihy, Marios Mavronicolas, Nir Shavit, and 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: http://cjtcs.cs.uchicago.edu/articles/2000/4/contents.html.

 

35.   Costas Busch, Neophytos Demetriou, Maurice Herlihy, and 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.

 

36.   Costas Busch and Marios Mavronicolas,
Impossibility Results for Weak Threshold Networks,
Information Processing Letters,

Vol. 63, No. 2, pp. 85-90, July 1997.

 

37.   Costas Busch and Marios Mavronicolas,

A Combinatorial Treatment of Balancing Networks,
Journal of the ACM,

Vol. 43, No. 5, pp. 749-839, September 1996.

 

38.   Costas Busch and 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.

 

Other Publications

Book ChapterS

1.      Rajgopal Kannan, Costas Busch, and Shuangqing Wei,

Jamming Games in Wireless and Sensor Networks,

Chapter 32 in Image and Sensor Signal Processing, S. Sitharama Iyengar and Richard R. Brooks editors, Chapman and Hall/CRC 2012, pp. 679-692, ISBN: 978-1-4398-6282-7.

 

2.      Costas Busch, Malik Magdon-Ismail, and 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, pages 381-406, 2011, ISBN 978-3-642-14849-1.

 

3.      Costas Busch,

Direct Routing,

Encyclopedia of Algorithms, Springer-Verlag, 2008; ISBN 978-0-387-30162-4.

 

4.      Costas Busch, Neophytos Demetriou, Maurice Herlihy, and 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 and 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, and 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,

PhD Thesis, Supervisor Maurice Herlihy, Department of Computer Science, Brown University, May 2000.

[slides]

 

2.      Costas Busch,
Counting Networks of width pk,
Master 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 Thesis, Supervisor Apostolos Traganitis, Department of Computer Science, University of Crete, Greece, August 1995.