NCN grant number DEC-2012/07/B/ST6/01534:

Design and Analysis of Scalable Algorithms for Wireless Networks (OPUS 4, 2013-17)

Publications & reports:

  1. M. Bienkowski, J. Byrka, K. Chrobak, T. Jurdzinski, and D. R. Kowalski. Provable fairness for TDMA scheduling. IEEE INFOCOM 2015, 1320–1327, 2015.
  2. M. Bienkowski, T. Jurdzinski, M. Korzeniowski, and D. R. Kowalski. Distributed online and stochastic queuing on a multiple access channel. Accepted to ACM Transactions on Algorithms (full&extended version of our DISC12 paper).
  3. M. Bienkowski, M. Klonowski, M. Korzeniowski, and D. R. Kowalski. Randomized mutual exclusion on a multiple access channel. Distributed Computing, 29(5):341–359, 2016.
  4. J. Byrka, T. Pensyl, B. Rybicki, J. Spoerhase, A. Srinivasan, and K. Trinh. An improved approximation algorithm for knapsack median using sparsification. ESA 2015, LNCS 9294, 275–287, Springer.
  5. T. Jurdzinski and D. R. Kowalski. On the complexity of distributed broadcasting and mds construction in radio networks. Manuscript, 2017.
  6. T. Jurdzinski, D. R. Kowalski, M. Rozanski, and G. Stachowiak. Distributed randomized broadcasting in wireless networks under the sinr model. In DISC, pages 373–387, 2013.
  7. T. Jurdzinski, D. R. Kowalski, M. Rozanski, and G. Stachowiak. On the impact of geometry on ad hoc communication in wireless networks. In ACM Symposium on Principles of Distributed Computing, PODC ’14, Paris, France, July 15-18, 2014, pages 357–366. ACM, 2014.
  8. T. Jurdzinski, D. R. Kowalski, M. Rozanski, and G. Stachowiak. On setting-up asynchronous ad hoc wireless networks. In 2015 IEEE Conference on Computer Communications, INFOCOM 2015, Kowloon, Hong Kong, April 26 - May 1, 2015, pages 2191–2199, 2015.
  9. Tomasz Jurdzinski, Krzysztof Nowicki: On Range and Edge Capacity in the Congested Clique, to appear in SOFSEM 2018. (This report, excluding Section 3, contains full exposition of the result)
  10. Tomasz Jurdzinski and Krzysztof Nowicki: Brief Announcement: On Connectivity in the Broadcast Congested Clique, to appear as a brief announcement in DISC 2017. (Section 3 of this report contains full exposition of the result)
  11. T. Jurdzinski, M. Rozanski, and G. Stachowiak. Token traversal in ad hoc wireless networks via implicit carrier sensing. SIROCCO 2017, 2017.
  12. Tomasz Jurdzinski, Dariusz R. Kowalski, Michal Rozanski, Grzegorz Stachowiak: Deterministic Digital Clustering of Wireless Ad Hoc Networks, arXiv
  13. T. Jurdzinski and G. Stachowiak. The cost of synchronizing multiple-access channels. In C. Georgiou and P. G. Spirakis, editors, Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC 2015, Donostia-San Sebasti´an, Spain, July 21-23, 2015, pages 421–430. ACM, 2015.
  14. G. D. Marco and D. R. Kowalski. Contention resolution in a non-synchronized multiple access channel. Accepted to Theoretical Computer Science, 2017.
  15. K. Nowicki. Parallel multiple selection by regular sampling. arXiv, 2016.
  16. Tomasz Jurdzinski, Krzysztof Nowicki: MST in O(1) Rounds of the Congested Clique, to appear in SODA 2018 (see this report).

Investigators:

  • M. Bieńkowski, J. Byrka, T. Jurdziński (Principal Investigator), D. Kowalski (Univ. Liverpool), K. Nowicki, M. Różański, G. Stachowiak.