Open questions

Graph exploration by a single agent

Arbitrary graphs, perpetual exploration static graph · undirected · perpetual

1. What is the time of memory-optimal perpetual exploration, and is there a trade-off between memory and time?

Trees, exploration with stop static graph · undirected · with stop · tree

1. Can exploration with stop on trees use asymptotically less memory than exploration with return? (Open problem of Diks et al. 2002.) Equivalently: close \(\Omega(\log\log\log n)\) versus \(O(\log n)\).

Exploration with return and pebbles static graph · undirected · pebbles

1. How much memory is needed to encode the agent's transition function? The naive table needs \((\log n)^{O(1)}\) bits (Remark 1 of Disser et al. 2019).

Exploration with stop when \(n\) is known static graph · undirected · knows a bound on \(n\) · with stop

1. Is \(\Omega(\log n)\) bits necessary when \(n\) is known? The trap arguments Fraigniaud et al. 2005 are stated for agents that know nothing.

Randomized exploration when \(n\) is known static graph · undirected · knows a bound on \(n\) · private coins · with stop

1. What is the memory needed by a randomized agent that must stop correctly with high probability, as a function of \(n\)?

Exploration with stop and one pebble static graph · undirected · one pebble · with stop

1. Is \(\Omega(D\log\Delta)\) memory needed for exploration with stop by an agent with one pebble Fraigniaud et al. 2005?

Port numbers chosen by the designer (periodic exploration) static graph · undirected · designer ports · perpetual

1. Close the constant gaps: \(2n-2\) versus \(3.5n-2\) for constant memory, \(2.8n-2\) versus \(4n-2\) for oblivious agents Czyzowicz et al. 2012.

2. Trade-offs between period and memory: the only lower bound for agents with memory does not depend on memory.

Directed graphs, one pebble static graph · one pebble · with stop

1. Close \(\Omega(n\log\Delta_{out})\) versus \(O(n\Delta_{out}\log n)\) bits for exploring digraphs with one pebble.

Directed graphs, one pebble, bound on \(n\) known static graph · knows a bound on \(n\) · one pebble · with stop

1. Improve the \(O(N^2 n^6 \Delta_{out}^2)\) running time (Section 5 of Bender et al. 2002).

Directed graphs with labelled nodes static graph · labelled nodes · with stop

1. Close \(\Omega(\phi^2m)\) versus \(O(\phi^8m)\) for online exploration of digraphs with deficiency \(\phi\).

Temporal graphs, schedule known connected every round · undirected · knows the map · perpetual

1. Tight bounds when the underlying graph is a grid, has bounded degree or is planar Erlebach et al. 2021.

Collaborative exploration

Arbitrary graphs, complete communication static graph · undirected · labelled nodes · global communication · synchronous

1. Is there an \(o(k)\)-competitive collaborative exploration algorithm for arbitrary graphs? (Stated as open in Cosson & Massoulié 2026.)

Trees, complete communication static graph · undirected · labelled nodes · global communication · synchronous · tree

1. Determine the competitive ratio of synchronous collective tree exploration: between \(\Omega(\log k/\log\log k)\) and \(O(\log^2 k)\).

2. Do randomized algorithms help? A randomized lower bound of \(\Omega(\sqrt{\log k}/\log\log k)\) is attributed to Ortolf and Schindelhauer (SPAA 2012), not checked here. Cosson and Massoulié conjecture they do not Cosson & Massoulié 2025.

Trees with \(k = n\) agents static graph · undirected · labelled nodes · global communication · synchronous · \(k = n\) · tree

1. For \(k=n\) and trees of depth \(D\) well above \(\sqrt{\log n}\) (e.g. \(D=\sqrt n\)), is \(\Omega(D^2)\) still necessary?

Large teams, complete communication static graph · undirected · labelled nodes · global communication · synchronous · \(k \ge Dn^{1+\varepsilon}\)

1. Which team size is necessary and sufficient for \(O(D)\)-round exploration of graphs of larger diameter? (Stated in Dereniowski et al. 2015.)

Trees, communication by whiteboards only static graph · undirected · labelled nodes · whiteboards · synchronous · tree

1. Is there a separation between write-read and complete communication? Cosson & Massoulié 2025 conjecture that centralised communication helps.

Trees, asynchronous, whiteboards only static graph · undirected · labelled nodes · whiteboards · tree

1. Is there a distributed asynchronous algorithm with polylogarithmic competitive ratio?

Anonymous graphs with \(k = n\) agents static graph · undirected · local communication · synchronous · \(k = n\)

1. Can \(n\) agents explore an anonymous tree in \(o(n)\) rounds, e.g. \(O(D^2)\), with local communication? With labelled nodes and global communication \(D^2\) suffices Disser et al. 2020.

Dispersion

Asynchronous agents static graph · undirected · \(k \le n\) · distinct IDs (eponymous) · no faults · local communication

