arxiv: 2605.09432 · v1 · submitted 2026-05-10 · 💻 cs.NI

Recognition: no theorem link

The Carrier Pigeon Internet Protocol: An Algorithmic (and Lighthearted) Perspective

Darya Melnyk, Matthias Bentert, Shay Kutten, Stefan Schmid, Tijana Milentijevic

Pith reviewed 2026-05-12 02:58 UTC · model grok-4.3

classification 💻 cs.NI

keywords carrier pigeonsnetwork protocolsapproximation algorithmsNP-hardnessdemand aggregationmultihop routing

0 comments

The pith

A polynomial-time demand aggregation algorithm approximates the fewest carrier pigeons needed for two-hop and multihop messages within a factor of two, even though exact minimization is NP-hard.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper addresses the algorithmic task of breeding and scheduling pigeons to satisfy a given set of communication demands while minimizing the total number of pigeons used. Single-hop demands permit a simple exact characterization, but both two-hop and multihop cases turn out to be NP-hard. The authors supply a polynomial-time method that aggregates demands to produce a schedule using at most twice the optimal number of pigeons. A sympathetic reader would care because the underlying Shannon model already shows that pigeon links can exceed the bandwidth of conventional media, so practical management of the birds could turn a theoretical curiosity into a workable network design choice.

Core claim

The authors prove NP-hardness for minimizing the number of pigeons required under two-hop and multihop routing. They then give a polynomial-time algorithm based on demand aggregation that returns a feasible pigeon schedule whose total count is guaranteed to be at most twice the minimum possible.

What carries the argument

Demand aggregation, the technique of grouping compatible messages so that the same pigeons can serve multiple demands without violating the one-use-per-pigeon rule.

Load-bearing premise

All communication demands are known in advance so that pigeon uses can be aggregated and planned offline.

What would settle it

A concrete set of node-to-node demands for which the aggregation algorithm returns a schedule using strictly more than twice the minimum number of pigeons required by any feasible schedule.

Figures

Figures reproduced from arXiv: 2605.09432 by Darya Melnyk, Matthias Bentert, Shay Kutten, Stefan Schmid, Tijana Milentijevic.

**Figure 1.** Figure 1: On the left side a demand graph 𝐺𝐷 is depicted with 3 source and 3 destination nodes. The right side shows the corresponding infrastructure graph 𝐺𝐼 induced by pigeons, illustrating an optimal placement and routing solution that satisfies all the demands while minimizing the total number of pigeons used. In this example, a pigeon 𝑝 flying from 𝑠3 to 𝑠1 has 𝑠1 as its birthplace, i.e. ℎ(𝑝) = 𝑠1. The pigeon i… view at source ↗

