7
$\begingroup$

I am currently researching for my diploma thesis in computer science with a topic in the area of distributed hash tables. Naturally, I came to the question were the term distributed hash table came from. (I know it is not rocket science to just derive it from distributing a hash table, but somebody somewhere must have come up with it).

Most papers I read referred to the original paper on consistent hashing and one of the first algorithms making use of it (e.g Chord). I know that there was a lot of research on distributed databases in the 80s, so I figure that the term, or maybe the idea behind it, should be older than ~15 years.

The motivation behind this question is that knowing an earlier date and maybe another term for a similar idea would possibly widen the range of useful information I could gather for my research. For example, what have others done that is similar to what I want to do and where have they failed. Etc. etc.

I tried to find more on this subject using Structured Overlay Networks as a search keyword, but the resulting definitions/papers are also quite young, which leaves me with the impression that the research topic might not be so old after all.

Does anybody of you know of earlier research (maybe pre-90s?) in the topics of distributed hash tables and/or structured overlay networks? I'd be glad to hear some keywords which could lead me to more historic papers.

$\endgroup$
6
  • $\begingroup$ Have you tried sifting through a google search restricted to earlier decades? The first hit for me, "Design and implementation of DDH: A distributed dynamic hashing algorithm", is from 1993. $\endgroup$
    – Raphael
    Jul 23, 2012 at 9:53
  • $\begingroup$ Good call, I haven't checked that source. Will do that now. $\endgroup$
    – evnu
    Jul 23, 2012 at 9:54
  • 1
    $\begingroup$ One of the earliest publications that I have found using the term DHT is the original publication on the Linda coordination language (1986), which attributes the term to Rob Bjornson. $\endgroup$
    – evnu
    Jul 23, 2012 at 10:16
  • 2
    $\begingroup$ Great! You might be able to move backwards from there via references. If/when you find something that satisfies you, make sure to post the result as an answer. $\endgroup$
    – Raphael
    Jul 23, 2012 at 10:23
  • $\begingroup$ Did you find its origin by any chance? $\endgroup$
    – Merbs
    Jan 16, 2013 at 7:55

1 Answer 1

5
$\begingroup$

The term can at least be traced back to a publication by Carriero, Gelernter and Leichter from 1986: Distributed Datastructures in Linda[Lin86]. The paper attributes the term to Rob Bjornson (which I believe to be this guy), but only cites personal communication as their mean of learning the term. [Lin86] also refers D. Gelernter: Dynamic global name spaces on network computers. (1984), which is said to propose an implementation. I didn't find the paper, so I can not say if this is true. Another report (which I didn't find as well) by Leichter is said to discuss the implementation further: Implementing the Unimplementable -- Algorithms for Linda's Tuple Space.

The source in Linda seems to be a dead end, but was the oldest source of the term that I could find. I think it could be attributed with the term, but I may be confuted. If we assume that Bjornson came up with the term, at least the time frame would be fitting. Bjornson started his work in 1984, so if he is attributed with the term, the term's origin would neatly fit into the time were the Linda papers above were written.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.