Near-Optimal Scheduling in the Congested Clique

Keren Censor-Hillel, Yannic Maus, Volodymyr Polosukhin

Research output: Contribution to conferencePaperpeer-review


This paper provides three nearly-optimal algorithms for scheduling t jobs in the CLIQUE model. First, we present a deterministic scheduling algorithm that runs in O(GlobalCongestion+ dilation) rounds for jobs that are sufficiently efficient in terms of their memory. The dilation is the maximum round complexity of any of the given jobs, and the GlobalCongestion is the total number of messages in all jobs divided by the per-round bandwidth of n 2 of the CLIQUE model. Both are inherent lower bounds for any scheduling algorithm. Then, we present a randomized scheduling algorithm which runs t jobs in O(GlobalCongestion+ dilation· log n+ t) rounds and only requires that inputs and outputs do not exceed O(nlog n) bits per node, which is met by, e.g., almost all graph problems. Lastly, we adjust the random-delay-based scheduling algorithm [Ghaffari, PODC’15] from the CONGEST model and obtain an algorithm that schedules any t jobs in O(t/ n+ LocalCongestion+ dilation· log n) rounds, where the LocalCongestion relates to the congestion at a single node of the CLIQUE. We compare this algorithm to the previous approaches and show their benefit. We schedule the set of jobs on-the-fly, without a priori knowledge of its parameters or the communication patterns of the jobs. In light of the inherent lower bounds, all of our algorithms are nearly-optimal. We exemplify the power of our algorithms by analyzing the message complexity of the state-of-the-art MIS protocol [Ghaffari, Gouleakis, Konrad, Mitrovic and Rubinfeld, PODC’18], and we show that we can solve t instances of MIS in O(t+ log log Δlog n) rounds, that is, in O(1) amortized time, for t≥ log log Δlog n.

Original languageEnglish
Number of pages18
Publication statusPublished - 2021
Externally publishedYes
Event28th International Colloquium on Structural Information and Communication Complexity: SIROCCO 2021 - Virtual, Wrocław, Poland
Duration: 28 Jun 20211 Jul 2021


Conference28th International Colloquium on Structural Information and Communication Complexity
CityVirtual, Wrocław


  • Congested clique
  • Distributed algorithms
  • Maximal independent set
  • Scheduling

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this