**Figure 2.** Figure 2: and the forced edge gadget is illustrated in [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗

**Figure 3.** Figure 3: Two arms of a forced edge gadget in the demand [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗

**Figure 4.** Figure 4: The constraints of the ILP for 2-hop - . node 𝑣𝑛−1. This construction always forwards all the demand with 2𝑛 − 2 pigeons. □ The following theorem establishes the properties of an ILP we present for the 2-hop - problem. Theorem 5. There is an ILP with 𝑂(𝑛 4 ) variables and 𝑂(𝑛 3 ) constraints for 2-hop - , where all variables are binary. Proof. Let (𝐺 = (𝑉 , 𝐸), 𝑘) be an instance of 2-hop - . We construct … view at source ↗

**Figure 5.** Figure 5: An example instance of Vertex Cover on the left and the corresponding equivalent instance of Multihop - on the right. To conclude the construction, we set 𝑘 ′ = 𝑛 + 𝑘 − 1, where 𝑛 = |𝑉 |. See [PITH_FULL_IMAGE:figures/full_fig_p008_5.png] view at source ↗

**Figure 6.** Figure 6: The constraints of the ILP for Multihop - . least two pigeons are initially placed in a solution as well as the the destination of the last pigeon flight. We will show that 𝐾 is a vertex cover of size at most 𝑘. First, note that since each node in 𝑉 is incident to at least one edge in 𝐸, it also holds for each node 𝑢 that there is a demand of the form (𝑢, 𝑣) ∈ 𝐸 ′ . Hence, at least one pigeon needs to star… view at source ↗

read the original abstract

The theoretical model behind the pigeon post as a link layer in a communication network was introduced by Shannon (under the guise of studying One-Time Pads for cryptography). That is, to send a one-hop message to $v$, a node $u$ needs a mail pigeon bred and raised at $v$. When sending a message using a pigeon to $v$, node $u$ loses the pigeon. To send another message to $v$, node $u$ needs another pigeon of $v$. It has been demonstrated that the communication bandwidth achievable with pigeon post can exceed that of networks using other media. This has already motivated the introduction of Internet standards that allow the use of pigeons as Internet link-layer media. In this paper, we begin to fill in the missing piece: designing algorithms for breeding and scheduling pigeons to meet a given communication demand efficiently, minimizing the number of pigeons required. We consider singlehop, 2-hop, and multihop pigeon use. While the singlehop variant admits a simple characterization, both the 2-hop and the multihop variants are NP-hard. For the latter variants, we present a polynomial-time algorithm based on demand aggregation that achieves a 2-approximation for the number of pigeons used. We believe that this pigeon-based perspective offers both amusing and instructive insights into network design and hopefully, into ornithology.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper supplies a clean 2-approximation for multihop pigeon scheduling via demand aggregation and shows NP-hardness for the non-trivial cases.

read the letter

The main thing to know is that the authors give a polynomial-time 2-approximation for the multihop pigeon scheduling problem by aggregating demands, and they prove NP-hardness for both the 2-hop and multihop variants under the Shannon model where pigeons are pre-bred at the destination and consumed on each use. Single-hop is easy to handle directly. This is the core technical content. The approximation is a direct application of demand aggregation, which produces the factor of 2 guarantee in polynomial time. It is a straightforward extension of standard techniques to this stylized setting, and the construction is explicit enough to be useful as a teaching example for NP-hardness and simple approximations. The model assumptions are stated up front, so the results sit on a consistent foundation rather than hidden fitting. The lighthearted framing does not interfere with the algorithmic claims. The main limitation is scope. The offline demand assumption and the specific breeding rules keep the problem clean but also keep the practical carry-over narrow. Hardness is asserted via reductions that look plausible from the description, with no internal contradictions in the stated results. This paper is aimed at readers who work on approximation algorithms or network design and want a memorable, self-contained example. It is coherent on its own terms and shows clear engagement with the model. I would send it to peer review. The claims are concrete and the approximation is constructive, so a referee can check the details without starting from scratch.

Referee Report

2 major / 1 minor

Summary. The paper models pigeon-based communication following Shannon's one-time-pad-inspired setup, where pigeons must be pre-bred at the destination node and are consumed on each use. It analyzes the minimum-pigeon scheduling problem for single-hop, 2-hop, and multihop demands. The single-hop case admits a simple characterization; the 2-hop and multihop cases are asserted to be NP-hard; and a polynomial-time demand-aggregation algorithm is presented that yields a 2-approximation on the number of pigeons required.

Significance. If the stated hardness results and approximation guarantee hold, the work supplies a constructive algorithmic treatment of resource allocation under the pigeon model, illustrating how offline demand aggregation can produce a constant-factor guarantee. This offers limited but instructive insight into unconventional network media and may serve pedagogical purposes in network-algorithm design.

major comments (2)

[Abstract] The abstract asserts NP-hardness for both the 2-hop and multihop variants together with a polynomial-time 2-approximation via demand aggregation, yet the manuscript provides neither the hardness reduction nor the proof that the aggregation procedure achieves a factor of 2. These claims are load-bearing for the central contribution.
The description of the demand-aggregation procedure (how demands are combined across hops while respecting the consumption and pre-breeding constraints) is not elaborated with sufficient detail to verify polynomial runtime or the approximation ratio.

minor comments (1)

The lighthearted framing is consistent with the title but occasionally blurs the boundary between informal remarks and formal statements; a brief dedicated technical section separating the algorithmic results would improve clarity.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful and constructive review of our manuscript. We agree that the central claims regarding NP-hardness and the 2-approximation require explicit supporting arguments in the text, and we will revise the paper to address these points in detail.

read point-by-point responses

Referee: [Abstract] The abstract asserts NP-hardness for both the 2-hop and multihop variants together with a polynomial-time 2-approximation via demand aggregation, yet the manuscript provides neither the hardness reduction nor the proof that the aggregation procedure achieves a factor of 2. These claims are load-bearing for the central contribution.

Authors: We acknowledge that the submitted manuscript does not contain the explicit hardness reduction or the formal proof of the approximation ratio. These elements were not included in the initial version. In the revision we will add a dedicated section that presents a polynomial-time reduction establishing NP-hardness for the 2-hop and multihop variants, together with a complete proof that the demand-aggregation algorithm yields a 2-approximation while respecting pre-breeding and consumption constraints. revision: yes
Referee: [—] The description of the demand-aggregation procedure (how demands are combined across hops while respecting the consumption and pre-breeding constraints) is not elaborated with sufficient detail to verify polynomial runtime or the approximation ratio.

Authors: We agree that the current description of the demand-aggregation procedure is insufficiently detailed. The revision will include pseudocode for the algorithm, a proof that it runs in polynomial time, and a step-by-step argument showing how demands are aggregated across hops without violating the pre-breeding requirement at each node or the one-time consumption of each pigeon, thereby establishing the claimed approximation guarantee. revision: yes

Circularity Check

0 steps flagged

No significant circularity; results derive from external model and standard algorithmic techniques

full rationale

The paper states its model (pigeons pre-bred at destination and consumed per use) as taken from Shannon and assumes offline known demands for aggregation. NP-hardness for 2-hop/multihop and the 2-approximation via demand aggregation are presented as constructive proofs and algorithms on this model, without reducing to self-definitions, fitted parameters renamed as predictions, or load-bearing self-citations. Single-hop admits an independent simple characterization. No equations or steps collapse by construction to inputs; the derivation chain is self-contained against the stated assumptions.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the Shannon pigeon-post model (pigeons pre-bred at destination and consumed per use) plus standard algorithmic assumptions; no free parameters or invented entities are introduced.

axioms (1)

domain assumption To send a message to node v, a node u requires a pigeon bred and raised at v; each use consumes the pigeon.
This is the core link-layer model stated in the abstract and attributed to Shannon.

pith-pipeline@v0.9.0 · 5559 in / 1221 out tokens · 45556 ms · 2026-05-12T02:58:29.596158+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

50 extracted references · 50 canonical work pages

[1]

Miklós Ajtai. 1994. The complexity of the pigeonhole principle.Combinatorica 14, 4 (1994), 417–433

work page 1994
[2]

Chen Avin, Manya Ghobadi, Chen Griner, and Stefan Schmid. 2020. On the com- plexity of traffic traces and implications.Proceedings of the ACM on Measurement and Analysis of Computing Systems4, 1 (2020), 1–29

work page 2020
[3]

Chen Avin, Kaushik Mondal, and Stefan Schmid. 2020. Demand-aware network designs of bounded degree.Distributed Computing33, 3 (2020), 311–325

work page 2020
[4]

Chen Avin and Stefan Schmid. 2025. Revolutionizing Datacenter Networks via Reconfigurable Topologies.Commun. ACM68, 6 (2025), 44–53

work page 2025
[5]

BBC. 2011. SA pigeon ’faster than broadband’. https://web.archive.org/ web/20110414225332/http://news.bbc.co.uk/2/hi/africa/8248056.stm Accessed: 24/12/2025. Conference’17, July 2017, Washington, DC, USA Matthias Bentert, Shay Kutten, Darya Melnyk, Tijana Milentijević, and Stefan Schmid

work page arXiv 2011
[6]

Beckmann, C

Martin J. Beckmann, C. B. McGuire, and Christopher B. Winsten. 1956.Studies in the Economics of Transportation. Yale University Press

work page 1956
[7]

Yossi Ben-Bassat. 2025. A New Israeli test confirms: PEI (Pigeon Enabled Internet) is FASTER than ADSL. https://web.archive.org/web/20080713090722/http://www. notes.co.il/benbasat/5240.asp Accessed: 24/12/2025

work page arXiv 2025
[8]

Samuel W Bent, Daniel D Sleator, and Robert E Tarjan. 1985. Biased search trees. SIAM J. Comput.14, 3 (1985), 545–568

work page 1985
[9]

Zhi Cao and Eric Masanet. 2022. Material efficiency to tackle the sand crisis. Nature Sustainability5, 5 (2022), 370–371

work page 2022
[10]

Carpenter and R

B. Carpenter and R. Hinden. [n. d.].Adaptation of RFC 1149 for IPv6. RFC 6249. RFC Editor. doi:10.17487/RFC2549

work page doi:10.17487/rfc2549
[11]

Benoit Crevier, Jean-François Cordeau, and Gilbert Laporte. 2007. The multi- depot vehicle routing problem with inter-depot routes.European journal of operational research176, 2 (2007), 756–773

work page 2007
[12]

Erik D Demaine, Dion Harmon, John Iacono, and Mihai P a ˇ traşcu. 2007. Dynamic optimality—almost.SIAM J. Comput.37, 1 (2007), 240–251

work page 2007
[13]

Josep Díaz, Jordi Petit, and Maria Serna. 2002. A survey of graph layout problems. ACM Computing Surveys (CSUR)34, 3 (2002), 313–356

work page 2002
[14]

Gutiérrez-Espeleta, Nyovani Madise, Ying Wang, Robert Watson, Tamiru A

United Nations Environment Programme, Edgar E. Gutiérrez-Espeleta, Nyovani Madise, Ying Wang, Robert Watson, Tamiru A. Abiye, Ana Paula Aguiar, Peter Alexander, Barbara Amon, Apoorva Arya, Ghassem Asrar, Lindsay Beevers, Medani Bhandari, Meena Bohara, Gillian Bowser, David Broadstock, Monday Businge, Donovan Campbell, Kateřina Černý Pixová, Lynette Cheah ...

work page 2025
[15]

Shimon Even, Alon Itai, and Adi Shamir. 1975. On the complexity of time table and multi-commodity flow problems. In16th annual symposium on foundations of computer science (FOCS). IEEE, 184–193

work page 1975
[16]

Nathan Farrington, George Porter, Sivasankar Radhakrishnan, Hamid Hajabdolali Bazzaz, Vikram Subramanya, Yeshaiahu Fainman, George Papen, and Amin Vahdat. 2010. Helios: a hybrid electrical/optical switch architecture for modular data centers. InProceedings of the ACM SIGCOMM 2010 Conference. 339–350

work page 2010
[17]

Bernard Fortz and Mikkel Thorup. 2000. Internet traffic engineering by optimiz- ing OSPF weights. InProceedings IEEE INFOCOM 2000. conference on computer communications. Nineteenth annual joint conference of the IEEE computer and communications societies (Cat. No. 00CH37064), Vol. 2. IEEE, 519–528

work page 2000
[18]

Monia Ghobadi, Ratul Mahajan, Amar Phanishayee, Nikhil Devanur, Janard- han Kulkarni, Gireeja Ranade, Pierre-Alexandre Blanche, Houman Rastegarfar, Madeleine Glick, and Daniel Kilper. 2016. Projector: Agile reconfigurable data center interconnect. InProceedings of the 2016 ACM SIGCOMM Conference. 216– 229

work page 2016
[19]

1958.Our Man in Havana

Graham Greene. 1958.Our Man in Havana. Heinemann

work page 1958
[20]

Lacy M Greening, Santanu S Dey, and Alan L Erera. 2025. Strengthening Dual Bounds for Multicommodity Capacitated Network Design with Unsplittable Flow Constraints.arXiv preprint arXiv:2512.25018(2025)

work page arXiv 2025
[21]

Mohammad Taghi Hajiaghayi, Jeong Han Kim, Tom Leighton, and Harald Räcke

work page
[22]

InProceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC ’05)

Oblivious routing in directed graphs with random demands. InProceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC ’05). ACM, 193–201. doi:10.1145/1060590.1060619

