Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
Add chord example for java
authorSamuel Lepetit <samuel.lepetit@inria.fr>
Fri, 18 May 2012 13:03:32 +0000 (15:03 +0200)
committerSamuel Lepetit <samuel.lepetit@inria.fr>
Fri, 18 May 2012 13:04:38 +0000 (15:04 +0200)
12 files changed:
CMakeLists.txt
examples/chord/Chord.java [new file with mode: 0644]
examples/chord/ChordTask.java [new file with mode: 0644]
examples/chord/Common.java [new file with mode: 0644]
examples/chord/FindSuccessorAnswerTask.java [new file with mode: 0644]
examples/chord/FindSuccessorTask.java [new file with mode: 0644]
examples/chord/GetPredecessorAnswerTask.java [new file with mode: 0644]
examples/chord/GetPredecessorTask.java [new file with mode: 0644]
examples/chord/Node.java [new file with mode: 0644]
examples/chord/NotifyTask.java [new file with mode: 0644]
examples/chord/chord.xml [new file with mode: 0644]
examples/chord/chord100.xml [new file with mode: 0644]

index f097deb..660e1aa 100644 (file)
@@ -110,7 +110,14 @@ set(JMSG_JAVA_SRC
 )
 
 set(JAVA_EXAMPLES
-
+  examples/chord/Chord.java
+  examples/chord/Common.java
+  examples/chord/Node.java
+  examples/chord/ChordTask.java
+       examples/chord/FindSuccessorAnswerTask.java
+       examples/chord/FindSuccessorTask.java
+       examples/chord/GetPredecessorAnswerTask.java
+       examples/chord/NotifyTask.java
        examples/mutualExclusion/centralized/MutexCentral.java
        examples/mutualExclusion/centralized/GrantTask.java
        examples/mutualExclusion/centralized/Coordinator.java
@@ -238,11 +245,12 @@ add_custom_command(
        DEPENDS ${JAVA_EXAMPLES}
        COMMAND ${JAVA_COMPILE} -d ${CMAKE_HOME_DIRECTORY}/examples -cp ${CMAKE_HOME_DIRECTORY}/simgrid.jar ${CMAKE_HOME_DIRECTORY}/examples/basic/*.java  
        COMMAND ${JAVA_COMPILE} -d ${CMAKE_HOME_DIRECTORY}/examples -cp ${CMAKE_HOME_DIRECTORY}/simgrid.jar ${CMAKE_HOME_DIRECTORY}/examples/async/*.java
-       COMMAND ${JAVA_COMPILE} -d ${CMAKE_HOME_DIRECTORY}/examples -cp ${CMAKE_HOME_DIRECTORY}/simgrid.jar ${CMAKE_HOME_DIRECTORY}/examples/pingPong/*.java
+       COMMAND ${JAVA_COMPILE} -d ${CMAKE_HOME_DIRECTORY}/examples -cp ${CMAKE_HOME_DIRECTORY}/simgrid.jar ${CMAKE_HOME_DIRECTORY}/examples/chord/*.java
        COMMAND ${JAVA_COMPILE} -d ${CMAKE_HOME_DIRECTORY}/examples -cp ${CMAKE_HOME_DIRECTORY}/simgrid.jar ${CMAKE_HOME_DIRECTORY}/examples/commTime/*.java
+         COMMAND ${JAVA_COMPILE} -d ${CMAKE_HOME_DIRECTORY}/examples -cp ${CMAKE_HOME_DIRECTORY}/simgrid.jar ${CMAKE_HOME_DIRECTORY}/examples/master_slave_bypass/*.java
+         COMMAND ${JAVA_COMPILE} -d ${CMAKE_HOME_DIRECTORY}/examples -cp ${CMAKE_HOME_DIRECTORY}/simgrid.jar ${CMAKE_HOME_DIRECTORY}/examples/master_slave_kill/*.java
        COMMAND ${JAVA_COMPILE} -d ${CMAKE_HOME_DIRECTORY}/examples -cp ${CMAKE_HOME_DIRECTORY}/simgrid.jar ${CMAKE_HOME_DIRECTORY}/examples/mutualExclusion/centralized/*.java                                 
-       COMMAND ${JAVA_COMPILE} -d ${CMAKE_HOME_DIRECTORY}/examples -cp ${CMAKE_HOME_DIRECTORY}/simgrid.jar ${CMAKE_HOME_DIRECTORY}/examples/master_slave_bypass/*.java
-       COMMAND ${JAVA_COMPILE} -d ${CMAKE_HOME_DIRECTORY}/examples -cp ${CMAKE_HOME_DIRECTORY}/simgrid.jar ${CMAKE_HOME_DIRECTORY}/examples/master_slave_kill/*.java
+       COMMAND ${JAVA_COMPILE} -d ${CMAKE_HOME_DIRECTORY}/examples -cp ${CMAKE_HOME_DIRECTORY}/simgrid.jar ${CMAKE_HOME_DIRECTORY}/examples/pingPong/*.java
        COMMAND ${JAVA_COMPILE} -d ${CMAKE_HOME_DIRECTORY}/examples -cp ${CMAKE_HOME_DIRECTORY}/simgrid.jar ${CMAKE_HOME_DIRECTORY}/examples/startKillTime/*.java
 )
 
diff --git a/examples/chord/Chord.java b/examples/chord/Chord.java
new file mode 100644 (file)
index 0000000..66f8e1b
--- /dev/null
@@ -0,0 +1,21 @@
+package chord;
+
+import org.simgrid.msg.Msg;
+
+public class Chord {
+       public static void main(String[] args) {
+               /* initialize the MSG simulation. Must be done before anything else (even logging). */
+               Msg.init(args);
+       if(args.length < 2) {
+               Msg.info("Usage   : Chord platform_file deployment_file");
+               Msg.info("example : Chord platform.xml deployment.xml");
+               System.exit(1);
+       }
+               /* construct the platform and deploy the application */
+               Msg.createEnvironment(args[0]);
+               Msg.deployApplication(args[1]);
+                       
+               /*  execute the simulation. */
+        Msg.run();             
+       }
+}
diff --git a/examples/chord/ChordTask.java b/examples/chord/ChordTask.java
new file mode 100644 (file)
index 0000000..b740fea
--- /dev/null
@@ -0,0 +1,20 @@
+package chord;
+
+import org.simgrid.msg.Task;
+
+import chord.Common;
+/**
+ * Base class for all Tasks in Chord.
+ */
+public class ChordTask extends Task {
+       public String issuerHostName;
+       public String answerTo;
+       public ChordTask() {
+               this(null,null);
+       }
+       public ChordTask(String issuerHostName, String answerTo) {
+               super(null, Common.COMP_SIZE, Common.COMM_SIZE);
+               this.issuerHostName = issuerHostName;
+               this.answerTo = answerTo;
+       }
+}
diff --git a/examples/chord/Common.java b/examples/chord/Common.java
new file mode 100644 (file)
index 0000000..d12f10b
--- /dev/null
@@ -0,0 +1,17 @@
+package chord;
+/**
+ * Common constants used over the simulation
+ */
+public class Common {
+       public final static int COMM_SIZE = 10;
+       public final static int COMP_SIZE = 0;
+       
+       public final static int NB_BITS = 24;
+       public final static int NB_KEYS = 16777216;
+       public final static int TIMEOUT = 50;
+       public final static int MAX_SIMULATION_TIME = 1000;
+       public final static int PERIODIC_STABILIZE_DELAY = 20;
+       public final static int PERIODIC_FIX_FINGERS_DELAY = 120;
+       public final static int PERIODIC_CHECK_PREDECESSOR_DELAY = 120;
+       public final static int PERIODIC_LOOKUP_DELAY = 10;
+}
diff --git a/examples/chord/FindSuccessorAnswerTask.java b/examples/chord/FindSuccessorAnswerTask.java
new file mode 100644 (file)
index 0000000..dea6ce1
--- /dev/null
@@ -0,0 +1,10 @@
+package chord;
+
+public class FindSuccessorAnswerTask extends ChordTask {
+       public int answerId;
+
+       public FindSuccessorAnswerTask(String issuerHostname, String answerTo, int answerId) {
+               super(issuerHostname,answerTo);
+               this.answerId = answerId;
+       }
+}
diff --git a/examples/chord/FindSuccessorTask.java b/examples/chord/FindSuccessorTask.java
new file mode 100644 (file)
index 0000000..2b068f0
--- /dev/null
@@ -0,0 +1,10 @@
+package chord;
+
+public class FindSuccessorTask extends ChordTask {
+       public int requestId;
+       
+       public FindSuccessorTask(String issuerHostname, String answerTo,  int requestId) {
+               super(issuerHostname, answerTo);
+               this.requestId = requestId;
+       }
+}
diff --git a/examples/chord/GetPredecessorAnswerTask.java b/examples/chord/GetPredecessorAnswerTask.java
new file mode 100644 (file)
index 0000000..493bffa
--- /dev/null
@@ -0,0 +1,9 @@
+package chord;
+
+public class GetPredecessorAnswerTask extends ChordTask {
+       public int answerId;
+       public GetPredecessorAnswerTask(String issuerHostname, String answerTo, int answerId) {
+               super(issuerHostname,answerTo);
+               this.answerId = answerId;
+       }
+}
diff --git a/examples/chord/GetPredecessorTask.java b/examples/chord/GetPredecessorTask.java
new file mode 100644 (file)
index 0000000..42dd2e9
--- /dev/null
@@ -0,0 +1,7 @@
+package chord;
+
+public class GetPredecessorTask extends ChordTask {
+       public GetPredecessorTask(String issuerHostName, String answerTo) {
+               super(issuerHostName, answerTo);
+       }
+}
diff --git a/examples/chord/Node.java b/examples/chord/Node.java
new file mode 100644 (file)
index 0000000..2727dd9
--- /dev/null
@@ -0,0 +1,471 @@
+package chord;
+
+import org.simgrid.msg.Comm;
+import org.simgrid.msg.Host;
+import org.simgrid.msg.Msg;
+import org.simgrid.msg.MsgException;
+import org.simgrid.msg.Process;
+import org.simgrid.msg.Task;
+import org.simgrid.msg.TimeoutException;
+/**
+ * Node data
+ */
+public class Node extends Process {
+       /**
+        * Node id
+        */
+       protected int id;
+       /**
+        * Node mailbox
+        */
+       protected String mailbox;
+       /**
+        * Predecessor id
+        */
+       protected int predId;
+       /**
+        * Predecessor mailbox
+        */
+       protected String predMailbox;
+       /**
+        * Index of the next finger to fix
+        */
+       protected int nextFingerToFix;
+       /**
+        * Current communication
+        */
+       protected Comm commReceive;
+       /**
+        * Last time I changed a finger or my predecessor
+        */
+       protected double lastChangeDate;
+       /**
+        * Node fingers
+        */
+       int fingers[];
+       /**
+        * Constructor
+        */
+       public Node(Host host, String name, String[] args) {
+               super(host,name,args);
+       }
+       @Override
+       public void main(String[] args) throws MsgException {
+               if (args.length != 2 && args.length != 4) {
+                       Msg.info("You need to provide 2 or 4 arguments.");
+                       return; 
+               }
+               double initTime = Msg.getClock();
+               int i;
+               boolean joinSuccess = false;
+               double deadline;
+               
+               double nextStabilizeDate = initTime + Common.PERIODIC_STABILIZE_DELAY;
+               double nextFixFingersDate = initTime + Common.PERIODIC_FIX_FINGERS_DELAY;
+               double nextCheckPredecessorDate = initTime + Common.PERIODIC_CHECK_PREDECESSOR_DELAY;
+               double nextLookupDate = initTime + Common.PERIODIC_LOOKUP_DELAY;
+               
+               id = Integer.valueOf(args[0]);
+               mailbox = Integer.toString(id);
+
+               fingers = new int[Common.NB_BITS];
+               for (i = 0; i < Common.NB_BITS; i++) {
+                       fingers[i] = -1;
+                       setFinger(i,this.id);
+               }
+               
+               //First node
+               if (args.length == 2) {
+                       deadline = Integer.valueOf(args[1]);
+                       create();
+                       joinSuccess = true;
+               }
+               else {
+                       int knownId = Integer.valueOf(args[1]);
+                       deadline = Integer.valueOf(args[3]);
+                       //Msg.info("Hey! Let's join the system with the id " + id + ".");
+                       
+                       joinSuccess = join(knownId);
+               }
+               if (joinSuccess) {
+                       double currentClock = Msg.getClock();
+                       while (currentClock < (initTime + deadline) && currentClock < Common.MAX_SIMULATION_TIME) {
+                               if (commReceive == null) {
+                                       commReceive = Task.irecv(this.mailbox);
+                               }
+                               try {
+                                       if (!commReceive.test()) {
+                                               if (currentClock >= nextStabilizeDate) {
+                                                       stabilize();
+                                                       nextStabilizeDate = Msg.getClock() + Common.PERIODIC_STABILIZE_DELAY;
+                                               }
+                                               else if (currentClock >= nextFixFingersDate) {
+                                                       fixFingers();
+                                                       nextFixFingersDate = Msg.getClock() + Common.PERIODIC_FIX_FINGERS_DELAY;
+                                               }
+                                               else if (currentClock >= nextCheckPredecessorDate) {
+                                                       this.checkPredecessor();
+                                                       nextCheckPredecessorDate = Msg.getClock() + Common.PERIODIC_CHECK_PREDECESSOR_DELAY;
+                                               }
+                                               else if (currentClock >= nextLookupDate) {
+                                                       this.randomLookup();
+                                                       nextLookupDate = Msg.getClock() + Common.PERIODIC_LOOKUP_DELAY;
+                                               }
+                                               else {
+                                                       waitFor(5);
+                                               }
+                                               currentClock = Msg.getClock();
+                                       }
+                                       else {
+                                               handleTask(commReceive.getTask());
+                                               currentClock = Msg.getClock();
+                                               commReceive = null;
+                                               
+                                       }
+                               }
+                               catch (Exception e) {
+                                       
+                               }
+                               
+                       }
+                       leave();
+                       if (commReceive != null) {
+                               commReceive = null;
+                       }
+               }
+               else {
+                       Msg.info("I couldn't join the ring");
+               }
+       }
+       void handleTask(Task task) {
+               if (task instanceof FindSuccessorTask) {
+                       FindSuccessorTask fTask = (FindSuccessorTask)task;
+                       Msg.debug("Receiving a 'Find Successor' request from " + fTask.issuerHostName + " for id " + fTask.requestId);
+                       // is my successor the successor?
+                       if (isInInterval(fTask.requestId, this.id + 1, fingers[0])) {
+                               //Msg.info("Send the request to " + fTask.answerTo + " with answer " + fingers[0]);
+                               FindSuccessorAnswerTask answer = new FindSuccessorAnswerTask(host.getName(), mailbox, fingers[0]);
+                               answer.dsend(fTask.answerTo);
+                       }
+                       else {
+                       // otherwise, forward the request to the closest preceding finger in my table
+                               int closest = closestPrecedingNode(fTask.requestId);
+                               //Msg.info("Forward the request to " + closest);
+                               fTask.dsend(Integer.toString(closest));
+                       }
+               }
+               else if (task instanceof GetPredecessorTask) {
+                       GetPredecessorTask gTask = (GetPredecessorTask)(task);
+                       Msg.debug("Receiving a 'Get Predecessor' request from " + gTask.issuerHostName);
+                       GetPredecessorAnswerTask answer = new GetPredecessorAnswerTask(host.getName(), mailbox, predId);
+                       answer.dsend(gTask.answerTo);
+               }
+               else if (task instanceof NotifyTask) {
+                       NotifyTask nTask = (NotifyTask)task;
+                       notify(nTask.requestId);
+               }
+               else {
+                       Msg.debug("Ignoring unexpected task of type:" + task);
+               }
+       }
+       /**
+        * @brief Makes the current node quit the system
+        */
+       void leave() {
+               Msg.debug("Well Guys! I Think it's time for me to quit ;)");
+               quitNotify(1); //Notify my successor
+               quitNotify(-1); //Notify my predecessor.
+               // TODO ...
+       }
+       /**
+        * @brief Notifies the successor or the predecessor of the current node
+        * of the departure
+        * @param to 1 to notify the successor, -1 to notify the predecessor
+        */
+       static void quitNotify( int to) {
+               //TODO
+       }
+       /**
+      * @brief Initializes the current node as the first one of the system.
+        */
+       void create() {
+               Msg.debug("Create a new Chord ring...");
+               setPredecessor(-1);
+               
+       }
+       /**
+        * Makes the current node join the ring, knowing the id of a node
+        * already in the ring 
+        */
+       boolean join(int knownId) {
+               Msg.info("Joining the ring with id " + this.id + " knowing node " + knownId);
+               setPredecessor(-1);
+               int successorId = remoteFindSuccessor(knownId, this.id);
+               if (successorId == -1) {
+                       Msg.info("Cannot join the ring.");
+               }
+               else {
+                       setFinger(0, successorId);
+               }
+               return successorId != -1;
+       }
+       
+       /**
+        * Sets the node predecessor
+        */
+       void setPredecessor(int predecessorId) {
+               if (predecessorId != predId) {
+                       predId = predecessorId;
+                       if (predecessorId != -1) {
+                               predMailbox = Integer.toString(predId);
+                       }
+                       lastChangeDate = Msg.getClock();
+               }
+       }
+       /**
+        * @brief Asks another node its predecessor.
+        * @param askTo the node to ask to
+        * @return the id of its predecessor node, or -1 if the request failed
+        * (or if the node does not know its predecessor)
+        */
+       int remoteGetPredecessor(int askTo) {
+               int predecessorId = -1;
+               boolean stop = false;
+               Msg.debug("Sending a 'Get Predecessor' request to " + askTo);
+               String mailboxTo = Integer.toString(askTo);
+               GetPredecessorTask sendTask = new GetPredecessorTask(host.getName(), this.mailbox);
+               try {
+                       sendTask.send(mailboxTo, Common.TIMEOUT);                       
+                       try {
+                               do {
+                                       if (commReceive == null) {
+                                               commReceive = Task.irecv(this.mailbox);
+                                       }
+                                       commReceive.waitCompletion(Common.TIMEOUT);
+                                       Task taskReceived = commReceive.getTask();
+                                       if (taskReceived instanceof GetPredecessorAnswerTask) {
+                                               predecessorId = ((GetPredecessorAnswerTask) taskReceived).answerId;
+                                               stop = true;
+                                       }
+                                       else {
+                                               handleTask(taskReceived);
+                                       }
+                                       commReceive = null;                                     
+                               } while (!stop);
+               
+                       }
+                       catch (MsgException e) {
+                               commReceive = null;     
+                               stop = true;
+                       }
+               }
+               catch (MsgException e) {
+                       Msg.debug("Failed to send the Get Predecessor request");
+               }
+               
+               
+               return predecessorId;
+       }
+       /**
+        * @brief Makes the current node find the successor node of an id.
+        * @param node the current node
+        * @param id the id to find
+        * @return the id of the successor node, or -1 if the request failed
+        */
+       int findSuccessor(int id) {
+               if (isInInterval(id, this.id + 1, fingers[0])) {
+                       return fingers[0];
+               }
+               
+               int closest = this.closestPrecedingNode(id);
+               return remoteFindSuccessor(closest, id);
+       }
+       /**
+        * @brief Asks another node the successor node of an id.
+        */
+       int remoteFindSuccessor(int askTo, int id) {
+               int successor = -1;
+               boolean stop = false;
+               String mailbox = Integer.toString(askTo);
+               Task sendTask = new FindSuccessorTask(host.getName(), this.mailbox, id);
+               Msg.debug("Sending a 'Find Successor' request to " + mailbox + " for id " + id);
+               try {
+                       sendTask.send(mailbox, Common.TIMEOUT);
+                       do {
+                               if (commReceive == null) {
+                                       commReceive = Task.irecv(this.mailbox);
+                               }
+                               try {
+                                       commReceive.waitCompletion(Common.TIMEOUT);
+                                       Task task = commReceive.getTask();
+                                       if (task instanceof FindSuccessorAnswerTask) {
+                                               //TODO: Check if this this our answer.
+                                               FindSuccessorAnswerTask fTask = (FindSuccessorAnswerTask) task;
+                                               stop = true;
+                                               successor = fTask.answerId;
+                                       }
+                                       else {
+                                               handleTask(task);
+                                       }
+                                       commReceive = null;
+                               }
+                               catch (TimeoutException e) {
+                                       stop = true;
+                                       commReceive = null;
+                               }
+                       } while (!stop);
+               }
+               catch (TimeoutException e) {
+                       Msg.debug("Failed to send the 'Find Successor' request");
+               }
+               catch (MsgException e) {
+                       Msg.debug("Failed to receive Find Successor");
+               }
+               
+               return successor;
+
+       }
+       /**
+        * @brief This function is called periodically. It checks the immediate
+        * successor of the current node.
+        */
+       void stabilize() {
+               Msg.debug("Stabilizing node");
+               int candidateId;
+               int successorId = fingers[0];
+               if (successorId != this.id){
+                       candidateId = remoteGetPredecessor(successorId);
+               }
+               else {
+                       candidateId = predId;
+               }
+               //This node is a candidate to become my new successor
+               if (candidateId != -1 && isInInterval(candidateId, this.id + 1, successorId - 1)) {
+                       setFinger(0, candidateId);
+               }
+               if (successorId != this.id) {
+                       remoteNotify(successorId, this.id);
+               }
+               
+       }
+       /**
+        * \brief Notifies the current node that its predecessor may have changed.
+        * \param candidate_id the possible new predecessor
+        */
+       void notify(int predecessorCandidateId) {
+               if (predId == -1 || isInInterval(predecessorCandidateId, predId + 1, this.id - 1 )) {
+                       setPredecessor(predecessorCandidateId);
+               }
+               else {
+                       //Don't have to change the predecessor.
+               }
+       }
+       /**
+        * \brief Notifies a remote node that its predecessor may have changed.
+        * \param notify_id id of the node to notify
+        * \param candidate_id the possible new predecessor
+        */     
+       void remoteNotify(int notifyId, int predecessorCandidateId) {
+               Msg.debug("Sending a 'Notify' request to " + notifyId);
+               Task sentTask = new NotifyTask(host.getName(), this.mailbox, predecessorCandidateId);
+               sentTask.dsend(Integer.toString(notifyId));
+       }
+       /**
+        * \brief This function is called periodically.
+        * It refreshes the finger table of the current node.
+        */
+       void fixFingers() {
+               Msg.debug("Fixing fingers");
+               int i = this.nextFingerToFix;
+               int id = this.findSuccessor(this.id + (int)Math.pow(2,i)); //FIXME: SLOW
+               if (id != -1) {
+                       if (id != fingers[i]) {
+                               setFinger(i, id);
+                       }
+                       nextFingerToFix = (i + 1) % Common.NB_BITS;
+               }
+       }
+       /**
+        * \brief This function is called periodically.
+        * It checks whether the predecessor has failed
+        */
+       void checkPredecessor() {
+               //TODO
+       }
+       /**
+        * \brief Performs a find successor request to a random id.
+        */
+       void randomLookup() {
+               int id = 1337;
+               //Msg.info("Making a lookup request for id " + id);
+               findSuccessor(id);
+       }
+       
+       
+
+       /**
+        * @brief Returns the closest preceding finger of an id
+        * with respect to the finger table of the current node.
+        * @param id the id to find
+        * \return the closest preceding finger of that id
+        */
+       int closestPrecedingNode(int id) {
+               int i;
+               for (i = Common.NB_BITS - 1; i >= 0; i--) {
+                       if (isInInterval(fingers[i], this.id + 1, id - 1)) {
+                               return fingers[i];
+                       }
+               }               
+               return this.id;
+       }
+       /**
+        * @brief Returns whether an id belongs to the interval [start, end].
+        *
+        * The parameters are noramlized to make sure they are between 0 and nb_keys - 1).
+        * 1 belongs to [62, 3]
+        * 1 does not belong to [3, 62]
+        * 63 belongs to [62, 3]
+        * 63 does not belong to [3, 62]
+        * 24 belongs to [21, 29]
+        * 24 does not belong to [29, 21]
+        *
+        * \param id id to check
+        * \param start lower bound
+        * \param end upper bound
+        * \return a non-zero value if id in in [start, end]
+        */
+       static boolean isInInterval(int id, int start, int end) {
+               id = normalize(id);
+               start = normalize(start);
+               end = normalize(end);
+               
+               // make sure end >= start and id >= start
+               if (end < start) {
+                       end += Common.NB_KEYS;
+               }
+               if (id < start) {
+                       id += Common.NB_KEYS;
+               }
+               return (id <= end);
+       
+       }
+       /**
+        * @brief Turns an id into an equivalent id in [0, nb_keys).
+        * @param id an id
+        * @return the corresponding normalized id
+        */
+       static int normalize(int id) {
+               return id & (Common.NB_KEYS - 1);
+       }
+       /**
+        * \brief Sets a finger of the current node.
+        * \param finger_index index of the finger to set (0 to nb_bits - 1)
+        * \param id the id to set for this finger
+        */
+       void setFinger(int fingerIndex, int id) {
+               if (id != fingers[fingerIndex]) {
+                       fingers[fingerIndex] = id;
+                       lastChangeDate = Msg.getClock();
+               }
+       }
+}
diff --git a/examples/chord/NotifyTask.java b/examples/chord/NotifyTask.java
new file mode 100644 (file)
index 0000000..d3e8f2e
--- /dev/null
@@ -0,0 +1,9 @@
+package chord;
+
+public class NotifyTask extends ChordTask {
+       public int requestId;
+       public NotifyTask(String issuerHostname, String answerTo, int requestId) {
+               super(issuerHostname, answerTo);
+               this.requestId = requestId;
+       }
+}
diff --git a/examples/chord/chord.xml b/examples/chord/chord.xml
new file mode 100644 (file)
index 0000000..f04ba2d
--- /dev/null
@@ -0,0 +1,59 @@
+<?xml version='1.0'?>
+<!DOCTYPE platform SYSTEM "http://simgrid.gforge.inria.fr/simgrid.dtd">
+<platform version="3">
+
+  <process host="Gatien" function="chord.Node">
+    <argument value="48"/>        <!-- my id -->
+    <argument value="1"/>         <!-- known id -->
+    <argument value="400"/>        <!-- time to sleep before it starts-->
+    <argument value ="600"/>           <!-- deadline -->
+  </process>
+
+  <process host="McGee" function="chord.Node">
+    <argument value="42"/>        <!-- my id -->
+    <argument value="1"/>         <!-- known id -->
+    <argument value="300"/>        <!-- time to sleep before it starts-->
+    <argument value ="600"/>           <!-- deadline -->
+  </process>
+
+  <process host="iRMX" function="chord.Node">
+    <argument value="38"/>        <!-- my id -->
+    <argument value="1"/>         <!-- known id -->
+    <argument value="200"/>         <!-- time to sleep before it starts-->
+    <argument value ="600"/>           <!-- deadline -->
+  </process>
+
+  <process host="Geoff" function="chord.Node">
+    <argument value="32"/>        <!-- my id -->
+    <argument value="1"/>         <!-- known id -->
+    <argument value="100"/>         <!-- time to sleep before it starts-->
+    <argument value ="600"/>           <!-- deadline -->
+  </process>
+
+  <process host="TeX" function="chord.Node">
+    <argument value="21"/>        <!-- my id -->
+    <argument value="1"/>         <!-- known id -->
+    <argument value="40"/>        <!-- time to sleep before it starts-->
+    <argument value ="600"/>           <!-- deadline -->
+  </process>
+
+  <process host="Jean_Yves" function="chord.Node">
+    <argument value="14"/>        <!-- my id -->
+    <argument value="1"/>         <!-- known id -->
+    <argument value="16"/>        <!-- time to sleep before it starts-->
+    <argument value ="600"/>           <!-- deadline -->
+  </process>
+  
+  <process host="Boivin" function="chord.Node">
+    <argument value="8"/>         <!-- my id -->
+    <argument value="1"/>         <!-- known id -->
+    <argument value="1"/>         <!-- time to sleep before it starts-->
+    <argument value ="600"/>           <!-- deadline -->
+  </process>
+
+  <process host="Jacquelin" function="chord.Node">
+    <argument value="1"/>         <!-- my id -->
+    <argument value ="600"/>           <!-- deadline -->
+  </process>
+
+</platform>
diff --git a/examples/chord/chord100.xml b/examples/chord/chord100.xml
new file mode 100644 (file)
index 0000000..f325f92
--- /dev/null
@@ -0,0 +1,104 @@
+<?xml version='1.0'?>
+<!DOCTYPE platform SYSTEM "http://simgrid.gforge.inria.fr/simgrid.dtd">
+<platform version="3">
+  <process host="c-0.me" function="chord.Node"><argument value="42"/><argument value="6000000"/></process>
+  <process host="c-1.me" function="chord.Node"><argument value="366680" /><argument value="42" /><argument value="10" /><argument value="6000000" /></process>
+  <process host="c-2.me" function="chord.Node"><argument value="533744" /><argument value="366680" /><argument value="20" /><argument value="6000000" /></process>
+  <process host="c-3.me" function="chord.Node"><argument value="1319738" /><argument value="42" /><argument value="30" /><argument value="6000000" /></process>
+  <process host="c-4.me" function="chord.Node"><argument value="16509405" /><argument value="366680" /><argument value="40" /><argument value="6000000" /></process>
+  <process host="c-5.me" function="chord.Node"><argument value="10874876" /><argument value="533744" /><argument value="50" /><argument value="6000000" /></process>
+  <process host="c-6.me" function="chord.Node"><argument value="16728096" /><argument value="1319738" /><argument value="60" /><argument value="6000000" /></process>
+  <process host="c-7.me" function="chord.Node"><argument value="10004760" /><argument value="16509405" /><argument value="70" /><argument value="6000000" /></process>
+  <process host="c-8.me" function="chord.Node"><argument value="6518808" /><argument value="42" /><argument value="80" /><argument value="6000000" /></process>
+  <process host="c-9.me" function="chord.Node"><argument value="2015253" /><argument value="1319738" /><argument value="90" /><argument value="6000000" /></process>
+  <process host="c-10.me" function="chord.Node"><argument value="10480191" /><argument value="42" /><argument value="100" /><argument value="6000000" /></process>
+  <process host="c-11.me" function="chord.Node"><argument value="13505621" /><argument value="10004760" /><argument value="110" /><argument value="6000000" /></process>
+  <process host="c-12.me" function="chord.Node"><argument value="13281914" /><argument value="10480191" /><argument value="120" /><argument value="6000000" /></process>
+  <process host="c-13.me" function="chord.Node"><argument value="13493864" /><argument value="6518808" /><argument value="130" /><argument value="6000000" /></process>
+  <process host="c-14.me" function="chord.Node"><argument value="15853741" /><argument value="6518808" /><argument value="140" /><argument value="6000000" /></process>
+  <process host="c-15.me" function="chord.Node"><argument value="12334717" /><argument value="2015253" /><argument value="150" /><argument value="6000000" /></process>
+  <process host="c-16.me" function="chord.Node"><argument value="13082922" /><argument value="2015253" /><argument value="160" /><argument value="6000000" /></process>
+  <process host="c-17.me" function="chord.Node"><argument value="11008018" /><argument value="13082922" /><argument value="170" /><argument value="6000000" /></process>
+  <process host="c-18.me" function="chord.Node"><argument value="14292368" /><argument value="13505621" /><argument value="180" /><argument value="6000000" /></process>
+  <process host="c-19.me" function="chord.Node"><argument value="13213873" /><argument value="16509405" /><argument value="190" /><argument value="6000000" /></process>
+  <process host="c-20.me" function="chord.Node"><argument value="16742003" /><argument value="11008018" /><argument value="200" /><argument value="6000000" /></process>
+  <process host="c-21.me" function="chord.Node"><argument value="8868836" /><argument value="6518808" /><argument value="210" /><argument value="6000000" /></process>
+  <process host="c-22.me" function="chord.Node"><argument value="596034" /><argument value="12334717" /><argument value="220" /><argument value="6000000" /></process>
+  <process host="c-23.me" function="chord.Node"><argument value="12957732" /><argument value="16728096" /><argument value="230" /><argument value="6000000" /></process>
+  <process host="c-24.me" function="chord.Node"><argument value="14183557" /><argument value="12334717" /><argument value="240" /><argument value="6000000" /></process>
+  <process host="c-25.me" function="chord.Node"><argument value="9710252" /><argument value="8868836" /><argument value="250" /><argument value="6000000" /></process>
+  <process host="c-26.me" function="chord.Node"><argument value="9592804" /><argument value="596034" /><argument value="260" /><argument value="6000000" /></process>
+  <process host="c-27.me" function="chord.Node"><argument value="10836171" /><argument value="366680" /><argument value="270" /><argument value="6000000" /></process>
+  <process host="c-28.me" function="chord.Node"><argument value="2610930" /><argument value="10836171" /><argument value="280" /><argument value="6000000" /></process>
+  <process host="c-29.me" function="chord.Node"><argument value="3938816" /><argument value="596034" /><argument value="290" /><argument value="6000000" /></process>
+  <process host="c-30.me" function="chord.Node"><argument value="9207700" /><argument value="1319738" /><argument value="300" /><argument value="6000000" /></process>
+  <process host="c-31.me" function="chord.Node"><argument value="11822289" /><argument value="10004760" /><argument value="310" /><argument value="6000000" /></process>
+  <process host="c-32.me" function="chord.Node"><argument value="6617885" /><argument value="10004760" /><argument value="320" /><argument value="6000000" /></process>
+  <process host="c-33.me" function="chord.Node"><argument value="10798069" /><argument value="366680" /><argument value="330" /><argument value="6000000" /></process>
+  <process host="c-34.me" function="chord.Node"><argument value="16224350" /><argument value="10836171" /><argument value="340" /><argument value="6000000" /></process>
+  <process host="c-35.me" function="chord.Node"><argument value="116769" /><argument value="13082922" /><argument value="350" /><argument value="6000000" /></process>
+  <process host="c-36.me" function="chord.Node"><argument value="8131023" /><argument value="2610930" /><argument value="360" /><argument value="6000000" /></process>
+  <process host="c-37.me" function="chord.Node"><argument value="15470236" /><argument value="116769" /><argument value="370" /><argument value="6000000" /></process>
+  <process host="c-38.me" function="chord.Node"><argument value="10364630" /><argument value="3938816" /><argument value="380" /><argument value="6000000" /></process>
+  <process host="c-39.me" function="chord.Node"><argument value="2379364" /><argument value="8868836" /><argument value="390" /><argument value="6000000" /></process>
+  <process host="c-40.me" function="chord.Node"><argument value="5944675" /><argument value="13281914" /><argument value="400" /><argument value="6000000" /></process>
+  <process host="c-41.me" function="chord.Node"><argument value="2772317" /><argument value="16224350" /><argument value="410" /><argument value="6000000" /></process>
+  <process host="c-42.me" function="chord.Node"><argument value="7514751" /><argument value="42" /><argument value="420" /><argument value="6000000" /></process>
+  <process host="c-43.me" function="chord.Node"><argument value="11363703" /><argument value="13505621" /><argument value="430" /><argument value="6000000" /></process>
+  <process host="c-44.me" function="chord.Node"><argument value="5864403" /><argument value="42" /><argument value="440" /><argument value="6000000" /></process>
+  <process host="c-45.me" function="chord.Node"><argument value="9509382" /><argument value="12957732" /><argument value="450" /><argument value="6000000" /></process>
+  <process host="c-46.me" function="chord.Node"><argument value="3107460" /><argument value="10364630" /><argument value="460" /><argument value="6000000" /></process>
+  <process host="c-47.me" function="chord.Node"><argument value="13568572" /><argument value="42" /><argument value="470" /><argument value="6000000" /></process>
+  <process host="c-48.me" function="chord.Node"><argument value="15651936" /><argument value="9710252" /><argument value="480" /><argument value="6000000" /></process>
+  <process host="c-49.me" function="chord.Node"><argument value="10558377" /><argument value="3938816" /><argument value="490" /><argument value="6000000" /></process>
+  <process host="c-50.me" function="chord.Node"><argument value="4285545" /><argument value="13493864" /><argument value="500" /><argument value="6000000" /></process>
+  <process host="c-51.me" function="chord.Node"><argument value="7467879" /><argument value="10480191" /><argument value="510" /><argument value="6000000" /></process>
+  <process host="c-52.me" function="chord.Node"><argument value="11019172" /><argument value="14183557" /><argument value="520" /><argument value="6000000" /></process>
+  <process host="c-53.me" function="chord.Node"><argument value="2358899" /><argument value="16728096" /><argument value="530" /><argument value="6000000" /></process>
+  <process host="c-54.me" function="chord.Node"><argument value="16134431" /><argument value="11822289" /><argument value="540" /><argument value="6000000" /></process>
+  <process host="c-55.me" function="chord.Node"><argument value="5244089" /><argument value="2015253" /><argument value="550" /><argument value="6000000" /></process>
+  <process host="c-56.me" function="chord.Node"><argument value="15499692" /><argument value="5944675" /><argument value="560" /><argument value="6000000" /></process>
+  <process host="c-57.me" function="chord.Node"><argument value="13922187" /><argument value="366680" /><argument value="570" /><argument value="6000000" /></process>
+  <process host="c-58.me" function="chord.Node"><argument value="12086592" /><argument value="2379364" /><argument value="580" /><argument value="6000000" /></process>
+  <process host="c-59.me" function="chord.Node"><argument value="10579841" /><argument value="8131023" /><argument value="590" /><argument value="6000000" /></process>
+  <process host="c-60.me" function="chord.Node"><argument value="14893867" /><argument value="10798069" /><argument value="600" /><argument value="6000000" /></process>
+  <process host="c-61.me" function="chord.Node"><argument value="11273607" /><argument value="12086592" /><argument value="610" /><argument value="6000000" /></process>
+  <process host="c-62.me" function="chord.Node"><argument value="810112" /><argument value="10558377" /><argument value="620" /><argument value="6000000" /></process>
+  <process host="c-63.me" function="chord.Node"><argument value="10874581" /><argument value="14893867" /><argument value="630" /><argument value="6000000" /></process>
+  <process host="c-64.me" function="chord.Node"><argument value="4339906" /><argument value="2379364" /><argument value="640" /><argument value="6000000" /></process>
+  <process host="c-65.me" function="chord.Node"><argument value="5230199" /><argument value="15651936" /><argument value="650" /><argument value="6000000" /></process>
+  <process host="c-66.me" function="chord.Node"><argument value="3459719" /><argument value="15651936" /><argument value="660" /><argument value="6000000" /></process>
+  <process host="c-67.me" function="chord.Node"><argument value="342511" /><argument value="11363703" /><argument value="670" /><argument value="6000000" /></process>
+  <process host="c-68.me" function="chord.Node"><argument value="12540825" /><argument value="13082922" /><argument value="680" /><argument value="6000000" /></process>
+  <process host="c-69.me" function="chord.Node"><argument value="3915035" /><argument value="16742003" /><argument value="690" /><argument value="6000000" /></process>
+  <process host="c-70.me" function="chord.Node"><argument value="9756331" /><argument value="14893867" /><argument value="700" /><argument value="6000000" /></process>
+  <process host="c-71.me" function="chord.Node"><argument value="1057" /><argument value="16224350" /><argument value="710" /><argument value="6000000" /></process>
+  <process host="c-72.me" function="chord.Node"><argument value="14905830" /><argument value="14292368" /><argument value="720" /><argument value="6000000" /></process>
+  <process host="c-73.me" function="chord.Node"><argument value="15011862" /><argument value="116769" /><argument value="730" /><argument value="6000000" /></process>
+  <process host="c-74.me" function="chord.Node"><argument value="16561708" /><argument value="2358899" /><argument value="740" /><argument value="6000000" /></process>
+  <process host="c-75.me" function="chord.Node"><argument value="15398543" /><argument value="13213873" /><argument value="750" /><argument value="6000000" /></process>
+  <process host="c-76.me" function="chord.Node"><argument value="182864" /><argument value="533744" /><argument value="760" /><argument value="6000000" /></process>
+  <process host="c-77.me" function="chord.Node"><argument value="6530186" /><argument value="13568572" /><argument value="770" /><argument value="6000000" /></process>
+  <process host="c-78.me" function="chord.Node"><argument value="11363165" /><argument value="13213873" /><argument value="780" /><argument value="6000000" /></process>
+  <process host="c-79.me" function="chord.Node"><argument value="8636303" /><argument value="15499692" /><argument value="790" /><argument value="6000000" /></process>
+  <process host="c-80.me" function="chord.Node"><argument value="11606104" /><argument value="5244089" /><argument value="800" /><argument value="6000000" /></process>
+  <process host="c-81.me" function="chord.Node"><argument value="7750053" /><argument value="13505621" /><argument value="810" /><argument value="6000000" /></process>
+  <process host="c-82.me" function="chord.Node"><argument value="15166832" /><argument value="3938816" /><argument value="820" /><argument value="6000000" /></process>
+  <process host="c-83.me" function="chord.Node"><argument value="4096877" /><argument value="11363703" /><argument value="830" /><argument value="6000000" /></process>
+  <process host="c-84.me" function="chord.Node"><argument value="15838695" /><argument value="1319738" /><argument value="840" /><argument value="6000000" /></process>
+  <process host="c-85.me" function="chord.Node"><argument value="16057285" /><argument value="182864" /><argument value="850" /><argument value="6000000" /></process>
+  <process host="c-86.me" function="chord.Node"><argument value="11161393" /><argument value="15166832" /><argument value="860" /><argument value="6000000" /></process>
+  <process host="c-87.me" function="chord.Node"><argument value="7283581" /><argument value="16224350" /><argument value="870" /><argument value="6000000" /></process>
+  <process host="c-88.me" function="chord.Node"><argument value="4769647" /><argument value="7750053" /><argument value="880" /><argument value="6000000" /></process>
+  <process host="c-89.me" function="chord.Node"><argument value="3395518" /><argument value="596034" /><argument value="890" /><argument value="6000000" /></process>
+  <process host="c-90.me" function="chord.Node"><argument value="11275302" /><argument value="10836171" /><argument value="900" /><argument value="6000000" /></process>
+  <process host="c-91.me" function="chord.Node"><argument value="1607535" /><argument value="15398543" /><argument value="910" /><argument value="6000000" /></process>
+  <process host="c-92.me" function="chord.Node"><argument value="9038828" /><argument value="1057" /><argument value="920" /><argument value="6000000" /></process>
+  <process host="c-93.me" function="chord.Node"><argument value="3254523" /><argument value="11363165" /><argument value="930" /><argument value="6000000" /></process>
+  <process host="c-94.me" function="chord.Node"><argument value="10826610" /><argument value="366680" /><argument value="940" /><argument value="6000000" /></process>
+  <process host="c-95.me" function="chord.Node"><argument value="2013580" /><argument value="11363165" /><argument value="950" /><argument value="6000000" /></process>
+  <process host="c-96.me" function="chord.Node"><argument value="4796981" /><argument value="14893867" /><argument value="960" /><argument value="6000000" /></process>
+  <process host="c-97.me" function="chord.Node"><argument value="5518537" /><argument value="4285545" /><argument value="970" /><argument value="6000000" /></process>
+  <process host="c-98.me" function="chord.Node"><argument value="15089786" /><argument value="15166832" /><argument value="980" /><argument value="6000000" /></process>
+  <process host="c-99.me" function="chord.Node"><argument value="8611178" /><argument value="3107460" /><argument value="990" /><argument value="6000000" /></process>
+</platform>