1. Can an asynchronous algorithm let every agent terminate in polynomial time without knowledge of the graph? The only terminating asynchronous algorithm known uses \(O(\Delta^{\min(D,k)+1})\) time Kshemkalyani 2025; the linear-time algorithms keep settled agents active.

2. Semi-synchronous schedulers sit between the two models; no separation or dedicated bound is known.

Arbitrary graph, arbitrary initial configuration static graph · undirected · \(k \le n\) · distinct IDs (eponymous) · no faults · local communication · synchronous

1. Can the memory be reduced to \(O(\log k)\) bits, independent of \(\Delta\), while keeping \(O(k)\) time? Equivalently, is there an \(\Omega(\log\Delta)\) memory lower bound for deterministic agents with identifiers? The bound \(\Omega(\log(k+\Delta))\) is quoted in several papers but only the \(\log k\) term is argued.

2. Can all agents terminate explicitly in \(O(k)\) rounds without any knowledge of \(k\), \(m\) or \(\Delta\)? Sudo et al. 2024 terminates the rooted case in \(O(k)\) extra rounds but needs global upper bounds in the general case; Kshemkalyani et al. 2025 does not address termination detection for arbitrary initial configurations.

3. Ongoing dispersion Kshemkalyani & Ali 2019: agents that have settled must periodically leave (for example to recharge) and the configuration must be re-dispersed; no bounds beyond the original proposal are known.

Trees static graph · undirected · \(k \le n\) · distinct IDs (eponymous) · no faults · local communication · synchronous · tree

1. Augustine & Moses Jr. 2018 asked for \(o(n)\)-round dispersion on arbitrary trees. Precisely: for \(k = n\) and an arbitrary initial configuration, is there an algorithm whose time is bounded by a function of \(D\) alone, ideally \(O(D^2)\) as in the rooted case? No tree-specific algorithm has appeared since 2018; the linear-time general algorithms give only \(O(n)\).

2. With global communication, trees admit \(O(D\cdot\max(D,k))\) rounds with \(O(\max(D, \Delta\log k))\) bits (arXiv version of Kshemkalyani et al. 2020); whether the \(\max(D,k)\) factor can be reduced to \(D\), and whether local communication suffices, is open.

Rooted trees static graph · undirected · \(k \le n\) · distinct IDs (eponymous) · no faults · local communication · synchronous · tree · rooted start

1. For \(k < n\) the lower bound \(\Omega(D^2)\) no longer applies (only \(k\) nodes must be reached). Whether \(O(\min(k, D^2))\) time is achievable, and whether it is necessary, has not been addressed.

2. For \(k=n\) agents rooted on a tree of height \(D\) much larger than \(\sqrt{\log n}\), is \(\Omega(D^2)\) time necessary? The known bound is existential in \(D\) Disser et al. 2020.

Rooted initial configuration static graph · undirected · \(k \le n\) · distinct IDs (eponymous) · no faults · local communication · synchronous · rooted start

1. Is \(O(k)\) time achievable with \(O(\log k)\) bits? Memory \(O(\log(k+\Delta))\) is needed by every known algorithm to remember a port number.

Rings and paths static graph · undirected · \(k \le n\) · distinct IDs (eponymous) · no faults · local communication · synchronous · ring

1. Anonymous randomized agents disperse from a rooted ring configuration with \(O(1)\) bits in \(O(n)\) rounds Molla & Moses Jr. 2019. From an arbitrary configuration the known algorithm never terminates; is \(O(1)\)-bit dispersion with termination possible on rings?

Grids static graph · undirected · \(k \le n\) · distinct IDs (eponymous) · no faults · local communication · synchronous · grid

1. Can \(k \le n\) agents disperse on a grid in \(O(\sqrt k)\) rounds with local communication? Global communication achieves it Kshemkalyani et al. 2020; asked again in Banerjee et al. 2025.

2. A lower bound in terms of \(k\) for \(k = o(\sqrt n)\) with \(O(\log n)\) memory on unoriented grids Banerjee et al. 2024.

3. Unoriented grids with no knowledge of \(n\) and with faults, matching the fault-free bounds Banerjee et al. 2024.

Silent agents (no communication) static graph · undirected · \(k \le n\) · distinct IDs (eponymous) · no faults · synchronous

1. Close the time gap on general graphs: is \(O(k + \log L)\) achievable, as on rings?

2. Arbitrary (multi-source) initial configurations on general graphs; only rings are solved Das et al. 2025.

3. Weaker sensing: agents that only learn whether they are alone and whether the count decreased, and agents that wake up at different times (a 2026 ICDCIT paper by Gorain, Mandal and Sharma treats this; its bounds are not recorded here).

Silent agents on rings static graph · undirected · \(k \le n\) · distinct IDs (eponymous) · no faults · synchronous · ring

1. Unoriented rings, and rings where agents cannot detect count changes.

Global communication static graph · undirected · \(k \le n\) · distinct IDs (eponymous) · no faults · global communication · synchronous