work page doi:10.1145/1060590.1060619
[23]

2001.The highly unofficial CPIP WG

The highly unofficial CPIP WG. 2001.The highly unofficial CPIP WG. Technical Report. University of Bergen. https://web.archive.org/web/20140215072548/http: //www.blug.linux.no/rfc1149/ Retrieved 24/12/2025

work page arXiv 2001
[24]

Hitchcock

Frank L. Hitchcock. 1941. The Distribution of a Product from Several Sources to Numerous Localities.Journal of Mathematics and Physics20, 1–4 (1941), 224–230

work page 1941
[25]

Yanping Huang, Youlong Cheng, Ankur Bapna, Orhan Firat, Dehao Chen, Mia Chen, HyoukJoong Lee, Jiquan Ngiam, Quoc V Le, Yonghui Wu, et al. 2019. Gpipe: Efficient training of giant neural networks using pipeline parallelism.Advances in neural information processing systems32 (2019)

work page 2019
[26]

David A Huffman. 2007. A method for the construction of minimum-redundancy codes.Proceedings of the IRE40, 9 (2007), 1098–1101

work page 2007
[27]

2017.The state of food security and nutrition in the world 2017

UNICEF IFAD et al. 2017.The state of food security and nutrition in the world 2017. FAO

work page 2017
[28]

