Chewbacca Algorithm

This is the corrected algorithm.

    /**
     * Main Protocol Methods (listed in the Chord paper)
     */
    public ChordNode successor() {
      return finger[1].node;
    }

    public ChordNode find_successor(int id) {
      ChordNode np = find_predecessor(id);
      return np.successor();
    }

    public ChordNode find_predecessor(int id) {
      ChordNode np = this;
      while (!on_range(id, np._id+1, np.successor()._id)) {
        np = np.closest_preceding_finger(id);
      }
      return np;
    }

    public ChordNode closest_preceding_finger(int id) {
      for (int i=_m; i>=1; i--) {
        if (on_range(finger[i].node._id, this._id+1, id-1))
          return finger[i].node;
      }
      return this;
    }

    public void join(ChordNode np) {
      if (np != null) {
        init_finger_table(np);
        update_others();
      } else { // n is the only node in the network
        for (int i=1; i<=_m; i++) {
          finger[i].node = this;
        }       
        predecessor = this;
      }
    }

    public void init_finger_table(ChordNode np) {
      finger[1].node = np.find_successor(finger[1].start());
      predecessor = successor().predecessor;
      successor().predecessor = this;
      for (int i=1; i<=_m-1; i++) {
        if (on_range(finger[i+1].start(), this._id, finger[i].node._id-1)) {
          finger[i+1].node = finger[i].node;
        } else {
          finger[i+1].node = np.find_successor(finger[i+1].start());
          if (!on_range(finger[i+1].node._id,
                       finger[i+1].start(),
                       this._id)) {
			finger[i+1].node = this;
          }
        }
      }
    }

    public void update_others() {
      for (int i=1; i<=_m; i++) {
        ChordNode p = find_predecessor(wrap(this._id-pow2(i-1)+1));
        p.update_finger_table(this, i);
      }
    }

    public void update_finger_table(ChordNode s, int i) {
      if (s._id == this._id) {
        return;
      }
      if (on_range(s._id, this._id+1, finger[i].node._id)) {
        finger[i].node = s;
        ChordNode p = predecessor;
        p.update_finger_table(s, i);
      } 
    }

    public void leave() {
      if (this == successor()) {
	  	return; // it is the last node in the cloud
	  }
	  successor().predecessor = predecessor;
      for (int i=1; i<=_m; i++) {
        ChordNode p = find_predecessor(wrap(this._id-pow2(i-1)+1));
		p.remove_node(this, i, successor());
      }
    }

    public void remove_node(ChordNode n, int i, ChordNode repl) {
	  if (finger[i].node == n) {
	    finger[i].node = repl;
		predecessor.remove_node(n, i, repl);
	  }
	}
	 

Last updated Tue Dec 2 07:48:22 EST 2003