References for Sensornet filesystem

OceanStore

• tapestry - overlay routing and location
• fragmentation, replication, erasure coding
• read-only storage (modify by version creation), naming via GUID
• byzantine update (see Castro & Liskov)
  

• uses file update model based on Bayou. no leases or locks - application must use predicate-guarded updates.
• caching and update routing (???) sec. 3.4
• object implemented as B-tree. metadata appended to top block; version i+1 is sparse update to version i. (copy-on-write)
• storage overhead = root block size (constant) + erasure coding rate.
• NFS mapping - file writes trivial, directory writes handled by predicate if-not-modified-since.
• performance - wide-area read better than NFS (4x), write worse (3x)

• description of Plaxton's method.  Object root node (fixed based on name suffix) and pointer trails from cached copies up to root node.  Can route around failure (hill-climbing algorithm - "sidestep" on failure of next path up)
• tapestry uses multiple roots per object by running the hash function (to compute object name) k times, with a different fixed salt added each time.
• incremental computation of unique root node for an object - "surrogate routing"

XFS

Chord

Bayou

• client-server, client may not have space for simultaneous storage of all data it wants access to.
• designed for mixed, possibly very weak connectivity (modem, floppy)
• node can act as both client and server, can access replicas if original not available
• writes have a predicate, the dependency set, and an application-specific procedure, the mergeproc that is invoked when the dependency set detects a write conflict.
• Ficus and Coda have similar but simpler mechanisms for resolving conflicts in an application-dependent way.
• primary server per database, function is to serialize writes and commit them
• provides both tentative and committed view of database for reads.  reads can also specify a max age parameter to bound inconsistency.
  
• anti-entropy protocol (demers et al) for reconciliation of writes
  

• describes version vectors for maintaining global write commit ordering among servers
• write protocol also used to add/drop servers from network - version vectors disambiguate case where two servers disagree about the presence of a third server in the network.
  

CFS

SFS

Plaxton's tree algorithm

All Cache (COMA)

Anti-entropy, epidemic protocols

• for gossip algorithms, if distribution of neighbor pick is spatial with pdf  between d^-(D+1) and d^-(2D), where D is dimensioniality of mesh, then convergence time and traffic are both logN
  
• for constructing a spatially localized distribution, use a distribution that is a function of Q(d), where Q(d) is the number of sites at a distance of d or less.  1/Q(d)^2 or 1/dQ(d) work.
• push-pull gossip is best

Lazy replication

Liskov - Harp, byzantine fault tolerance

Other papers to read

• Eugene Gendelman, Lubomir F. Bic, and Michael B. Dillencourt. LDFS: A Fault-Tolerant Local Disk-Based File System for Mobile Agents. Department of Information and Computer Science, University of California, Irvine, CA. TR 01-21. http://citeseer.ist.psu.edu/449381.html
• S. Soltis, G. Erickson, K. Preslan, M. O'Keefe, and T. Ruwart, "The Global File System: A File System for Shared Disk Storage," submitted to the IEEE Transactions on Parallel and Distributed Systems, October 1997. http://citeseer.ist.psu.edu/soltis97global.html
• Y. Saito, C. Karamonolis, M. Karlsson, and M. Mahalingam. Taming aggressive replication in the Pangaea wide-area file system. In Proc. of the 5th Symp. on Operating Systems Design and Implementation. Dec. 2002. http://citeseer.ist.psu.edu/saito02taming.html
• A. Adya, W. J. Bolosky, M. Castro, R. Chaiken, G. Cermak, J. R. Douceur, J. Howell, J. R. Lorch, M. Theimer, R. P. Wattenhofer, "FARSITE: Federated, Available, and Reliable Storage for an Incompletely Trusted Environment", 5th OSDI, Dec 2002. http://citeseer.ist.psu.edu/adya02farsite.html

Spatial databases

@article{615206,
 author = {Ralf Hartmut G\&\#252;ting},
 title = {An introduction to spatial database systems},
 journal = {The VLDB Journal},
 volume = {3},
 number = {4},
 year = {1994},
 issn = {1066-8888},
 pages = {357--399},
 publisher = {Springer-Verlag New York, Inc.},
 }

Distributed database indices

Brigitte Kroll and Peter Widmayer. Balanced distributed search trees do not exist. In Algorithms and Data Structures, 4th International Workshop, volume 955 of Lecture Notes in Computer Science, pages 50--61, Kingston, Ontario, Canada, 16--18 August 1995. http://citeseer.ist.psu.edu/article/kroll95balanced.html (cached)

@inproceedings{ bozanis-ldt,
  author = "Panayiotis Bozanis and Yannis Manolopoulos",
  title = "LDT: a Logarithmic Distributed Search",
  booktitle = "Proceedings 4th Workshop on Distributed Data and Structures (WDAS'02)",
  city = "Paris",
  year = 2002,
  url = "citeseer.ist.psu.edu/527887.html" }

Gnutella

Other