1976.Queueing Systems, Volume II: Computer Applications

Leonard Kleinrock. 1976.Queueing Systems, Volume II: Computer Applications. John Wiley & Sons

work page 1976
[29]

Vanessa Lamb. 2023. Constructing the global sand crisis: Four reasons to inter- rogate crisis and scarcity in narrating extraction.The Extractive Industries and Society15 (2023), 101282

work page 2023
[30]

Jean-Pierre Luminet. 2021. Closed Timelike Curves, Singularities and Causality: A Survey from Gödel to Chronological Protection.Universe7, 1 (Jan. 2021), 12. doi:10.3390/universe7010012

work page doi:10.3390/universe7010012 2021
[31]

Carolina Elisabet Masin, Alejandra Duran, Cristina Susana Zalazar, and Maria Emilia Fernandez. 2024. Composting-vermicomposting of pigeon dropping waste: A contribution to the reduction of urban contamination. (2024)

work page 2024
[32]

Alberto Medina, Nina Taft, Kavé Salamatian, Supratik Bhattacharyya, and Christophe Diot. 2002. Traffic matrix estimation: existing techniques and new directions. InProceedings of the ACM SIGCOMM 2002 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication (SIGCOMM ’02). ACM, 161–174. doi:10.1145/633025.633041

work page doi:10.1145/633025.633041 2002
[33]