1. Does global communication buy anything for dispersion? Since \(O(k)\) time with \(O(\log(k+\Delta))\) bits holds with local communication, a separation could only come from memory (\(O(\log k)\) bits), from termination detection, or from the BFS-style question of achieving time close to \(O(D)\)-dependent bounds for small \(D\).

2. Kshemkalyani et al. 2022 asks for \(O(\min(m,k\Delta))\) time with only \(O(\log(k+\Delta))\) bits in the global model; this is implied by the later local-model result, so the live version of the question is the memory question above.

Weak Byzantine agents static graph · undirected · \(k \le n\) · distinct IDs (eponymous) · at most weak Byzantine faults · local communication · synchronous

1. Faster Byzantine dispersion on general graphs: the time is dominated by Byzantine gathering, and the authors ask whether building a map before settling is necessary Molla et al. 2021.

2. Tolerating more than \(n/2\) weak Byzantine agents on general graphs (possible only on the restricted class so far) Molla et al. 2021.

3. Byzantine dispersion with bounded memory per agent, on trees, with \(k < n\), or under asynchrony: nothing is known Molla et al. 2020 Chand et al. 2023.

Weak Byzantine agents on rings static graph · undirected · \(k \le n\) · distinct IDs (eponymous) · at most weak Byzantine faults · local communication · synchronous · ring

1. Keep \(O(n)\) time and \(O(\log n)\) bits while dropping any of: identifiers in \([1,n]\), knowledge of \(f\), the bound \(f \le (n-4)/17\), the follow primitive Molla et al. 2020.

2. Asynchronous Byzantine dispersion on rings Molla et al. 2020.

Weak Byzantine agents on grids static graph · undirected · \(k \le n\) · distinct IDs (eponymous) · at most weak Byzantine faults · local communication · synchronous · grid

1. Reduce the memory below \(O(n\log n)\) bits on grids with weak Byzantine agents.

2. Strong Byzantine agents (able to fake identifiers) on grids Banerjee et al. 2025.

Crash faults static graph · undirected · \(k \le n\) · distinct IDs (eponymous) · at most crash faults · local communication · synchronous

1. Is \(O(k)\) time achievable with crash faults, or does fault tolerance cost a factor of \(\Delta\)? No lower bound beyond the fault-free \(\Omega(k)\) is known, even with \(O(\log(k+\Delta))\) memory Chand et al. 2023.

2. Simultaneously \(O(\min(m,k\Delta))\) (or better) time and \(O(\log(k+\Delta))\) memory for arbitrary configurations, without knowledge of \(f\), \(\ell\), \(\Delta\) or \(m\) Chand et al. 2023 Pattanayak et al. 2023.

3. Crash faults under asynchrony: no result exists.

Crash faults on grids static graph · undirected · \(k \le n\) · distinct IDs (eponymous) · at most crash faults · local communication · synchronous · grid

1. Unoriented grids with crashes: close the gap between \(O(\sqrt n\log n)\) rounds with \(O(\sqrt n\log n)\) bits and the fault-free \(O(\sqrt n)\), \(O(\log n)\) Banerjee et al. 2024.

Strong Byzantine agents static graph · undirected · \(k \le n\) · distinct IDs (eponymous) · local communication · synchronous

1. Polynomial-time strong-Byzantine dispersion from arbitrary configurations without a trusted agent, and the largest tolerable \(f\).

2. Asynchronous versions: a slow agent cannot be distinguished from a silent Byzantine one Moses Jr. & Redlich 2024.

Anonymous agents with randomness static graph · undirected · \(k \le n\) · private coins · no faults · local communication · synchronous

1. Close the gap between \(\Omega(k)\) and \(\Theta(k^2)\) rounds for anonymous agents from a rooted configuration with \(O(\log\Delta)\) bits Das et al. 2021.

2. Can anonymous randomized agents disperse from an arbitrary configuration and then stop, rather than staying active forever? Molla & Moses Jr. 2019 Das et al. 2021

3. On rings the memory bound is \(O(1)\); is \(O(1)\)-bit dispersion with termination possible on rings from arbitrary configurations?

More agents than nodes static graph · undirected · private coins · no faults · local communication · synchronous

1. Deterministic dispersion with \(k > n\) agents with identifiers on static graphs has not been studied: no algorithm and no lower bound beyond \(\Omega(k)\) is recorded in the literature surveyed here. (Related work exists only on dynamic rings and dynamic graphs under the name balanced dispersion.)

2. Is \(O(k)\) time possible for rooted configurations when \(k > n\), matching the \(k \le n\) case?

3. Terminating dispersion with \(k > n\) on general rooted graphs with \(O(\log\Delta)\) bits per agent (Open Problem 2 of Molla & Moses Jr. 2019).

Directed graphs static graph · \(k \le n\) · distinct IDs (eponymous) · no faults · local communication · synchronous

1. Close the time gaps; in particular \(O((k+f)k\Delta_{out})\) with \(f\) crashes Italiano et al. 2022.

