Dariusz Kowalski's research interests and publications:

My research focuses on algorithms and complexity analysis.

Topics: Tools:



 

Publications

    1. On the complexity of asynchronous gossip,
      with Chryssis Georgiou, Seth Gilbert, and Rachid Guerraoui

      Conference version: Proc. of the 27th Annual ACM Symposium on Principles of Distributed Computing, PODC 2008, pp. 135-144

    2. Asynchronous exclusive selection,
      with Bogdan Chlebus

      Conference version: Proc. of the 27th Annual ACM Symposium on Principles of Distributed Computing, PODC 2008, pp. 375-384

    3. Fast Radio Broadcasting with Advice,
      with David Ilcinkas and Andrzej Pelc

      Conference version: Proc. of the 15th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2008, pp. 291-305

    4. Time efficient k-shot broadcasting in known topology radio networks,
      with Leszek Gasieniec, Erez Kantor, David Peleg, and Chang Su

      Conference version: Energy and time efficient broadcasting in known topology radio networks, Proc. of the 21st International Symposium on Distributed Computing, DISC 2007, pp. 253-267

      Journal version: Distributed Computing 21 (2008) 117-127 (DISC 2007 special issue)

    5. On the message complexity of indulgent consensus,
      with Seth Gilbert and Rachid Guerraoui

      Conference version: Proc. of the 21st International Symposium on Distributed Computing, DISC 2007, pp. 283-297

    6. On the Communication Surplus Incurred by Faulty Processors,
      with Michal Strojnowski

      Conference version: Proc. of the 21st International Symposium on Distributed Computing, DISC 2007, pp. 328-342

    7. Stability of the multiple-access channel under maximum broadcast loads,
      with Bogdan Chlebus and Mariusz Rokicki

      Conference version: Proc. of the 9th International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS 2007, pp. 124-138

    8. Adversarial queuing on the multiple-access channel,
      with Bogdan Chlebus and Mariusz Rokicki

      Conference version: Proc. of the 25th ACM Symposium on Principles of Distributed Computing, PODC 2006, pp. 92-101

    9. Time and communication efficient consensus for crash failures,
      with Bogdan Chlebus

      Conference version: Proc. of the 20th International Symposium on Distributed Computing, DISC 2006, pp. 314-328

    10. Average-time complexity of gossiping in radio networks,
      with Bogdan Chlebus and Mariusz Rokicki

      Conference version: Proc. of the 13th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2006, pp. 253-267

    11. How to meet in anonymous network,
      with Adam Malinowski

      Conference version: Proc. of the 13th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2006, pp. 44-58

      Journal version: Theoretical Computer Science 399 (2008) 141-156 (SIROCCO 2006 special issue)

    12. Many-to-Many Communication in Radio Networks,
      with Bogdan Chlebus and Tomasz Radzik

      Conference version: On many-to-many communication in packet radio networks, Proc. of the 10th International Conference on Principles of Distributed Systems, OPODIS 2006, pp. 260-274

      Journal version: Algorithmica, to appear

    13. Complexity of searching for a black hole,
      with Jurek Czyzowicz, Euripides Markou, and Andrzej Pelc

      Journal version: Fundamenta Informaticae 71 (2006) 229-242

    14. Node discovery in networks,
      with Kishori Konwar and Alex Shvartsman

      Conference version: Proc. of the 9th International Conference on Principles of Distributed Systems, OPODIS 2005, pp. 206-220

    15. Almost optimal explicit selectors,
      with Bogdan Chlebus

      Conference version: in Proc. of the 15th International Symposium on Fundamentals of Computation Theory, FCT 2005, pp. 270-280

    16. On the wake-up problem in radio networks,
      with Bogdan Chlebus, Leszek Gasieniec, and Tomasz Radzik

      Conference version: Proc. of the 32nd International Col loquium on Automata, Languages and Programming, ICALP 2005, pp. 347-359

    17. On selection problem in radio networks,

      Conference version: Proc. of the 24th ACM Symposium on Principles of Distributed Computing, PODC 2005, pp. 158-166

    18. Cooperative asynchronous update of shared memory,
      with Bogdan Chlebus

      Conference version: Proc. of the 37th ACM Symposium on Theory of Computing, STOC 2005, pp. 733-739

    19. Explicit combinatorial structures for cooperative distributed algorithms,
      with Peter Musial and Alex Shvartsman

      Conference version: Proc. of the 25th International Conference on Distributed Computing Systems, ICDCS 2005, pp. 49-58

    20. Fast distributed algorithm for convergecast in ad hoc geometric radio networks,
      with Alex Kesselman

      Conference version: Proc. of the 2nd International Conference on Wireless on Demand Network Systems and Service, WoNS 2005, pp. 119-124

      Journal version: Journal of Parallel and Distributed Computing (special issue on Algorithms for Wireless and Ad-Hoc Networks) 66:4 (2006) 578-585

    21. Energy efficient communication in ad hoc networks from user's and designer's perspective,
      with Alex Kesselman and Michael Segal

      Conference version: Energy efficient connectivity in ad hoc networks from user's and designer's perspective, in Proc. of the 40th IEEE Internationl Conference on Communications, ICC 2005

      Journal version: Mobile Computing and Communications Review 9:1 (2005) 15 - 26

    22. Collective tree exploration,
      with Pierre Fraigniaud, Leszek Gasieniec, and Andrzej Pelc

      Conference version: Proc. of the 6th Latin American Symposium on Theoretical Informatics, LATIN 2004, pp. 141-151

      Journal version: Networks 48:3 (2006) 166-177

    23. Writing-all deterministically and optimally using a nontrivial number of asynchronous processors,
      with Alex Shvartsman

      Conference version: Writing-All deterministically and optimally using a non-trivial number of asynchronous processors, in Proc. of the 16th ACM Symposium on Paral lel Algorithms and Architectures, SPAA 2004, pp. 311-320

      Journal version: ACM Transactions on Algorithms 4 (2008)

    24. Searching for a black hole in synchronous tree networks,
      with Jurek Czyzowicz, Euripides Markou, and Andrzej Pelc

      Conference version: Searching for a black hole in tree networks, in Proc. of the 8th International Conference on Principles of Distributed Systems, OPODIS 2004, pp. 67-80

      Journal version: Combinatorics, Probability and Computing 16 (2007) 595-619

    25. The wakeup problem in multihop radio networks,
      with Marek Chrobak and Leszek Gasieniec

      Conference version: The Wake-Up problem in multi-hop radio networks, in Proc. of the 15th ACM-SIAM Symposium on Discrete Algorithms, SODA 2004, pp. 992-1000

      Journal version: SIAM Journal on Computing 36:5 (2007) 1453-1471

    26. Optimal deterministic broadcasting in known topology radio networks,
      with Andrzej Pelc

      Preliminary conference version: Centralized deterministic broadcasting in undirected multi-hop radio networks, in Proc. of the 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2004, LNCS 3122, pp. 171-182

      Journal version: Distributed Computing 19:3 (2007) 185-195

    27. Deterministic rendezvous in graphs,
      with Anders Dessmark, Pierre Fraigniaud, and Andrzej Pelc

      Preliminary conference version: Polynomial deterministic rendezvous in arbitrary graphs, in Proc. of the 15th International Symposium on Algorithms and Computation, ISAAC 2004, LNCS 3341, pp. 644-656 (only with A. Pelc)

      Journal version: Algorithmica 46 (2006) 69-96 (ISAAC 2004 special issue)

    28. A better wake-up in radio networks,
      with Bogdan Chlebus

      Conference version: Proc. of the 23rd Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2004, pp. 266-274

    29. Collective asynchronous reading with polylogarithmic worst-case overhead,
      with Bogdan Chlebus and Alex Shvartsman

      Conference version: Proc. of the 36th ACM Symposium on Theory of Computing, STOC 2004, pp. 321-330

    30. The join problem in dynamic network algorithms,
      with Kishori Konwar and Alex Shvartsman

      Conference version: Proc. of the International Conference on Dependable Systems and Networks, DSN 2004, pp. 315-324

    31. Performing work with asynchronous processors: Message-delay-sensitive bounds,
      with Alex Shvartsman

      Conference version: Proc. of the 22nd ACM Symposium on Principles of Distributed Computing, PODC 2003, pp. 265-274

      Journal version: Information and Computation 203:2 (2005) 181-210

    32. Broadcasting in undirected ad hoc radio networks,
      with Andrzej Pelc

      Conference version: Proc. of the 22nd ACM Symposium on Principles of Distributed Computing, PODC 2003, pp. 73-82

      Journal version: Distributed Computing 18:1 (2005) 43-57 (PODC 2003 special issue)

    33. Efficient gossip and robust distributed computation,
      with Chryssis Georgiou and Alex Shvartsman

      Conference version: Proc. of the 17th International Symposium on Distributed Computing, DISC 2003, pp. 224-238

      Journal version: Theoretical Computer Science 347:1-2 (2005) 130-166

    34. Faster deterministic broadcasting in ad hoc radio networks,
      with Andrzej Pelc

      Conference version: Proc. of the 20th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2003,Springer, pp. 109-120

      Journal version: SIAM Journal on Discrete Mathematics 18:2 (2004) 332-346

    35. Time complexity of radio broadcasting: adaptiveness vs. obliviousness and randomization vs. determinism,
      with Andrzej Pelc

      Conference version: Time of radio broadcasting: adaptiveness vs. obliviousness and randomization vs. determinism, in Proc. of the 10th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2003, pp. 195-210

      Journal version: Theoretical Computer Science 333:3 (2005) 355-371 (SIROCCO 2003 special issue)

    36. Emulating shared-memory Do-All algorithms in asynchronous message-passing systems,
      with Mariam Momenzadeh and Alex Shvartsman

      Conference version: Proc. of the 7th Interantional Conference On Principles of Distributed Systems, OPODIS 2003, pp. 210-222

    37. Time of deterministic broadcasting in radio networks with local knowledge,
      with Andrzej Pelc

      Conference version: Deterministic broadcasting time in radio networks of unknown topology, in Proc. of the 43rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2002, pp. 63-72

      Journal version: SIAM Journal on Computing 33:4 (2004) 870-891

    38. Robust gossiping with an application to consensus,
      with Bogdan Chlebus

      Conference version: Gossiping to reach consensus, in Proc. of the 14th ACM Symposium on Parallel Algorithms and Architectures, SPAA 2002, pp. 220-229

      Journal version: Journal of Computer and System Sciences 72:8 (2006) 1262-1281

    39. Broadcasting spanning forests on a Multiple Access Channel,
      with Bogdan Chlebus and Karol Golab

      Conference version: Finding spanning forests by broadcasting, in Proc. of the 9th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2002, pp. 41-56

      Journal version: Theory of Computing Systems 36 (2003) 711-733 (SIROCCO 2002 special issue)

    40. Bounding work and communication in robust cooperative computation,
      with Bogdan Chlebus, Leszek Gasieniec, and Alex Shvartsman

      Conference version: Proc. of the 16th International Symposium on Distributed Computing, DISC 2002, pp. 295-310

    41. Towards practical deterministic Write-All algorithms,
      with Bogdan Chlebus, Stefan Dobrev, Grzegorz Malewicz, Alex Shvartsman, and Imrich Vrto

      Conference version: Proc. of the 13th ACM Symposium on Parallel Algorithms and Architectures, SPAA 2001, pp. 271-280

    42. Performing work in broadcast networks,
      with Bogdan Chlebus and Andrzej Lingas

      Conference version: The Do-All problem in broadcast networks, in Proc. of the 20th ACM Symposium on Principles of Distributed Computing, PODC 2001, pp. 117-126

      Journal version: Distributed Computing 18:6 (2006) 435-451

    43. Randomization helps to perform independent tasks reliably,
      with Bogdan Chlebus

      Conference version: Randomization helps to perform tasks on processors prone to failures, in Proc. of the 13th International Symposium on Distributed Computing, DISC 1999,LNCS 1693, pp. 284-296

      Journal version: Random Structures and Algorithms 24 (2004) 11-41

Book chapter

    1. Distributed Algorithms, in Algorithms of Computer Science, Volume II, Scholar Publisher, Budapest, February 2005 (with B. Englert, G. Malewicz and A. Shvartsman)



 

Other publications

    1. A Review of the DISC 2005 Conference, SIGACT News (Distributed Computing Column), 20 (2005)
    2. Distributed algorithms to perform independent tasks in networks with processor faults, Ph.D. Thesis, Warsaw University, Poland, 2001 (pdf format)
    3. Algorithms for generating and counting based on rapidly mixing Markov Chains (in Polish), M.Sc. Thesis, Warsaw University, Poland, 1996


Last updated12.09.2008