Deepak Narayanan, Mohammad Shoeybi, Jared Casper, Patrick LeGresley, Mostofa Patwary, Vijay Korthikanti, Dmitri Vainbrand, Prethvi Kashinkunti, Julie Bernauer, Bryan Catanzaro, et al. 2021. Efficient large-scale language model training on gpu clusters using megatron-lm. InProceedings of the International Conference for High Performance Computing, Networki...

work page 2021
[34]

Pascal Peduzzi, Josefine Reimer Lynggaard, and Stephanie Chuah. 2022. Sand and sustainability: 10 strategic recommendations to avert a crisis. (2022)

work page 2022
[35]

Leon Poutievski, Omid Mashayekhi, Joon Ong, Arjun Singh, Mukarram Tariq, Rui Wang, Jianan Zhang, Virginia Beauregard, Patrick Conner, Steve Gribble, et al. 2022. Jupiter evolving: transforming google’s datacenter network via optical circuit switches and software-defined networking. InProceedings of the ACM SIGCOMM 2022 Conference. 66–85

work page 2022
[36]

Hungry Beast Real Human Stories. 2010. Pigeons vs. Australian Internet. url: https://www.youtube.com/watch?v=ci2bFFGM8T8. Accessed: 24/12/2025

work page 2010
[37]

