| 2000 | A powerful heuristic for telephone gossiping. René Beier, Jop F. Sibeyn |
| 2000 | A randomized leader election protocol for ad-hoc networks. Koji Nakano, Stephan Olariu |
| 2000 | An algorithmic definition of interval with applications to routing. Fabrizio Luccio, Linda Pagli |
| 2000 | Congestion and dilation, similarities and differences: A survey. André Raspaud, Ondrej Sýkora, Imrich Vrto |
| 2000 | Consensus in byzantine asynchronous systems. Roberto Baldoni, Jean-Michel Hélary, Michel Raynal, Lénaick Tanguy |
| 2000 | Construction of low-cost and low-diameter Steiner trees for multipoint groups. Alexis Irlande, Jean-Claude König, Christian Laforest |
| 2000 | Cooperative computing with fragmentable and mergeable groups. Chryssis Georgiou, Alexander A. Shvartsman |
| 2000 | Efficient wakeup in anonymous oriented complete graphs. Stefan Dobrev |
| 2000 | Exact communication costs for consensus and leader in a tree. Yefim Dinitz, Shlomo Moran, Sergio Rajsbaum |
| 2000 | Extremal bounds for probabilistic polling in graphs. Yehuda Hassin, David Peleg |
| 2000 | Lower bounds for (weak) sense of direction. Paolo Boldi, Sebastiano Vigna |
| 2000 | Lower bounds for hot-potato permutation routing on trees. Alan Roberts, Antonios Symvonis, David R. Wood |
| 2000 | Multiple message broadcasting in modified Knödel graph. Hovhannes A. Harutyunyan |
| 2000 | On time versus size for monotone dynamic monopolies in regular topologies. Paola Flocchini, Rastislav Kralovic, Alessandro Roncato, Peter Ruzicka, Nicola Santoro |
| 2000 | Optimal broadcast on parallel locality models. Ben H. H. Juurlink, Petr Kolman, Friedhelm Meyer auf der Heide, Ingo Rieping |
| 2000 | Randomized mobile agent based routing in wireless networks. Marc Bui, Sajal K. Das, Ajoy Kumar Datta, Dai Tho Nguyen |
| 2000 | SIROCCO 7, Proceedings of the 7th International Colloquium on Structural Information and Communication Complexity, Laquila, Italy, June 20-22, 2000 Michele Flammini, Enrico Nardelli, Guido Proietti, Paul G. Spirakis |
| 2000 | Self-stabilization with path algebra. Bertrand Ducourthial, Sébastien Tixeuil |
| 2000 | Termination detection and universal graph reconstruction. Yves Métivier, Gerard Tel |
| 2000 | The 1.5-loop network and the mixed 1.5-loop network. Frank K. Hwang, S. K. Chen |
| 2000 | The compactness of adaptive routing tables. Cyril Gavoille, Akka Zemmari |
| 2000 | Tracking causality in distributed systems: a suite of efficient protocols. Jean-Michel Hélary, Giovanna Melideo, Michel Raynal |