2. BFS-based dispersion in the local model, without 1-hop communication Italiano et al. 2022.

3. Dispersion on dynamic directed graphs, and in semi-synchronous and asynchronous settings Italiano et al. 2022.

Directed graphs, 1-hop communication static graph · \(k \le n\) · distinct IDs (eponymous) · no faults · \(h\)-hop communication · synchronous

1. A BFS-based algorithm with \(O(\log(k+\Delta_{out}))\) bits per agent, as with local communication Italiano et al. 2022.

2. Does \(O(kD)\) improve to \(O(k + D^2)\) or \(O(k)\) with 1-hop communication?

Dynamic graphs (1-interval connected) connected every round · undirected · \(k \le n\) · distinct IDs (eponymous) · no faults · local communication · synchronous

1. Which combination of communication range and visibility is necessary for dispersion on \(T\)-interval connected graphs with \(T > 1\), where the impossibility proof for \(T = 1\) does not apply? Saxena & Mondal 2025

2. Dynamic graphs with a bounded number of missing edges per round: Saxena et al. 2025 gives impossibilities on 1-bounded 1-interval connected graphs for several weaker communication and visibility combinations and an \(O(k)\) algorithm with global communication and 1-hop visibility; the local-communication case with few missing edges is not settled.

Dynamic rings connected every round · undirected · \(k \le n\) · distinct IDs (eponymous) · no faults · local communication · synchronous · ring

1. Visibility strictly between none and full: how much must an agent see of a dynamic ring for dispersion to be possible? Agarwalla et al. 2018

2. Achiral agents on even rings of size at least 6 under vertex permutation and 1-interval connectivity: is \(O(n)\) time possible from arbitrary configurations? Agarwalla et al. 2018; \(O(\ell n)\) is known without vertex permutation Mondal et al. 2025.

Dynamic graphs with global communication connected every round · undirected · \(k \le n\) · distinct IDs (eponymous) · no faults · global communication · synchronous

1. Byzantine agents on dynamic graphs Kshemkalyani et al. 2020.

2. Memory \(O(\log k)\) instead of \(O(\log\max(k,T))\) on \(T\)-path connected graphs when \(T\) need not be known Saxena & Mondal 2025.

Treasure hunt

Anonymous finite graphs static graph · undirected · finite graph

1. Treasure hunt when the treasure may appear after the agent starts and the agent does not see its entry port: "We do not know if an efficient solution is possible when backtracking is not allowed" Ta-Shma & Zwick 2014.

2. Do strongly universal traversal sequences exist? They exist if and only if treasure hunt has a solution independent of the start time Ta-Shma & Zwick 2014.

Labelled nodes, locally finite graphs static graph · undirected · locally finite · labelled nodes

1. Remove the \(O(\log d)\) factor between \(O(e(d)\log d)\) and \(\Omega(e(d))\) Bouchard et al. 2023.

Rendezvous

Asynchronous labelled agents static graph · undirected · finite graph · distinct IDs (eponymous)

1. Find an optimal-cost asynchronous rendezvous algorithm in arbitrary graphs (open problem of Pelc 2019).

Labelled agents, arbitrary finite graphs static graph · undirected · finite graph · distinct IDs (eponymous) · synchronous

1. Find an optimal-time synchronous rendezvous algorithm for labelled agents in arbitrary graphs (open problem of Pelc 2019).

Labelled agents, graphs with infinite degrees static graph · undirected · distinct IDs (eponymous) · synchronous

1. Find an optimal rendezvous algorithm, "even for finite graphs" Pattanayak & Pelc 2024.

Pattern formation

ASYNC, no agreement on coordinates point · unlimited visibility · transparent · no faults

1. Bound the number of epochs needed by an arbitrary pattern formation algorithm in ASYNC; no time analysis is recorded.

Opaque robots with lights, ASYNC, one axis, rigid point · unlimited visibility · no faults · lights (LUMI) · one axis · rigid

1. The minimum number of colours, and formation with chirality only or with no agreement Bose et al. 2021.

Limited visibility point · transparent · no faults

1. Arbitrary pattern formation by oblivious robots with limited visibility from a general (connected) initial configuration Hahn et al. 2024.

Gathering

Rendezvous, internal light (FSTA), SSYNC, non-rigid point · unlimited visibility · transparent · no faults · SSYNC · internal light (FSTA) · \(n = 2\)

1. Rendezvous with internal lights in non-rigid SSYNC when \(\delta\) is unknown.

Gathering, internal light (FSTA), SSYNC, non-rigid point · unlimited visibility · transparent · no faults · SSYNC · internal light (FSTA) · chirality · \(n \ge 3\)

1. Gathering with internal lights in SSYNC from every start, with more than 2 colours, and in ASYNC Otaka et al. 2026.

Gathering, external light (FCOM), SSYNC, rigid point · unlimited visibility · transparent · no faults · SSYNC · external light (FCOM) · chirality · rigid · \(n \ge 3\)

1. Gathering with external lights in ASYNC Otaka et al. 2026.