Grégory Salle. 2022. On the ‘global sand crisis’: From capital accumulation to ecological planning. (2022)

work page 2022
[38]

Stefan Schmid, Chen Avin, Christian Scheideler, Michael Borokhovich, Bernhard Haeupler, and Zvi Lotker. 2015. Splaynet: Towards locally self-adjusting networks. IEEE/ACM Transactions on Networking24, 3 (2015), 1421–1433

work page 2015
[39]

Claude E Shannon. 1949. Communication theory of secrecy systems.The Bell system technical journal28, 4 (1949), 656–715

work page 1949
[40]

Sharanpreet Singh, Jaswinder Singh, Amandeep Kaur, Jagroop Kaur, Adarsh Pal Vig, and Sartaj Ahmad Bhat. 2019. Nutrient recovery from pigeon dropping by using exotic earthworm Eisenia fetida.Sustainable Chemistry and Pharmacy12 (2019), 100126

work page 2019
[41]

Daniel Dominic Sleator and Robert Endre Tarjan. 1985. Self-adjusting binary search trees.Journal of the ACM (JACM)32, 3 (1985), 652–686

work page 1985
[42]

1999.Criptonomicon

Neal Stephenson. 1999.Criptonomicon. Avon

work page 1999
[43]

Google team. 2002. Google PigeonRank. url: http://www.google.com/technology/pigeonrank.html. Accessed: 24/12/2025

work page 2002
[44]

BBC News Technology. 2016. Pigeons vs. Australian Internet. url: Pigeon flies past broadband in data speed race. Accessed: 24/12/2025

work page 2016
[45]

Niren Tolsi. 2009. Winston the homing pigeon draws tweets of sup- port. url: https://mg.co.za/article/2009-09-10-winston-the-homing-pigeon-draws- tweets-of-support/. Accessed: 24/12/2025

work page 2009
[46]

2002.The vehicle routing problem

Paolo Toth and Daniele Vigo. 2002.The vehicle routing problem. SIAM

work page 2002
[47]

Gilbert S Vernam. 1926. Cipher printing telegraph systems: For secret wire and radio telegraphic communications.Journal of the AIEE45, 2 (1926), 109–115

work page 1926
[48]

Waitzman

D. Waitzman. 1990.A Standard for the Transmission of IP Datagrams on A vian Carriers. RFC 1149. RFC Editor. doi:10.17487/RFC1149

work page doi:10.17487/rfc1149 1990
[49]

Wikipedia contributors. 2014. Google Pigeon Protocol. https: //en.wikipedia.org/wiki/Google_Pigeon#:~:text=Google%20Pigeon%20is% 20the%20code,local%20listings%20in%20a%20search. [Online; accessed 24-December-2025]

work page 2014
[50]

Wikipedia contributors. 2025. Pigeon post. https://en.wikipedia.org/wiki/ Pigeon_post?utm_source=chatgpt.com [Online; accessed 24-December-2025]

work page 2025