Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems
Lecture notes in computer science, 2001 · paper · Computer science
Presents Pastry, a decentralized, self-organizing system for locating objects and routing messages in large peer-to-peer networks, taking network locality into account. Experiments on an emulated network of up to 100,000 nodes confirm its scalability and efficiency.
Checked: PDF from rowstron.azurewebsites.net, fetched 4 Oct 2026. Page numbers are those of that PDF.
4 findings
Substance p.8 Node departure: "if L_i failed for ⌊|L|/2⌋ < i < 0, it requests the leaf set from L_{−⌊|L|/2⌋}". The lower bound has lost its minus sign (should be −⌊|L|/2⌋ < i < 0); as printed the range is empty.
- p. 8 Section 2.4, Node departure
if Li failed for ⌊|L|/2⌋ < i < 0
Judge's note: On the p.8 image there is no minus before ⌊|L|/2⌋ in the range, while the subscript L_{−⌊|L|/2⌋} right after it does show one. Negative indices mean smaller nodeIds (definition on p.5, −⌊|L|/2⌋ ≤ i ≤ ⌊|L|/2⌋). With |L|=16, 8 < i < 0 has no solution.
Second check: another model agreed
Report a problem with this finding
Substance The text says that without the heuristic (WTF) 'Pastry is able to locate the closest node 68% of the time, and one of the top two nodes 87% of the time', but the Fig. 8 WTF STANDARD bar shows about 59% (0 closer nodes) and about 78% (0 or 1 closer nodes).
- p. 17 Section 3.3, last paragraph
to locate the closest node 68% of the time, and one of the top two nodes 87% of the time
- p. 17 Fig. 8, WTF STANDARD bar
STANDARD
- p. 17 Section 3.3, last paragraph
Pastry is able to locate the closest node 68% of the time, and one of the top two nodes 87% of the time
- p. 17 Section 3.3 text
locate the closest node 68% of the time, and one of the top two nodes 87% of the time
Only the authors can say what is right here.
Judge's note: Read from the p017 page and the C027-b crop. In the WTF STANDARD bar, the '0' segment ends just below the 60 gridline and the '1' segment ends near 78. No STANDARD bar reaches 68%. The heuristic values (76%, 92%) do match the WTF ESTIMATION bar (about 75 and 92), so I am reading the axis correctly. The gap of about 9 points is too large for reading error. Only the authors can say whether the text or the figure is right.
Second check: another model agreed
Report a problem with this finding
Reference or label p.6: "routing performance degrades gradually with the number of recent node failures, as we will show experimentally in Section 3.1". Section 3.1 has no failure experiments; node failures are covered in Section 3.4 (Figs. 9–10).
- p. 6 Section 2.2, Routing performance
as we will show experimentally in Section 3.1
- p. 14 Section 3.1 Routing performance
3.1 Routing performance
- p. 6 Section 2.2, Routing performance
number of recent node failures, as we will show experimentally in Section 3.1
Judge's note: p.14–15: Section 3.1 (Figs. 4–6) covers hop counts and route distance with no failures. The Section 3 overview on p.14 says "in 3.4 the properties of Pastry under node failures are considered". The routing-under-failure results (Fig. 10) are on p.19 in Section 3.4. The pointer should be 3.4.
Second check: another model agreed
Report a problem with this finding
Reference or label p.9: "Experimental results in Section 3.2 demonstrate Pastry’s effectiveness in repairing the node state in the presences of node failures, and quantify the cost of this repair in terms of the number of messages exchanged". These results (Figs. 9–10, 57 RPCs per failed node) are in Section 3.4.
- p. 9 Section 2.4, end of Node departure
Experimental results in Section 3.2 demonstrate Pastry’s effectiveness in repairing the node state in the presences of node failures
- p. 19 Section 3.4, last paragraph
a total of 57 remote procedure calls were needed on average per failed node
- p. 9 end of Section 2.4
Experimental results in Section 3.2 demonstrate Pastry’s effectiveness in repairing
- p. 9 end of 2.4
in the presences of node failures
Judge's note: Section 3.2 ("Maintaining the network", p.16–17, Fig. 7) only examines routing-table locality after 5,000 nodes join, with no failures and no message counts. The repair results and "57 remote procedure calls ... per failed node" are on p.19 in Section 3.4. The "presences" typo is judged under C015.
Second check: another model agreed
Report a problem with this finding
26 minor (typos and the like; most checked by the judge only)
Reference or label Fig. 1 caption: "nodeId 10233102, b = 2, and l = 8". Elsewhere the leaf-set size is written |L| and l is the routing-table row index, so this should read |L| = 8.
- p. 4 Fig. 1 caption
b = 2, and l = 8
Judge's note: In the p.4 image the figure's leaf set has 8 entries (4 smaller, 4 larger). Section 2.2 (p.5) uses l as the row index (R_l^i, 0 ≤ l < ⌊128/b⌋) and |L| for the leaf-set size. The caption's "l" therefore clashes with the paper's own notation.
Second check: another model agreed
Report a problem with this finding
Wording Section 2 says Pastry can route "in less than ⌈log_{2^b} N⌉ steps", but Fig. 5 shows probability 0.1745 of exactly 5 hops for N=100,000, and ⌈log_16 100,000⌉ = 5. Section 3.1 calls ⌈log_{2^b} N⌉ the "maximum route length".
- p. 3 Section 2, paragraph 3
in less than ⌈log2bN⌉ steps under normal operation
- p. 15 Fig. 5
0.1745
- p. 14 Section 3.1
the maximum route length is (⌈log2bN⌉
Only the authors can say what is right here.
Judge's note: p.3 prints "in less than ⌈log_{2^b}N⌉ steps under normal operation". The Fig. 5 bar at 5 hops is 0.1745 (b=4, N=100,000). p.14 says "the maximum route length is (⌈log_{2^b}N⌉ (⌈log_{2^b} 100,000⌉ = 5)". So the strict "less than" is contradicted by the paper's own data; "at most" fits. This is a wording issue only.
Second check: another model agreed
Report a problem with this finding
Wording p.4: "with 10^9 nodes, the routing table contains on average 105 entries, and the expected number of routing hops in 7". The ⌈log_{2^b}N⌉×(2^b−1) and ⌈log_{2^b}N⌉ expressions in the same paragraph give 8 rows, 120 entries and 8 hops for b=4, while the 10^6 example (75 entries, 5 hops) does follow the ceiling.
- p. 4 Section 2.1, paragraph on choice of b
with 10^9 nodes, the routing table contains on average 105 entries, and the expected number of routing hops in 7
- p. 4 Section 2.1
the expected number of routing hops in 7
- p. 4
and the expected number of routing hops in 7.
Only the authors can say what is right here.
Judge's note: Checked on the p.4 image. log16(10^6)=4.98, which rounds up to 5, and 5×15=75 matches. log16(10^9)=7.47, which rounds up to 8, giving 8×15=120. The printed 105=7×15 and the 7 hops match rounding down. The text says "approximately" and "on average", so the authors should say which rule they used. The "in 7" → "is 7" typo noted here is judged under C006.
Second check: another model agreed
Report a problem with this finding
Wording Section 3.4 says "The results show that Pastry recovers all missing table entries", but in Fig. 9 the Level 2 'Repair' bar still has a white ('Missing' in the legend) segment, about the same size as in the Level 2 'No repair' bar.
- p. 19 Section 3.4, first paragraph
The results show that Pastry recovers all missing table entries
- p. 18 Fig. 9, Level 2 'Repair' bar
Repair
- p. 18 Fig. 9, Level 2, Repair bar
Missing
Only the authors can say what is right here.
Judge's note: I looked at Fig. 9 on page 18 at full size and in crop C031-c. At Levels 0 and 1 the white Missing segment shown in the No repair bars is gone from the Repair bars. At Level 2, both the No repair and Repair bars have a white segment from about 9.85 to 10.2, below the black Empty segment. In the legend white is 'Missing'. As drawn, the figure does not support 'all'. The white segment might be mis-shaded or might stand for entries left empty by sparseness, which the page 19 text discusses. Only the authors can say which, so this goes to them as a query.
Second check: another model agreed
Report a problem with this finding
Wording The text says "the increase in empty entries at levels 1 and 2 after the failures", but in Fig. 9 no black 'Empty' segment appears in any Level 1 bar; only Level 2 shows Empty entries.
- p. 19 Section 3.4
the increase in empty entries at levels 1 and 2 after the failures
- p. 18 Fig. 9, Level 1 bars
Level 1
Only the authors can say what is right here.
Judge's note: In Fig. 9 on page 18, all three Level 1 bars reach 15. The No repair bar is Optimal, then Sub-Optimal, then a white Missing segment from about 14.05 to 15, with no black segment. At Level 2 the black Empty segment does grow after the failures, from about 10.45 to about 10.2 at its lower edge. Any increase at Level 1 is either too small to see or is being counted under 'Missing'. Either way, the text and the legend do not match as published.
Second check: another model agreed
Report a problem with this finding
Typo Abstract reads "according to a to scalar proximity metric like the number of IP routing hops"; stray "to" (should be "according to a scalar proximity metric").
- p. 1 Abstract
according to a to scalar proximity metric
- p. 1
according to a to scalar proximity metric like the
Judge's note: Seen in the crop of the page-1 abstract: the extra "to" is printed, so this is not an extraction artefact.
Second check: none (judge only)
Report a problem with this finding
Typo Introduction p.2: "Several application have been built on top of Pastry to date" should be "Several applications".
- p. 2 Introduction, paragraph 3
Several application have been built
- p. 2 Introduction, paragraph 2
Several application have been built on top of Pastry to date
- p. 2 Introduction
Several application have been built on top of Pastry
Judge's note: Seen in the crop: the singular "application" is printed. The same sentence on p.7 correctly reads "Several applications have been built".
Second check: none (judge only)
Report a problem with this finding
Typo Section 2.2 notation: "D_l: the value of the l’s digit in the key D" should be "the l-th digit".
- p. 5 Section 2.2, notation
the value of the l’s digit in the key D
Judge's note: Seen on the p.5 image. The neighbouring definition uses "the i-th closest nodeId".
Second check: none (judge only)
Report a problem with this finding
Typo p.6: "is less than .02 and 0.006, respectively". The two probabilities are written with and without a leading zero.
- p. 6 Routing performance
is less than .02 and 0.006, respectively
Judge's note: Seen on the p.6 image. This is a cosmetic style inconsistency only.
Second check: none (judge only)
Report a problem with this finding
Typo p.7: "Since node A is assumed to be in proximity to the new node X, A’s neighborhood set to initialize X’s neighborhood set." The sentence has no main verb (e.g. "is used to initialize").
- p. 7 Section 2.4, Node arrival
A’s neighborhood set to initialize X’s neighborhood set
- p. 7 Node arrival
A’s neighborhood
Judge's note: Seen on the p.7 image: the words are missing on the printed page, so this is not an extraction loss.
Second check: none (judge only)
Report a problem with this finding
Typo p.7: "using a procedure describe below" should be "described below".
- p. 7 Section 2.4
using a procedure describe below
Judge's note: Seen on the p.7 image.
Second check: none (judge only)
Report a problem with this finding
Typo p.8: "asks that node for its leaf table", while the next sentence says "requests the leaf set" and the structure is defined as the leaf set.
- p. 8 Node departure
asks that node for its leaf table
Judge's note: Seen on the p.8 image. The term is inconsistent but the meaning is clear; p.9 similarly says "neighborhood tables".
Second check: none (judge only)
Report a problem with this finding
Typo p.9: "updates it own neighborhood set" should be "its own", and "in the presences of node failures" should be "presence".
- p. 9 Section 2.4, end
updates it own neighborhood set
- p. 9 Section 2.4, end
in the presences of node failures
Judge's note: Both errors are seen on the p.9 image.
Second check: none (judge only)
Report a problem with this finding
Typo Section 2.5 has three agreement errors: 'An application is expected to implements this function', 'The message follows a paths through nodes', 'show how we can maintains the property'.
- p. 9 Section 2.5
An application is expected to implements this function
- p. 9 Section 2.5, Locality in the routing table
The message follows a paths through nodes
- p. 9 Section 2.5
how we can maintains the property
- p. 9 Section 2.5
is expected to implements this function
Judge's note: I checked all three phrases in the p009 crops. Each appears as quoted. Fixes: 'implement', 'a path', 'maintain'.
Second check: none (judge only)
Report a problem with this finding
Typo Two number-agreement errors on p.11: 'the expected distance traveled by a messages' and 'Some peer-to-peer application we have built using Pastry replicate information'.
- p. 11 Section 2.5, Route locality
the expected distance traveled by a messages
- p. 11 Section 2.5, Locating the nearest among k nodes
Some peer-to-peer application we have built
- p. 11 Locating the nearest among k nodes
Some peer-to-peer application we have built using
- p. 11
the expected distance traveled by a messages during each successive rout-
Judge's note: Both phrases appear on the p011 page image as quoted. Fixes: 'a message' and 'applications'.
Second check: none (judge only)
Report a problem with this finding
Typo Grammatical slips in Section 2.6: 'arbitrary nodes failures' (p.12), 'able to communication with their immediate neighbors' and 'If isolated Pastry overlays exists' (p.13).
- p. 12 Section 2.6
arbitrary nodes failures
- p. 13 Section 2.6
able to communication with their immediate neighbors
- p. 13 Section 2.6
If isolated Pastry overlays exists
Judge's note: All three are on the page images (p012 crop, p013 full page). Fixes: 'node failures', 'communicate', 'exist'.
Second check: none (judge only)
Report a problem with this finding
Typo The experimental setup names the operating system as 'running True64 UNIX, version 4.0F'.
- p. 13 Section 3, experimental setup
running True64 UNIX
Only the authors can say what is right here.
Judge's note: Rests on outside knowledge: the Compaq operating system is spelled 'Tru64 UNIX'. The p013 image does read 'True64 UNIX'.
Second check: none (judge only)
Report a problem with this finding
Typo Subject-verb disagreement: 'Figure 4 show the average number of routing hops taken'.
- p. 14 Section 3.1
Figure 4 show the average number of routing hops
Judge's note: Visible on the p014 image. Should read 'shows'.
Second check: none (judge only)
Report a problem with this finding
Typo Unbalanced parentheses: 'the maximum route length is (⌈log_{2^b} N⌉ (⌈log_{2^b} 100,000⌉ = 5), as expected.' Two parentheses open and only one closes.
- p. 14 Section 3.1
(dlog2b Ne (dlog2b 100; 000e = 5)
Judge's note: On the p014 image the opening parenthesis before ⌈log N⌉ is never closed. The value is consistent: log base 16 of 100,000 is about 4.15, which rounds up to 5.
Second check: none (judge only)
Report a problem with this finding
Typo The text says '(labeled “Complete routing tables”)', but the Fig. 6 legend reads 'Complete routing table'.
- p. 15 Section 3.1 vs Fig. 6 legend
(labeled “Complete routing tables”)
Judge's note: On the p015 image the legend reads 'Complete routing table' (singular). The difference is cosmetic and the meaning is clear.
Second check: none (judge only)
Report a problem with this finding
Typo Typo: 'less than 1 entry per level of the routing able is not the best choice'. 'able' should be 'table'.
- p. 17 Section 3.2, last paragraph
per level of the routing able is not the best choice
- p. 17 Section 3.2
of the routing able is not the best choice
Judge's note: Visible on the p017 image.
Second check: none (judge only)
Report a problem with this finding
Typo Number agreement: 'With the heuristic routing option, this figures increase to 76% and 92%'. Should be 'these figures'.
- p. 17 Section 3.3
this figures increase to 76% and 92%
Judge's note: Visible on the p017 image.
Second check: none (judge only)
Report a problem with this finding
Typo Typo in Section 3.4: "the stale routing table state causes as significant deterioration of route quality"; it should read "a significant".
- p. 19 Section 3.4
causes as significant deterioration
- p. 19 Section 3.4
causes as significant deterioration of route
Judge's note: I checked the page 19 image, and the text reads 'causes as significant deterioration'.
Second check: none (judge only)
Report a problem with this finding
Typo Typo in Section 4: "and the emphasis in on self-organization"; it should read "is on".
- p. 20 Section 4
the emphasis in on self-organization
Judge's note: I checked the page 20 image, and the text reads 'the emphasis in on self-organization'.
Second check: none (judge only)
Report a problem with this finding
Typo Page 20 says "Lampson's Global Naming System (GNS) [16]", but the cited reference [16] is titled "Designing a global name service".
- p. 20 Section 4
Lampson’s Global Naming System (GNS) [16]
- p. 22 Reference 16
Designing a global name service
Judge's note: Page 20 expands the acronym as 'Global Naming System', while reference 16 on page 22 has the title 'Designing a global name service'. The mismatch is visible inside the paper itself. It may be a loose paraphrase, so it is recorded as a minor consistency point.
Second check: none (judge only)
Report a problem with this finding
Typo Reference 27 gives the report number with a doubled slash: "Technical Report UCB//CSD-01-1141".
- p. 22 Reference 27
UCB//CSD-01-1141
Only the authors can say what is right here.
Judge's note: Rests on outside knowledge: Berkeley technical reports use the format UCB/CSD-01-1141 with a single slash. The crop of page 22 confirms that the doubled slash is printed and is not an extraction artefact.
Second check: none (judge only)