Homonymous robots, SSYNC point · unlimited visibility · transparent · no faults · SSYNC · homonymous

1. What is the minimum number of identifiers for Byzantine-tolerant gathering? Asahiro & Yamashita 2025

Gathering, full lights, SSYNC, no multiplicity detection point · unlimited visibility · transparent · no faults · SSYNC · lights (LUMI) · chirality · \(n \ge 3\)

1. Gathering with lights without chirality Terai et al. 2023.

Gathering, full lights, ASYNC, no multiplicity detection point · unlimited visibility · transparent · no faults · lights (LUMI) · chirality · \(n \ge 3\)

1. Is 3 the minimum number of colours for ASYNC gathering with lights, and can chirality be dropped Nakai et al. 2021?

2. Self-stabilizing gathering of \(n\) robots with lights Heriban et al. 2018.

Rendezvous, external light (FCOM), ASYNC, non-rigid point · unlimited visibility · transparent · no faults · external light (FCOM) · \(n = 2\)

1. Rendezvous with external lights in non-rigid ASYNC when \(\delta\) is unknown Flocchini et al. 2016 Masuzawa et al. 2026.

Rendezvous, external light (FCOM), ASYNC, rigid point · unlimited visibility · transparent · no faults · external light (FCOM) · rigid · \(n = 2\)

1. Close the gap between 3 and 6 colours Masuzawa et al. 2026.

ASYNC with weak multiplicity detection point · unlimited visibility · transparent · no faults · weak multiplicity · \(n \ge 3\)

1. How many epochs does oblivious ASYNC gathering with weak multiplicity detection need?

Rendezvous, internal light (FSTA), ASYNC point · unlimited visibility · transparent · no faults · internal light (FSTA) · \(n = 2\)

1. Can robots with internal lights solve rendezvous in ASYNC Flocchini et al. 2016 Masuzawa et al. 2026?

Crash faults, SSYNC point · unlimited visibility · transparent · crash faults · SSYNC · weak multiplicity · \(n \ge 3\)

1. "The maximum number of faults under which a solution is still feasible, for gathering and other tasks, has yet to be established" Agmon & Peleg 2006, in particular in ASYNC.

Limited visibility, FSYNC, disoriented point · transparent · no faults · FSYNC

1. Is \(\Omega(\Delta_0^2)\) necessary for every protocol, not only local convex-hull ones?

Fat robots, few robots, no common orientation unlimited visibility · no faults · \(n \ge 3\)

1. Gathering any number of fat robots without chirality Agathangelou et al. 2013.

Fat robots, chirality, any number unlimited visibility · no faults · chirality · \(n \ge 3\)

1. Remove the chirality assumption Agathangelou et al. 2013.

Transparent fat robots, no chirality unlimited visibility · transparent · no faults · \(n \ge 3\)

1. Gathering transparent fat robots from symmetric starts; the paper proves no general impossibility Chaudhuri & Mukhopadhyaya 2015.

Uniform circle formation

ASYNC, oblivious, disoriented point · unlimited visibility · transparent · no faults

1. Can oblivious robots without lights form a uniform circle in \(O(1)\) epochs, with rigid or non-rigid moves? Feletti et al. 2024

Opaque robots with lights, ASYNC point · unlimited visibility · no faults · lights (LUMI) · rigid

1. What is the exact minimum number of colours for \(O(1)\)-epoch uniform circle formation in ASYNC? Feletti et al. 2024

2. Uniform circle formation with non-rigid moves in the luminous opaque model Feletti et al. 2024.

Convergence

Limited visibility, asynchronous point · transparent · no faults

1. Is point convergence with limited visibility solvable in full ASYNC, without perception or motion errors? Kirkpatrick et al. 2024

2. Is there a problem that separates k-ASYNC from SSYNC? Kirkpatrick et al. 2024

Linear search (cow path)

\(k\) robots on a line, Byzantine faults line · search · wireless · equal speeds

1. Determine the optimal competitive ratio \(B(k,f)\) for Byzantine search on the line; already \(B(3,1)\) is open.

Evacuation

Disk, two wireless robots of different speeds disk · two robots · wireless · no faults

1. Optimal evacuation for \(1 < v < 2.75\), for more than two robots, and face-to-face Lamprou et al. 2020.

Two robots, two exits, wireless disk · two robots · two exits · wireless · no faults · equal speeds

1. Close the gap between \(2R\) and \((1+\pi/3)R\) for two wireless robots and two exits Pattanayak et al. 2018.

Disk, search-and-fetch, two wireless robots disk · two robots · search-and-fetch · wireless · no faults

1. Lower bounds that separate wireless from face-to-face search-and-fetch Georgiou et al. 2019.

Two face-to-face robots, disk disk · two robots · no faults · equal speeds

1. Close the gap between \(3+\pi/6+\sqrt3 \approx 5.255\) and \(5.6234\) for two face-to-face robots.

