Decentralised Task-distribution in Peer-to-Peer Networks

Occurrences : 

2020

Nombre d'étudiants minimum: 

2

Nombre d'étudiants maximum: 

5

Nombre d'instances : 

2

Domaines: 

Overview and Objectives

This project aims to develop a multi-agent system for achieving decentralised task-distribution in peer-to-peer networks. Namely, a set of agents aim to distribute a number of tasks of different types, provided as input, equally amongst themselves, by coordinating via a communication network (or by moving around a 2D space). The algorithm should be tested initially on fully-connected and random graphs. Then, the algorithm can be tested on different network topologies (e.g. small world, scale-free, or community - Cf. Fig. 1) and at increasing scales. Alternatively, agents can move around a 2D environment (e.g. random or Levy walks). This project is supervised by researchers from several disciplines and universities and part of a larger research project [1].

Initially, agents select tasks randomly (one task each). Then they must coordinate with each other and update their selected tasks so as to reach the targeted task distribution. E.g. for 10 agents and 2 task types, the targeted distribution is to have 5 agents performing one task and the other 5 agents performing the other task. When the task types cannot be distributed exactly among the agents, we aim to reach the most equal distribution possible. E.g. for 10 agents and 3 task types, the target distribution allocates 3 agents to each of the first two task types, and 4 agents to the third type.

Coordination is achieved via local communication among agent peers (e.g. a gossip algorithm) and local adaptations based on the perceived state of the global system (e.g. deciding when and how to change the selected task). At each iteration: agents exchange their states, including their selected task, with their neighbours (adjacent agent nodes in the network); aggregate the states received from neighbours to form a global view of the network's state (how many agents have selected how many tasks of each type), update their selected task so as to get closer to the target task distribution, and forward the updated state to their neighbours.

Note: The project subject can be tuned depending on the students' interests and background. More detailed information will be provided by supervisors depending on the exact system developed (e.g. possible task-distribution algorithms, related references from literature, common types of network topologies).

Implementation

The simulator should be developed in NetLogo (https://ccl.northwestern.edu/netlogo/) or in Java.

References

[1] Ada Diaconescu, Louisa Jane Di Felice, Patricia Mellodge, “Multi-scale Feedbacks for Large-scale Coordination in Self-* Systems”, IEEE SASO 2019, Umea Sweden, 2019. (available upon request)