examples/msg/chord/chord.c

   1
   2 /* Copyright (c) 2010. The SimGrid Team.
   3  * All rights reserved.                                                     */
   4
   5 /* This program is free software; you can redistribute it and/or modify it
   6  * under the terms of the license (GNU LGPL) which comes with this package. */
   7
   8 #include <stdio.h>
   9 #include "msg/msg.h"
  10 #include "xbt/log.h"
  11 #include "xbt/asserts.h"
  12 XBT_LOG_NEW_DEFAULT_CATEGORY(msg_chord,
  13                              "Messages specific for this msg example");
  14
  15 #define NB_BITS 6
  16 #define NB_KEYS 64
  17
  18 /**
  19  * Finger element.
  20  */
  21 typedef struct finger {
  22   int id;
  23   char* mailbox;
  24 } s_finger_t, *finger_t;
  25
  26 /**
  27  * Node data.
  28  */
  29 typedef struct node {
  30   int id;                                 // my id
  31   char* mailbox;
  32   s_finger_t fingers[NB_BITS];            // finger table (fingers[0] is my successor)
  33   int pred_id;                            // predecessor id
  34   char* pred_mailbox;
  35   xbt_dynar_t comms;                      // current communications to finish
  36 } s_node_t, *node_t;
  37
  38 /**
  39  * Task data
  40  */
  41 typedef struct task_data {
  42   int request_id;
  43   int request_finger;
  44   int answer_id;
  45   const char* answer_to;
  46   const char* issuer_host_name; // used for logging
  47   int successor_id;                             // used when quitting
  48   int pred_id;                                  // used when quitting
  49 } s_task_data_t, *task_data_t;
  50
  51 // utility functions
  52 static int normalize(int id);
  53 static int is_in_interval(int id, int start, int end);
  54 static char* get_mailbox(int host_id);
  55 static void print_finger_table(node_t node);
  56
  57 // process functions
  58 static int node(int argc, char *argv[]);
  59
  60 // initialization
  61 static void initialize_first_node(node_t node);
  62 static void initialize_finger_table(node_t data, int known_id);
  63 static void join(node_t node, int known_id);
  64 static void leave(node_t node);
  65
  66 // Chord core
  67 static int find_successor(node_t node, int id);
  68 static int remote_find_successor(node_t node, int ask_to_id, int id);
  69 static int find_predecessor(node_t node, int id);
  70 static int remote_find_predecessor(node_t node, int ask_to_id, int id);
  71 static int closest_preceding_finger(node_t node, int id);
  72 static int remote_closest_preceding_finger(int ask_to_id, int id);
  73 static void notify_predecessors(node_t node);
  74 static void remote_move_keys(node_t node, int take_from_id);
  75 static void update_finger_table(node_t node, int candidate_id, int finger_index);
  76 static void remote_update_finger_table(node_t node, int ask_to_id, int candidate_id, int finger_index);
  77 static void notify(node_t node, int predecessor_candidate_id);
  78 static void remote_notify(node_t node, int notify_to, int predecessor_candidate_id);
  79 static void stabilize(node_t node);
  80 static void quit_notify(node_t node, int to);
  81
  82 /**
  83  * \brief Turns an id into an equivalent id in [0, NB_KEYS[
  84  * \param id an id
  85  * \return the corresponding normalized id
  86  */
  87 static int normalize(int id) {
  88
  89   // make sure id >= 0
  90   while (id < 0) {
  91     id += NB_KEYS;
  92   }
  93   // make sure id < NB_KEYS
  94   id = id % NB_KEYS;
  95
  96   return id;
  97 }
  98
  99 /**
 100  * \brief Returns whether a id belongs to the interval [start, end].
 101  *
 102  * The parameters are noramlized to make sure they are between 0 and CHORD_NB_KEYS - 1).
 103  * 1 belongs to [62, 3]
 104  * 1 does not belong to [3, 62]
 105  * 63 belongs to [62, 3]
 106  * 63 does not belong to [3, 62]
 107  * 24 belongs to [21, 29]
 108  * 24 does not belong to [29, 21]
 109  *
 110  * \param id id to check
 111  * \param start lower bound
 112  * \param end upper bound
 113  * \return a non-zero value if id in in [start, end]
 114  */
 115 static int is_in_interval(int id, int start, int end) {
 116
 117   id = normalize(id);
 118   start = normalize(start);
 119   end = normalize(end);
 120
 121   // make sure end >= start and id >= start
 122   if (end < start) {
 123     end += NB_KEYS;
 124   }
 125
 126   if (id < start) {
 127     id += NB_KEYS;
 128   }
 129
 130   return id <= end;
 131 }
 132
 133 /**
 134  * \brief Gets the mailbox name of a host given its chord id.
 135  * \param node_id id of a node
 136  * \return the name of its mailbox
 137  * FIXME: free the memory
 138  */
 139 static char* get_mailbox(int node_id) {
 140
 141   return bprintf("mailbox%d", node_id);
 142 }
 143
 144 /**
 145  * \brief Displays the finger table of a node.
 146  * \param node a node
 147  */
 148 static void print_finger_table(node_t node) {
 149
 150   int i;
 151   int pow = 1;
 152   INFO0("My finger table:");
 153   INFO0("Start | Succ ");
 154   for (i = 0; i < NB_BITS; i++) {
 155     INFO2(" %3d  | %3d ", (node->id + pow) % NB_KEYS, node->fingers[i].id);
 156     pow = pow << 1;
 157   }
 158   INFO1("Predecessor: %d", node->pred_id);
 159 }
 160
 161 /**
 162  * \brief Node Function
 163  * Arguments:
 164  * - my id
 165  * - the id of a guy I know in the system (except for the first node)
 166  * - the time to sleep before I join (except for the first node)
 167  */
 168 int node(int argc, char *argv[])
 169 {
 170   double init_time = MSG_get_clock();
 171   msg_comm_t comm = NULL;
 172   int i;
 173   char* mailbox;
 174   double deadline;
 175
 176   xbt_assert0(argc == 3 || argc == 5, "Wrong number of arguments for this node");
 177
 178   // initialize my node
 179   s_node_t node = {0};
 180   node.id = atoi(argv[1]);
 181   node.mailbox = get_mailbox(node.id);
 182   node.comms = xbt_dynar_new(sizeof(msg_comm_t), NULL);
 183
 184
 185   if (argc == 3) { // first ring
 186     initialize_first_node(&node);
 187     deadline = atof(argv[2]);
 188   }
 189   else {
 190     int known_id = atoi(argv[2]);
 191     double sleep_time = atof(argv[3]);
 192     deadline = atof(argv[4]);
 193
 194     // sleep before starting
 195     INFO1("Let's sleep >>%f", sleep_time);
 196     MSG_process_sleep(sleep_time);
 197     INFO0("Hey! Let's join the system.");
 198
 199     join(&node, known_id);
 200   }
 201
 202   while ((MSG_get_clock( )- init_time) < deadline) {
 203
 204     unsigned int cursor;
 205     comm = NULL;
 206     xbt_dynar_foreach(node.comms, cursor, comm) {
 207       if (MSG_comm_test(comm)) { // FIXME: try with MSG_comm_testany instead
 208         xbt_dynar_cursor_rm(node.comms, &cursor);
 209         MSG_comm_destroy(comm);
 210       }
 211     }
 212
 213     m_task_t task = NULL;
 214     MSG_error_t res = MSG_task_receive_with_timeout(&task, node.mailbox,45); // FIXME >> find the right timeout !!
 215
 216     if(res == MSG_OK)                    // else check deadline condition and keep waiting for a task
 217     {
 218
 219     // get data
 220     const char* task_name = MSG_task_get_name(task);
 221     task_data_t task_data = (task_data_t) MSG_task_get_data(task);
 222
 223     if (!strcmp(task_name, "Find Successor")) {
 224       INFO2("Receiving a 'Find Successor' Request from %s for id %d", task_data->issuer_host_name, task_data->request_id);
 225       // is my successor the successor?
 226       if (is_in_interval(task_data->request_id, node.id + 1, node.fingers[0].id)) {
 227         task_data->answer_id = node.fingers[0].id;
 228         MSG_task_set_name(task, "Find Successor Answer");
 229         INFO3("Sending back a 'Find Successor' Answer to %s: the successor of %d is %d", task_data->issuer_host_name, task_data->request_id, task_data->answer_id);
 230         comm = MSG_task_isend(task, task_data->answer_to);
 231         xbt_dynar_push(node.comms, &comm);
 232       }
 233       else {
 234         // otherwise, forward the request to the closest preceding finger in my table
 235         int closest = closest_preceding_finger(&node, task_data->request_id);
 236         INFO2("Forwarding 'Find Successor' request for id %d to my closest preceding finger %d", task_data->request_id, closest);
 237         mailbox = get_mailbox(closest);
 238         comm = MSG_task_isend(task, mailbox);
 239         xbt_dynar_push(node.comms, &comm);
 240         xbt_free(mailbox);
 241       }
 242     }
 243
 244     else if (!strcmp(task_name, "Find Predecessor")) {
 245       INFO2("Receiving a 'Find Predecessor' Request from %s for id %d", task_data->issuer_host_name, task_data->request_id);
 246       // am I the predecessor?
 247       if (is_in_interval(task_data->request_id, node.id + 1, node.fingers[0].id)) {
 248         task_data->answer_id = node.id;
 249         MSG_task_set_name(task, "Find Predecessor Answer");
 250         INFO3("Sending back a 'Find Predecessor' Answer to %s: the predecessor of %d is %d", task_data->issuer_host_name, task_data->request_id, task_data->answer_id);
 251         comm = MSG_task_isend(task, task_data->answer_to);
 252         xbt_dynar_push(node.comms, &comm);
 253       }
 254       else {
 255         // otherwise, forward the request to the closest preceding finger in my table
 256         int closest = closest_preceding_finger(&node, task_data->request_id);
 257         INFO2("Forwarding 'Find Predecessor' request for id %d to my closest preceding finger %d", task_data->request_id, closest);
 258         mailbox = get_mailbox(closest);
 259         comm = MSG_task_isend(task, mailbox);
 260         xbt_dynar_push(node.comms, &comm);
 261         xbt_free(mailbox);
 262       }
 263     }
 264
 265     else if (!strcmp(task_name, "Update Finger")) {
 266       // someone is telling me that he may be my new finger
 267       INFO1("Receiving an 'Update Finger' request from %s", task_data->issuer_host_name);
 268       update_finger_table(&node, task_data->request_id, task_data->request_finger);
 269     }
 270     else if (!strcmp(task_name, "Notify")) {
 271       // someone is telling me that he may be my new predecessor
 272       INFO1("Receiving a 'Notify' request from %s", task_data->issuer_host_name);
 273       notify(&node, task_data->request_id);
 274     }
 275     else if (!strcmp(task_name, "Predecessor Leaving")) {
 276           // my predecessor is about quitting
 277           INFO1("Receiving a 'quite notify' from %s", task_data->issuer_host_name);
 278           // modify my predecessor
 279           node.pred_id = task_data->pred_id;
 280           node.pred_mailbox = get_mailbox(node.id);
 281           /*TODO :
 282           >> notify my new predecessor
 283           >> send a notify_predecessors !!
 284           */
 285
 286         }
 287     else if (!strcmp(task_name, "Successor Leaving")) {
 288           // my successor is about quitting
 289           INFO1("Receiving a 'quite notify' from %s", task_data->issuer_host_name);
 290           // modify my successor FIXME : this should be implicit ?
 291           node.fingers[0].id = task_data->successor_id;
 292           node.fingers[0].mailbox = get_mailbox(node.fingers[0].id);
 293           /* TODO
 294           >> notify my new successor
 295           >> update my table & predecessors table */
 296         }
 297     }
 298   }
 299   // leave the ring and quit simulation
 300   leave(&node);
 301   xbt_dynar_free(&node.comms);
 302   xbt_free(node.mailbox);
 303   xbt_free(node.pred_mailbox);
 304   for (i = 0; i < NB_BITS - 1; i++) {
 305     xbt_free(node.fingers[i].mailbox);
 306   }
 307   return 1;
 308 }
 309
 310 /**
 311  * \brief Initializes the current node as the first one of the system.
 312  * \param node the current node
 313  */
 314 static void initialize_first_node(node_t node)
 315 {
 316   INFO0("Create a new Chord ring...");
 317
 318   // I am my own successor and predecessor
 319   int i;
 320   for (i = 0; i < NB_BITS; i++) {
 321     node->fingers[i].id = node->id;
 322     node->fingers[i].mailbox = xbt_strdup(node->mailbox);
 323   }
 324   node->pred_id = node->id;
 325   node->pred_mailbox = node->mailbox;
 326   print_finger_table(node);
 327 }
 328
 329 /**
 330  * \brief Makes the current node join the system, knowing the id of a node already in the system
 331  * \param node the current node
 332  * \param known_id id of a node already in the system
 333  */
 334 static void join(node_t node, int known_id)
 335 {
 336   initialize_finger_table(node, known_id); // determine my fingers, asking to known_id
 337   remote_notify(node, node->fingers[0].id, node->id); // tell my successor that I'm his new predecessor
 338   notify_predecessors(node); // tell others that I may have became their finger
 339   remote_move_keys(node, node->fingers[0].id); // take some key-value pairs from my successor
 340 }
 341
 342 /**
 343  * \brief Makes the current node quit the system
 344  * \param node the current node
 345  */
 346 static void leave(node_t node)
 347 {
 348         INFO0("Well Guys! I Think it's time for me to quit ;)");
 349         quit_notify(node,1);            // notify to my successor ( >>> 1 );
 350         quit_notify(node,-1);           // notify my predecessor  ( >>> -1);
 351     // TODO ...
 352 }
 353 /*
 354  * \brief Notify msg to tell my successor||predecessor about my departure
 355  * \param node the current node
 356  */
 357 static void quit_notify(node_t node, int to)
 358 {
 359         task_data_t req_data = xbt_new0(s_task_data_t, 1);
 360         req_data->request_id = node->id;
 361         req_data->successor_id = node->fingers[0].id;
 362         req_data->pred_id = node->pred_id;
 363         req_data->issuer_host_name = MSG_host_get_name(MSG_host_self());
 364         const char *task_name = NULL;
 365         const char* to_mailbox = NULL;
 366         if( to == 1)    // notify my successor
 367         {
 368                 to_mailbox = node->fingers[0].mailbox;
 369             INFO1("Telling my Successor about my departure via mailbox %s", to_mailbox);
 370                 task_name = "Predecessor Leaving";
 371
 372         }
 373         else if(to == -1)    // notify my predecessor
 374         {
 375                 to_mailbox = node->pred_mailbox;
 376             INFO1("Telling my Predecessor about my departure via mailbox %s",to_mailbox);
 377                 task_name = "Predecessor Leaving";
 378         }
 379     m_task_t task = MSG_task_create(task_name, 1000, 5000, req_data);
 380     //char* mailbox = get_mailbox(to_mailbox);
 381         msg_comm_t comm = MSG_task_isend(task, to_mailbox);
 382         xbt_dynar_push(node->comms, &comm);
 383 }
 384
 385 /*
 386  * \brief Initializes my finger table, knowing the id of a node already in the system.
 387  * \param node the current node
 388  * \param known_id id of a node already in the system
 389  */
 390 static void initialize_finger_table(node_t node, int known_id)
 391 {
 392   int my_id = node->id;
 393   int i;
 394   int pow = 1; // 2^i
 395
 396   INFO0("Initializing my finger table...");
 397
 398   // ask known_id who is my immediate successor
 399   node->fingers[0].id = remote_find_successor(node, known_id, my_id + 1);
 400   node->fingers[0].mailbox = get_mailbox(node->fingers[0].id);
 401
 402   // find all other fingers
 403   for (i = 0; i < NB_BITS - 1; i++) {
 404
 405     pow = pow << 1; // equivalent to pow = pow * 2
 406     if (is_in_interval(my_id + pow, my_id, node->fingers[i].id - 1)) {
 407       // I already have the info for this finger
 408       node->fingers[i + 1].id = node->fingers[i].id;
 409     }
 410     else {
 411       // I don't have the info, ask the only guy I know
 412       node->fingers[i + 1].id = remote_find_successor(node, known_id, my_id + pow);
 413     }
 414     node->fingers[i + 1].mailbox = get_mailbox(node->fingers[i + 1].id);
 415   }
 416
 417   node->pred_id = find_predecessor(node, node->id);
 418   node->pred_mailbox = get_mailbox(node->pred_id);
 419
 420   INFO0("Finger table initialized!");
 421   print_finger_table(node);
 422 }
 423
 424 /**
 425  * \brief Notifies some nodes that the current node may have became their finger.
 426  * \param node the current node, which has just joined the system
 427  */
 428 static void notify_predecessors(node_t node)
 429 {
 430   int i, pred_id;
 431   int pow = 1;
 432   for (i = 0; i < NB_BITS; i++) {
 433     // find the closest node whose finger #i can be me
 434     pred_id = find_predecessor(node, node->id - pow + 1); // note: no "+1" in the article!
 435     if (pred_id != node->id) {
 436       remote_update_finger_table(node, pred_id, node->id, i);
 437     }
 438     pow = pow << 1; // pow = pow * 2
 439   }
 440 }
 441
 442 /**
 443  * \brief Tells the current node that a node may have became its new finger.
 444  * \param node the current node
 445  * \param candidate_id id of the node that may be a new finger of the current node
 446  * \param finger_index index of the finger to update
 447  */
 448 static void update_finger_table(node_t node, int candidate_id, int finger_index)
 449 {
 450   int pow = 1;
 451   int i;
 452   for (i = 0; i < finger_index; i++) {
 453     pow = pow << 1;
 454   }
 455
 456   //  if (is_in_interval(candidate_id, node->id + pow, node->fingers[finger_index].id - 1)) {
 457   if (is_in_interval(candidate_id, node->id, node->fingers[finger_index].id - 1)) {
 458 //    INFO3("Candidate %d is between %d and %d!", candidate_id, node->id + pow, node->fingers[finger_index].id - 1);
 459     // candidate_id is my new finger
 460     xbt_free(node->fingers[finger_index].mailbox);
 461     node->fingers[finger_index].id = candidate_id;
 462     node->fingers[finger_index].mailbox = get_mailbox(candidate_id);
 463     INFO2("My new finger #%d is %d", finger_index, candidate_id);
 464     print_finger_table(node);
 465
 466     if (node->pred_id != node->id) { // FIXME: is this necessary?
 467       // my predecessor may be concerned too
 468       remote_update_finger_table(node, node->pred_id, candidate_id, finger_index);
 469     }
 470   }
 471 }
 472
 473 /**
 474  * \brief Tells a remote node that a node may have became its new finger.
 475  * \param ask_to_id id of the remote node to update
 476  * \param candidate_id id of the node that may be a new finger of the remote node
 477  * \param finger_index index of the finger to update
 478  */
 479 static void remote_update_finger_table(node_t node, int ask_to_id, int candidate_id, int finger_index)
 480 {
 481   task_data_t req_data = xbt_new0(s_task_data_t, 1);
 482   req_data->request_id = candidate_id;
 483   req_data->request_finger = finger_index;
 484   req_data->issuer_host_name = MSG_host_get_name(MSG_host_self());
 485
 486   // send a "Update Finger" request to ask_to_id
 487   INFO3("Sending an 'Update Finger' request to %d: his finger #%d may be %d now", ask_to_id, finger_index, candidate_id);
 488   m_task_t task = MSG_task_create("Update Finger", 1000, 5000, req_data);
 489   char* mailbox = get_mailbox(ask_to_id);
 490   msg_comm_t comm = MSG_task_isend(task, mailbox);
 491   xbt_dynar_push(node->comms, &comm);
 492   xbt_free(mailbox);
 493 }
 494
 495 /**
 496  * \brief Makes the current node find the successor node of an id.
 497  * \param node the current node
 498  * \param id the id to find
 499  * \return the id of the successor node
 500  */
 501 static int find_successor(node_t node, int id)
 502 {
 503   // is my successor the successor?
 504   if (is_in_interval(id, node->id + 1, node->fingers[0].id)) {
 505     return node->fingers[0].id;
 506   }
 507
 508   // otherwise, ask the closest preceding finger in my table
 509   int closest = closest_preceding_finger(node, id);
 510   return remote_find_successor(node, closest, id);
 511 }
 512
 513 /**
 514  * \brief Asks another node the successor node of an id.
 515  * \param node the current node
 516  * \param ask_to the node to ask to
 517  * \param id the id to find
 518  * \return the id of the successor node
 519  */
 520 static int remote_find_successor(node_t node, int ask_to, int id)
 521 {
 522   s_task_data_t req_data;
 523   char* mailbox = bprintf("%s Find Successor", node->mailbox);
 524   req_data.request_id = id;
 525   req_data.answer_to = mailbox;
 526   req_data.issuer_host_name = MSG_host_get_name(MSG_host_self());
 527
 528   // send a "Find Successor" request to ask_to_id
 529   INFO2("Sending a 'Find Successor' request to %d for key %d", ask_to, id);
 530   m_task_t task = MSG_task_create("Find Successor", 1000, 5000, &req_data);
 531   MSG_task_send(task, get_mailbox(ask_to));
 532
 533   // receive the answer
 534   task = NULL;
 535   MSG_task_receive(&task, req_data.answer_to);
 536   task_data_t ans_data;
 537   ans_data = MSG_task_get_data(task);
 538   int successor = ans_data->answer_id;
 539   xbt_free(mailbox);
 540   INFO2("Received the answer to my Find Successor request: the successor of key %d is %d", id, successor);
 541
 542   return successor;
 543 }
 544
 545
 546 /**
 547  * \brief Makes the current node find the predecessor node of an id.
 548  * \param node the current node
 549  * \param id the id to find
 550  * \return the id of the predecessor node
 551  */
 552 static int find_predecessor(node_t node, int id)
 553 {
 554   if (node->id == node->fingers[0].id) {
 555     // I am the only node in the system
 556     return node->id;
 557   }
 558
 559   if (is_in_interval(id, node->id + 1, node->fingers[0].id)) {
 560     return node->id;
 561   }
 562   int ask_to = closest_preceding_finger(node, id);
 563   return remote_find_predecessor(node, ask_to, id);
 564 }
 565
 566 /**
 567  * \brief Asks another node the predecessor node of an id.
 568  * \param node the current node
 569  * \param ask_to the node to ask to
 570  * \param id the id to find
 571  * \return the id of the predecessor node
 572  */
 573 static int remote_find_predecessor(node_t node, int ask_to, int id)
 574 {
 575   s_task_data_t req_data;
 576   char* mailbox = bprintf("%s Find Predecessor", node->mailbox);
 577   req_data.request_id = id;
 578   req_data.answer_to = mailbox;
 579   req_data.issuer_host_name = MSG_host_get_name(MSG_host_self());
 580
 581   // send a "Find Predecessor" request to ask_to
 582   INFO2("Sending a 'Find Predecessor' request to %d for key %d", ask_to, id);
 583   m_task_t task = MSG_task_create("Find Predecessor", 1000, 5000, &req_data);
 584   MSG_task_send(task, get_mailbox(ask_to));
 585
 586   // receive the answer
 587   task = NULL;
 588   MSG_task_receive(&task, req_data.answer_to);
 589   task_data_t ans_data;
 590   ans_data = MSG_task_get_data(task);
 591   int predecessor = ans_data->answer_id;
 592   xbt_free(mailbox);
 593   INFO2("Received the answer to my 'Find Predecessor' request: the predecessor of key %d is %d", id, predecessor);
 594
 595   return predecessor;
 596 }
 597
 598 /**
 599  * \brief Returns the closest preceding finger of an id
 600  * with respect to the finger table of the current node.
 601  * \param node the current node
 602  * \param id the id to find
 603  * \return the closest preceding finger of that id
 604  */
 605 int closest_preceding_finger(node_t node, int id)
 606 {
 607   int i;
 608   for (i = NB_BITS - 1; i >= 0; i--) {
 609     if (is_in_interval(node->fingers[i].id, node->id + 1, id - 1)) {
 610       return node->fingers[i].id;
 611     }
 612   }
 613   return node->id;
 614 }
 615
 616 /**
 617  * \brief This function is called periodically. It checks the immediate
 618  * successor of the current node.
 619  * \param node the current node
 620  */
 621 static void stabilize(node_t node) {
 622
 623   int x = find_predecessor(node, node->fingers[0].id);
 624   if (is_in_interval(x, node->id + 1, node->fingers[0].id)) {
 625     xbt_free(node->fingers[0].mailbox);
 626     node->fingers[0].id = x;
 627     node->fingers[0].mailbox = get_mailbox(x);
 628   }
 629   remote_notify(node, node->fingers[0].id, node->id);
 630 }
 631
 632 /**
 633  * \brief Notifies the current node that its predecessor may have changed.
 634  * \param node the current node
 635  * \param candidate_id the possible new predecessor
 636  */
 637 static void notify(node_t node, int predecessor_candidate_id) {
 638
 639   if (node->pred_id == node->id
 640     || is_in_interval(predecessor_candidate_id, node->pred_id, node->id)) {
 641
 642     node->pred_id = predecessor_candidate_id;
 643     node->pred_mailbox = get_mailbox(predecessor_candidate_id);
 644
 645     INFO1("My new predecessor is %d", predecessor_candidate_id);
 646     print_finger_table(node);
 647   }
 648   else {
 649     INFO1("I don't have to change my predecessor to %d", predecessor_candidate_id);
 650   }
 651 }
 652
 653 /**
 654  * \brief Notifies a remote node that its predecessor may have changed.
 655  * \param node the current node
 656  * \param notify_id id of the node to notify
 657  * \param candidate_id the possible new predecessor
 658  */
 659 static void remote_notify(node_t node, int notify_id, int predecessor_candidate_id) {
 660
 661   task_data_t req_data = xbt_new0(s_task_data_t, 1);
 662   req_data->request_id = predecessor_candidate_id;
 663   req_data->issuer_host_name = MSG_host_get_name(MSG_host_self());
 664
 665   // send a "Notify" request to notify_id
 666   INFO1("Sending a 'Notify' request to %d", notify_id);
 667   m_task_t task = MSG_task_create("Notify", 1000, 5000, req_data);
 668   char* mailbox = get_mailbox(notify_id);
 669   msg_comm_t comm = MSG_task_isend(task, mailbox);
 670   xbt_dynar_push(node->comms, &comm);
 671   xbt_free(mailbox);
 672 }
 673
 674 /**
 675  * \brief Asks a node to take some of its keys.
 676  * \param node the current node, which has just joined the system
 677  * \param take_from_id id of a node who may have keys to give to the current node
 678  */
 679 static void remote_move_keys(node_t node, int take_from_id) {
 680   // TODO
 681 }
 682
 683 /**
 684  * \brief Main function.
 685  */
 686 int main(int argc, char *argv[])
 687 {
 688   if (argc < 3) {
 689     printf("Usage: %s platform_file deployment_file\n", argv[0]);
 690     printf("example: %s ../msg_platform.xml chord.xml\n", argv[0]);
 691     exit(1);
 692   }
 693
 694   MSG_global_init(&argc, argv);
 695
 696   const char* platform_file = argv[1];
 697   const char* application_file = argv[2];
 698
 699   /* MSG_config("workstation/model","KCCFLN05"); */
 700   MSG_set_channel_number(0);
 701   MSG_create_environment(platform_file);
 702
 703   MSG_function_register("node", node);
 704   MSG_launch_application(application_file);
 705
 706   MSG_error_t res = MSG_main();
 707   INFO1("Simulation time: %g", MSG_get_clock());
 708
 709   MSG_clean();
 710
 711   if (res == MSG_OK)
 712     return 0;
 713   else
 714     return 1;
 715 }