Two robots with asymmetric communication, disk disk · two robots · sender/receiver · no faults · equal speeds

1. Give an explicit lower bound above \(\approx 4.826\) for sender/receiver evacuation.

Disk, priority evacuation, queen and one servant disk · two robots · priority (queen) · wireless · no faults

1. Close the gap between \(4.568\) and \(4.819\) Georgiou & Wang 2025.

Three wireless robots, disk disk · three robots · wireless · no faults · equal speeds

1. Find the optimal evacuation time for three wireless robots.

Three wireless robots, one crash fault disk · three robots · wireless · crash faults · equal speeds

1. Tight bounds for disk evacuation with one crash-faulty robot among three.

Priority evacuation (queen and servants), disk disk · priority (queen) · wireless · no faults · equal speeds

1. Close the gap for priority evacuation; for one servant the bounds differ by about 0.25 (a 2024 preprint, not yet in the bibliography).

Line, a sender and a receiver line · two robots · sender/receiver · no faults · equal speeds

1. Close the gaps for one sender and many receivers (\(2+\sqrt5\) against \(5\)) and for many senders and one receiver (\(3\) against about \(5.681\)) Czyzowicz et al. 2021.

Line, \(2f+1\) wireless robots, \(f\) crash faults line · wireless · crash faults · equal speeds

1. Tight bounds for evacuation with \(k = 2f+1\) crash or Byzantine robots Czyzowicz et al. 2021.

Triangle, two wireless robots starting on the boundary triangle · two robots · wireless · no faults · equal speeds

1. Face-to-face evacuation of general triangles, and wireless evacuation of obtuse triangles Georgiou & Jang 2026.

\(m\) rays, \(k = m\) wireless robots at the junction rays · wireless · no faults · equal speeds

1. Starting off the junction with \(k = m\): close \(2+\sqrt{7/3} \approx 3.528\) against \(4\) Brandt et al. 2020.

2. Fewer robots than rays (\(1 < k < m\)): the bounds \(3+2\lfloor (m-1)/k\rfloor\) and \(1+2\tfrac{m-1}{k}(1+\tfrac{k}{m-1})^{1+(m-1)/k}\) differ Brandt et al. 2020.

Gathering in graphs

Labelled agents static graph · undirected · no faults · distinct IDs (eponymous) · synchronous

1. Gathering without communication when no bound on \(n\) is known.

Byzantine agents static graph · undirected · distinct IDs (eponymous) · synchronous

1. Polynomial-time Byzantine gathering with teams of size close to \(f+1\).

Exploration of dynamic graphs by teams

1-interval-connected rings connected every round · undirected · synchronous · ring

1. With a landmark but no chirality, is \(O(n\log n)\) time necessary? Di Luna et al. 2020

Scattering

Randomized, ASYNC point · unlimited visibility · transparent · no faults · randomized

1. Solve scattering in ASYNC; Bramas and Tixeuil call it "the open problem of ASYNC scattering" Bramas & Tixeuil 2016 Bramas & Tixeuil 2017. A 2019 preprint by Léchine and Tixeuil (arXiv 1905.09177, not peer reviewed) solves it with vision and weak local multiplicity detection (its Theorem 4), and leaves open the plane with vision and no multiplicity detection.

Pattern sequences

Oblivious, SSYNC, chirality point · unlimited visibility · transparent · no faults · SSYNC · chirality · rigid

1. Form a sequence of patterns in ASYNC with oblivious robots Das et al. 2015.

Luminous robots, ASYNC, non-rigid, chirality point · unlimited visibility · transparent · no faults · lights (LUMI) · chirality

1. Close the gap between the colours used and the lower bound of Theorem 18 Das et al. 2020.

2. Pattern sequences with lights without chirality, with faults, or self-stabilising Das et al. 2020.

Near-gathering

ASYNC, limited visibility, one common axis point · transparent · no faults · one axis

1. Pagli, Prencipe and Viglietta conjecture that near-gathering is impossible without agreement on one axis.

SSYNC, limited visibility, disoriented point · transparent · no faults · SSYNC

1. Near-gathering in \(O(\Delta_0)\) epochs?

Mutual visibility

Lights, SSYNC, non-rigid point · unlimited visibility · no faults · SSYNC · lights (LUMI)

1. Does the 2-colour algorithm work in non-rigid SSYNC without knowing \(\delta\) Di Luna et al. 2017?

Lights, ASYNC, rigid point · unlimited visibility · no faults · lights (LUMI) · rigid

1. Fewer colours with \(O(1)\) epochs Sharma et al. 2021.

2. Time bounds with non-rigid moves.

Lights, ASYNC, non-rigid, one axis point · unlimited visibility · no faults · lights (LUMI) · one axis

1. Mutual visibility in non-rigid ASYNC without axis agreement, ideally with 2 colours Di Luna et al. 2017.

Lights, one crash, SSYNC, rigid, compass point · unlimited visibility · crash faults · SSYNC · lights (LUMI) · compass · rigid

