{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/40506"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/40506","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"Huge networks, tiny faulty nodes","abstract":"Can one build, and efficiently use, networks of arbitrary size and topology using a \"standard\" node whose resources, in terms of memory and reliability, do not need to scale up with the complexity and size of the network? This thesis addresses two important aspects of this question. The first is whether one can achieve efficient connectivity despite the presence of a constant probability of faults per node/link. Efficient connectivity means (informally) having every pair of regions connected by a constant fraction of the independent, entirely non-faulty paths that would be present if the entire network were fault free - even at distances where each path has only a vanishingly small probability of being fault-free. The answer is yes, as long as some very mild topological conditions on the high level structure of the network are met - informally, if the network is not too \"thin\" and if it does not contain too many large \"holes\". The results go against some established \"empyrical wisdom\" in the networking community. The second issue addressed by this thesis is whether one can route efficiently on a network of arbitrary size and topology using only a constant number c of bits/node (even if c is less than the logarithm of the network's size!). Routing efficiently means (informally) that message delivery should only stretch the delivery path by a constant factor. The answer again is yes, as long as the volume of the network grows only polynomially with its radius (otherwise, we run into established lower bounds). This effectively captures every network one may build in a universe (like our own) with finite dimensionality using links of a fixed, maximum length and nodes with a fixed, minimum volume. The results extend the current results for compact routing, allowing one to route efficiently on a much larger class of networks than had previously been known, with many fewer bits.","abstract_html":"Can one build, and efficiently use, networks of arbitrary size and topology using a "standard" node whose resources, in terms of memory and reliability, do not need to scale up with the complexity and size of the network? This thesis addresses two important aspects of this question. The first is whether one can achieve efficient connectivity despite the presence of a constant probability of faults per node/link. Efficient connectivity means (informally) having every pair of regions connected by a constant fraction of the independent, entirely non-faulty paths that would be present if the entire network were fault free - even at distances where each path has only a vanishingly small probability of being fault-free. The answer is yes, as long as some very mild topological conditions on the high level structure of the network are met - informally, if the network is not too "thin" and if it does not contain too many large "holes". The results go against some established "empyrical wisdom" in the networking community. The second issue addressed by this thesis is whether one can route efficiently on a network of arbitrary size and topology using only a constant number c of bits/node (even if c is less than the logarithm of the network's size!). Routing efficiently means (informally) that message delivery should only stretch the delivery path by a constant factor. The answer again is yes, as long as the volume of the network grows only polynomially with its radius (otherwise, we run into established lower bounds). This effectively captures every network one may build in a universe (like our own) with finite dimensionality using links of a fixed, maximum length and nodes with a fixed, minimum volume. The results extend the current results for compact routing, allowing one to route efficiently on a much larger class of networks than had previously been known, with many fewer bits.","abstract_has_math":false,"creators":["Peserico, Enoch (Peserico Stecchini Negri de Salvi)"],"institution":"Massachusetts Institute of Technology","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.","school":null,"contributors":[],"advisors":["Larry Rduolph."],"committee_chairs":[],"committee_members":[],"year":2007,"date_issued":"2007","date_published":"2007","updated_at":"2026-07-22T22:22:16Z","subjects":["Electrical Engineering and Computer Science."],"languages":["eng"],"rights":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."],"rights_urls":["http://dspace.mit.edu/handle/1721.1/7582"],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/1721.1/40506","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Larry Rduolph."]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."]},{"key":"dc:contributor.other","label":"Dc Contributor Other","values":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."]},{"key":"dc:creator","label":"Author","values":["Peserico, Enoch (Peserico Stecchini Negri de Salvi)"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2008-02-27T22:39:33Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2008-02-27T22:39:33Z"]},{"key":"dc:date.issued","label":"Date","values":["2007"]},{"key":"dc:publisher","label":"Institution","values":["Massachusetts Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Electrical Engineering and Computer Science."]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://dspace.mit.edu/handle/1721.1/7582"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/1721.1/40506"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2007.","Includes bibliographical references (p. 87-91)."]},{"key":"dc:description.abstract","label":"Abstract","values":["Can one build, and efficiently use, networks of arbitrary size and topology using a \"standard\" node whose resources, in terms of memory and reliability, do not need to scale up with the complexity and size of the network? This thesis addresses two important aspects of this question. The first is whether one can achieve efficient connectivity despite the presence of a constant probability of faults per node/link. Efficient connectivity means (informally) having every pair of regions connected by a constant fraction of the independent, entirely non-faulty paths that would be present if the entire network were fault free - even at distances where each path has only a vanishingly small probability of being fault-free. The answer is yes, as long as some very mild topological conditions on the high level structure of the network are met - informally, if the network is not too \"thin\" and if it does not contain too many large \"holes\". The results go against some established \"empyrical wisdom\" in the networking community. The second issue addressed by this thesis is whether one can route efficiently on a network of arbitrary size and topology using only a constant number c of bits/node (even if c is less than the logarithm of the network's size!). Routing efficiently means (informally) that message delivery should only stretch the delivery path by a constant factor. The answer again is yes, as long as the volume of the network grows only polynomially with its radius (otherwise, we run into established lower bounds). This effectively captures every network one may build in a universe (like our own) with finite dimensionality using links of a fixed, maximum length and nodes with a fixed, minimum volume. The results extend the current results for compact routing, allowing one to route efficiently on a much larger class of networks than had previously been known, with many fewer bits."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Ph.D."]},{"key":"dc:title","label":"Title","values":["Huge networks, tiny faulty nodes"]}]}],"canonical_facts":{"dc:contributor.advisor":["Larry Rduolph."],"dc:contributor.department":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."],"dc:contributor.other":["Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science."],"dc:creator":["Peserico, Enoch (Peserico Stecchini Negri de Salvi)"],"dc:date.accessioned":["2008-02-27T22:39:33Z"],"dc:date.available":["2008-02-27T22:39:33Z"],"dc:date.issued":["2007"],"dc:description":["Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2007.","Includes bibliographical references (p. 87-91)."],"dc:description.abstract":["Can one build, and efficiently use, networks of arbitrary size and topology using a \"standard\" node whose resources, in terms of memory and reliability, do not need to scale up with the complexity and size of the network? This thesis addresses two important aspects of this question. The first is whether one can achieve efficient connectivity despite the presence of a constant probability of faults per node/link. Efficient connectivity means (informally) having every pair of regions connected by a constant fraction of the independent, entirely non-faulty paths that would be present if the entire network were fault free - even at distances where each path has only a vanishingly small probability of being fault-free. The answer is yes, as long as some very mild topological conditions on the high level structure of the network are met - informally, if the network is not too \"thin\" and if it does not contain too many large \"holes\". The results go against some established \"empyrical wisdom\" in the networking community. The second issue addressed by this thesis is whether one can route efficiently on a network of arbitrary size and topology using only a constant number c of bits/node (even if c is less than the logarithm of the network's size!). Routing efficiently means (informally) that message delivery should only stretch the delivery path by a constant factor. The answer again is yes, as long as the volume of the network grows only polynomially with its radius (otherwise, we run into established lower bounds). This effectively captures every network one may build in a universe (like our own) with finite dimensionality using links of a fixed, maximum length and nodes with a fixed, minimum volume. The results extend the current results for compact routing, allowing one to route efficiently on a much larger class of networks than had previously been known, with many fewer bits."],"dc:description.degree":["Ph.D."],"dc:identifier.uri":["http://hdl.handle.net/1721.1/40506"],"dc:language.iso":["eng"],"dc:publisher":["Massachusetts Institute of Technology"],"dc:rights":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."],"dc:rights.uri":["http://dspace.mit.edu/handle/1721.1/7582"],"dc:subject":["Electrical Engineering and Computer Science."],"dc:title":["Huge networks, tiny faulty nodes"],"dc:type":["Thesis"]},"updated_at":"2026-07-22T22:22:16Z"}