1. Tolerating three or more crashes, and using 2 colours Aljohani & Sharma 2018.

Fat robots, ASYNC, one axis unlimited visibility · no faults · lights (LUMI) · one axis

1. Non-rigid moves, and SSYNC and ASYNC extensions of the 2-colour FSYNC algorithm Alsaedi et al. 2023.

k-grouping

\(k\) equal groups, randomized, SSYNC point · unlimited visibility · transparent · crash faults · SSYNC · randomized

1. Partitioning in ASYNC without a common orientation, by a randomized algorithm with no extra memory.

Leader election in programmable matter

Deterministic, with chirality constant memory · strong scheduler · chirality · may move · may disconnect

1. Fast deterministic leader election under weaker (non-atomic) schedulers, and without letting the system disconnect Dufoulon et al. 2021.

Deterministic, no orientation constant memory · strong scheduler · may move

1. Deterministic leader election without chirality in linear time.

Stationary, chirality, weak scheduler constant memory · chirality

1. Is a unique leader ever impossible for stationary particles with chirality? Dufoulon et al. say this was shown in Bazzi & Briones 2019, at least for a weak scheduler Dufoulon et al. 2021; the theorem was not read.

Stationary, asynchronous, no orientation, no holes constant memory · no holes

1. Deterministic leader election in \(O(L_{out}+D)\) rounds under a weaker scheduler Dufoulon et al. 2021.

SILBOT with holes may move

1. Can SILBOT particles elect leaders from configurations with holes if the system may disconnect temporarily, without exterior awareness? The impossibility of D'Angelo et al. 2020 assumes that connectivity is preserved.

Shape formation in programmable matter

SILBOT, chirality chirality

1. Is line formation solvable in SILBOT when particles share just one direction instead of the full orientation Navarra & Piselli 2023?

SILBOT, full orientation common compass · may disconnect

1. Does 1-hop visibility suffice for line formation in SILBOT Navarra & Piselli 2023?

2. Which other shapes can SILBOT particles form Navarra & Piselli 2023?

Coating

SILBOT, chirality, deterministic chirality

1. Coating in SILBOT without chirality Navarra & Piselli 2023.

2. Multi-layer coating, which "seems unfeasible" in SILBOT Navarra & Piselli 2023.

Compression

Markov chain, sequential constant memory · sequential · randomized

1. Behaviour for \(2.17 \le \lambda \le 2+\sqrt2\), and bounds on the convergence time.

Patrolling

Open fence, distinct speeds segment · no faults

1. How much better than partition can an optimal schedule be on a segment, and is the problem of computing an optimal schedule hard?

Graphs with faulty patrollers crash faults · equal speeds

1. Is the decision version of fault-tolerant patrolling in NP? With \(k\) part of the input and integer edge lengths it is in PSPACE Czyzowicz et al. 2017.

2. Optimal fault-tolerant patrolling of a segment when \(f \ge k/2 - 1\), and for even \(f\) Czyzowicz et al. 2017.

3. Approximation algorithms for the optimal idle time on general graphs Czyzowicz et al. 2017.

Exploration by luminous robots

Grids, FSYNC, terminating, no chirality, \(\varphi = 1\) static graph · undirected · grid · terminating · luminous · FSYNC · no faults

1. How many robots are needed for terminating grid exploration under FSYNC with \(\varphi = 1\) and no chirality: three or four?

Grids, ASYNC, terminating, no chirality, \(\varphi = 1\) static graph · undirected · grid · terminating · luminous · no faults

1. Close the gap between three and six robots for terminating grid exploration under ASYNC with \(\varphi = 1\) and no chirality Nagahama et al. 2022.

Grids, ASYNC, perpetual, chirality, \(\varphi = 2\) static graph · undirected · grid · perpetual · luminous · \(\varphi=2\) · chirality · no faults

1. Can two luminous robots with common chirality and \(\varphi = 2\) explore a finite grid perpetually under ASYNC (or SSYNC)?

Grids, ASYNC, perpetual, no chirality, \(\varphi = 2\) static graph · undirected · grid · perpetual · luminous · \(\varphi=2\) · no faults

1. Is there an optimal ASYNC algorithm (three robots, \(\varphi = 2\), no chirality) for opaque robots? Posed in Bramas et al. 2026.

Grids, ASYNC, perpetual, chirality, \(\varphi = 1\) (exclusive) static graph · undirected · grid · perpetual · luminous · chirality · no faults

1. Is perpetual grid exploration with \(\varphi = 1\) solvable under ASYNC when robots may share nodes (form towers)? Terminating exploration is, with three robots and three colours Nagahama et al. 2022.

Rings, FSYNC, perpetual, up to \(f\) crashes static graph · undirected · ring · perpetual · luminous · FSYNC · at most crash faults

1. With \(f + 2\) robots under FSYNC, how many colours are necessary for crash-tolerant perpetual ring exploration? The best algorithm uses \(3f + 2\) Ooshita et al. 2025.

Rings, ASYNC, perpetual, \(\varphi = 1\) static graph · undirected · ring · perpetual · luminous · no faults

1. Can three oblivious robots (\(c = 1\)) with \(\varphi = 1\) explore a ring perpetually under SSYNC or ASYNC, or are two colours necessary?

Rings, FSYNC, terminating, \(\varphi = 1\) static graph · undirected · ring · terminating · luminous · FSYNC · no faults

1. Characterise the initial configurations of three robots with \(c \ge 3\) colours from which terminating exploration of a ring is solvable under FSYNC with \(\varphi = 1\) (with two colours no universal algorithm exists Ooshita & Tixeuil 2022).

Rings, ASYNC, terminating, \(\varphi = 1\) static graph · undirected · ring · terminating · luminous · no faults

1. Does any task separate SSYNC from ASYNC for myopic luminous robots on rings? The known exploration bounds coincide under both Ooshita & Tixeuil 2022.

Tori, FSYNC, perpetual, no chirality, \(\varphi = 2\) static graph · undirected · torus · perpetual · luminous · FSYNC · \(\varphi=2\) · no faults

1. Can four oblivious robots with \(\varphi = 2\) explore a torus perpetually without chirality?

Tori, FSYNC, perpetual, no chirality, \(\varphi = 1\) static graph · undirected · torus · perpetual · luminous · FSYNC · no faults

1. Can three robots with two colours and \(\varphi = 1\) explore a torus perpetually without common chirality?

Exploration of recolourable graphs

Recolourable nodes, oblivious agent, any graph static graph · undirected · neighbour colours · recolourable · uniform \(c_0\)

1. Is the colour complexity of recolourable exploration of arbitrary graphs 4, 5 or 6 Takahashi et al. 2026 Hiraoka et al. 2026?

2. Give a proof of the four-colour lower bound without computer assistance, or for a single graph Hiraoka et al. 2026.

3. How many moves does a constant-colour algorithm need on general graphs? No bound is known; for graphs whose blocks are cliques or triangle-free, five colours and \(O(n\Delta)\) moves suffice Hiraoka et al. 2026.

4. How many colours suffice if the agent has a constant number of bits, or even one bit, of memory, or may move at random Böckenhauer et al. 2023 Takahashi et al. 2026?

5. Does forbidding recolouring back to \(c_0\) change the colour complexity, or only the algorithms Takahashi et al. 2026?

Recolourable nodes on cacti static graph · undirected · neighbour colours · recolourable · uniform \(c_0\) · cactus

1. Is four colours enough for φ-free graphs, or for graphs of maximum degree three? Both lie between 4 and 5 Hiraoka et al. 2026.

Once-colourable nodes, any graph static graph · undirected · neighbour colours · colour once · uniform \(c_0\)

1. For graphs of circumference \(\mathrm{circ}(G) \le g\), close the gap between \(\min(2g-2, n)\) and \(\min(2g, n)\) colours Böckenhauer et al. 2023.

Once-colourable nodes, \(n\) known static graph · undirected · neighbour colours · colour once · uniform \(c_0\) · \(n\) known

1. Is the colour complexity with known \(n\) equal to \(n-2\) or \(n-1\) Böckenhauer et al. 2023?

Label-guided: colours fixed by a designer static graph · undirected · ports + entry port · finite automaton · designer's colours · stop

1. Is there a 1-bit (two-colour) labeling with which a finite automaton explores every graph Cohen et al. 2008?

Label-guided, oblivious agent static graph · undirected · ports + entry port · designer's colours · perpetual

1. How many designer colours does an oblivious agent need to explore all graphs of maximum degree \(\Delta\) Cohen et al. 2008?

Rotor-router: a pointer in every node static graph · undirected · ports, no entry port · recolourable · perpetual

1. For which graphs (other than paths) is the rotor-router exactly time-optimal among oblivious agents without the entry port Menc et al. 2017?

Uniform deployment on a ring

Oriented ring, asynchronous, oblivious point · unlimited visibility · transparent · no faults · chirality

1. Is knowledge of \(d\) necessary for exact deployment on an oriented ring? Which capabilities allow asynchronous exact deployment on unoriented rings? Flocchini et al. 2008

Partitioning

Exactly \(n/k\) robots at each fixed point point · unlimited visibility · transparent · no faults · one axis

1. Partitioning into \(k\) groups of size \(n/k\) at points chosen by the robots (no fixed points given).

Separation of coloured particles

Markov chain, sequential constant memory · sequential · randomized

1. Bounds on the convergence (mixing) time.

Centralised transformations of modular robots

Rotation only nothing assumed on any axis

1. What is the complexity of connectivity-preserving transformability with rotations alone? The paper leaves it open (Section 7) Michail et al. 2019.

Rotation and sliding rotation + sliding

1. Prove the suspected \(\Omega(n\log n)\) lower bound for universal transformations with line pushing Almethen et al. 2020.

2. Distributed universal transformations with line pushing Almethen et al. 2020.