Сеть состоит из подсетей (колец), соединенных в более крупное кольцо (главное кольцо). Каждая подсеть выполняет завершающий алгоритм LCR, тогда как главное кольцо использует вариант алгоритма LCR с асинхронным запуском. Все кольца являются двунаправленными, а процессоры различают ориентацию по часовой стрелке и против часовой стрелки, что потенциально может быть использовано для оптимизации передачи сообщений.
Моя задача — экспериментально оценить корректность и производительность реализованный алгоритм путем его выполнения в сетях различных размеров и структур. Сюда входят разное количество и расположение узлов интерфейса, размеры подсетей, а также различные назначения идентификаторов. Я планирую протестировать как специально созданные назначения идентификаторов (например, идентификаторы по возрастанию по часовой стрелке или против часовой стрелки), так и случайные назначения идентификаторов.
Симулятор должен проверить, что максимальный идентификатор выбран в качестве лидера в каждое выполнение, что служит показателем правильности алгоритма. Кроме того, он должен записывать количество раундов и общее количество сообщений, переданных до завершения, чтобы оценить производительность алгоритма.
Вот мой код:
LeaderElection.java
Код: Выделить всё
import java.io.FileWriter;
import java.io.IOException;
public class LeaderElection {
public static void main(String[] args) {
int[] networkSizes = {10, 20, 30}; // Example network sizes
try (FileWriter csvWriter = new FileWriter("leader_election_results.csv")) {
// Write CSV header
csvWriter.append("Ring ID,Ring Size,Sub-Ring Size,Leader ID,Total Message Count,Rounds,Termination Status\n");
// For each network size...
for (int size : networkSizes) {
RingOfRingsNetwork network = new RingOfRingsNetwork(size, 10);
// Ensure unique IDs across all sub-rings
network.ensureUniqueIds();
// Run algorithms...
network.runAsynchronousStartLCR();
network.runTerminatingLCR();
// Write to CSV after termination
writeStatsToCSV(network, csvWriter, size);
}
} catch (IOException e) {
e.printStackTrace();
}
}
private static void writeStatsToCSV(RingOfRingsNetwork network, FileWriter csvWriter, int size) throws IOException {
// Collect and write statistics for each ring to CSV
for (int i = 0; i < network.rings.size(); i++) {
RingNetwork ring = network.rings.get(i);
csvWriter.append(String.join(",",
String.valueOf(i+1), // Ring ID
String.valueOf(size),
String.valueOf(10), // Assuming sub-ring size is 10 for simplicity
String.valueOf(ring.getLeaderId()),
String.valueOf(ring.processors.stream().mapToInt(Processor::getMessageCount).sum()),
String.valueOf(ring.processors.get(0).getMessageCount()), // Assuming all processors have the same round count
String.valueOf(ring.processors.stream().allMatch(p -> p.receivedTerminationMessage)) // Termination status
));
csvWriter.append("\n");
}
}
}
Код: Выделить всё
import java.util.*;
class Processor {
int id;
Processor next;
boolean leader;
boolean active;
int messageCount;
boolean receivedTerminationMessage;
int ultimateLeaderId;
public Processor(int id) {
this.id = id;
this.leader = false;
this.active = true;
this.messageCount = 0;
this.receivedTerminationMessage = false;
this.ultimateLeaderId = -1; // Default value indicating no ultimate leader set
}
public void incrementMessageCount() {
this.messageCount++;
System.out.println("Processor " + id + " incremented message count to " + messageCount);
}
public int getMessageCount() {
return this.messageCount;
}
public void setLeader(boolean leader) {
this.leader = leader;
}
public boolean isActive() {
return this.active;
}
public void receiveId(int newId) {
if (newId > this.id) {
System.out.println("Processor " + id + " updated ID from " + this.id + " to " + newId);
this.id = newId;
incrementMessageCount(); // Increment message count when a new ID is received and set
}
}
public void passId() {
if (this.active) {
next.receiveId(this.id); // Forward the current ID to the next processor
}
}
public void terminate() {
this.active = false;
if (this.leader) {
this.leader = true;
}
System.out.println("Processor " + id + " is now terminated.");
if (!receivedTerminationMessage) {
next.receiveTerminationSignal(); // Propagate the termination signal to the next processor
}
}
public void setUltimateLeaderId(int id) {
this.ultimateLeaderId = id; // Set the ultimate leader ID
if (this.id == id) {
setLeader(true); // If the current ID matches the ultimate leader ID, set this processor as the leader
}
System.out.println("Processor " + this.id + " acknowledges ultimate leader ID: " + this.ultimateLeaderId);
// Propagate the ultimate leader ID to the next processor only if the next processor's ID is not the same as the current processor's ID
if (next.id != this.id) {
next.setUltimateLeaderId(id);
}
}
public void receiveTerminationSignal() {
this.receivedTerminationMessage = true;
incrementMessageCount(); // Increment message count when a termination signal is received
terminate(); // Terminate the processor when a termination signal is received
}
public void setTerminationStatus(boolean status) {
this.active = !status;
}
public int getUltimateLeaderId() {
return this.ultimateLeaderId;
}
}
Код: Выделить всё
import java.util.List;
import java.util.ArrayList;
import java.util.Random;
class RingNetwork {
List
processors;
int size;
int leaderId; // ID of the elected leader
int totalMessageCount; // Total messages sent during the election
int roundCount; // Total rounds taken to elect a leader
public RingNetwork(int size) {
this.size = size;
this.processors = new ArrayList();
this.leaderId = 0;
this.totalMessageCount = 0;
this.roundCount = 0;
// Initialize processors and their next pointers
for (int i = 0; i < size; i++) {
processors.add(new Processor(i));
}
for (int i = 0; i < size; i++) {
Processor current = processors.get(i);
current.next = processors.get((i + 1) % size);
}
// Print the initial state of the ring
System.out.println("Initial state:");
for (Processor p : processors) {
System.out.println("Processor " + p.id + " -> Next Processor " + p.next.id);
}
}
public int getLeaderId() {
return this.leaderId;
}
public int getTotalMessageCount() {
return this.totalMessageCount;
}
public int getRoundCount() {
return this.roundCount;
}
public void setUltimateLeaderId(int id) {
this.leaderId = id;
// Optionally, update all processors in this ring with the ultimate leader ID
for (Processor p : processors) {
p.setUltimateLeaderId(id);
}
}
public void terminate() {
for (Processor processor : processors) {
processor.terminate();
processor.setTerminationStatus(true); // Set the termination status
}
}
public void runAsynchronousStartLCR() {
Random rand = new Random();
int maxRounds = 1000; // Maximum number of rounds to prevent infinite loop
// Assign random IDs and reset counts
for (Processor processor : processors) {
processor.id = rand.nextInt(Integer.MAX_VALUE);
}
this.totalMessageCount = 0;
this.roundCount = 0;
boolean electedLeader = false;
while (!electedLeader && this.roundCount < maxRounds) {
this.roundCount++;
for (Processor p : processors) {
if (p.isActive()) {
Processor nextActiveProcessor = p.next;
while (!nextActiveProcessor.isActive()) {
nextActiveProcessor = nextActiveProcessor.next;
}
nextActiveProcessor.receiveId(p.id);
this.totalMessageCount++;
}
if (p.isActive() && p.id == p.next.id) {
electedLeader = true;
p.setLeader(true);
this.leaderId = p.id;
System.out.println("Leader elected: Processor " + p.id);
break; // Exit the loop as soon as a leader is elected
}
}
// Print the state of the ring at the end of each round
System.out.println("End of round " + this.roundCount + ":");
for (Processor p : processors) {
System.out.println("Processor " + p.id + " -> Next Processor " + p.next.id);
}
}
}
public void runTerminatingLCR() {
// Ensure leader is elected and all processors are aware of the leader ID before terminating
if (this.leaderId == 0 || processors.stream().anyMatch(p -> p.getUltimateLeaderId() != this.leaderId)) {
System.out.println("Cannot terminate: Leader has not been elected or not all processors are aware of the leader ID");
return;
}
// Terminate all processors in this ring
terminate();
// Print the state of the ring after termination
System.out.println("State after termination:");
for (Processor p : processors) {
if (p.isActive()) {
System.out.println("Processor " + p.id + " is still active");
} else {
System.out.println("Processor " + p.id + " is terminated");
}
}
}
}
Код: Выделить всё
import java.util.ArrayList;
import java.util.List;
public class RingOfRingsNetwork {
List rings;
int totalMessageCount = 0;
int totalRounds = 0;
public RingOfRingsNetwork(int numberOfRings, int sizeOfEachRing) {
rings = new ArrayList();
for (int i = 0; i < numberOfRings; i++) {
rings.add(new RingNetwork(sizeOfEachRing));
}
ensureUniqueIds();
}
public void ensureUniqueIds() {
int id = 0;
for (RingNetwork ring : rings) {
for (Processor processor : ring.processors) {
processor.id = id++;
}
}
}
public void runAsynchronousStartLCR() {
for (RingNetwork ring : rings) {
ring.runAsynchronousStartLCR();
totalMessageCount += ring.getTotalMessageCount();
totalRounds += ring.getRoundCount();
}
electUltimateLeader();
}
public void electUltimateLeader() {
RingNetwork mainRing = new RingNetwork(rings.size());
for (int i = 0; i < rings.size(); i++) {
mainRing.processors.get(i).id = rings.get(i).getLeaderId();
}
mainRing.runAsynchronousStartLCR();
int ultimateLeaderId = mainRing.getLeaderId();
for (RingNetwork ring : rings) {
ring.setUltimateLeaderId(ultimateLeaderId);
}
totalMessageCount += mainRing.getTotalMessageCount();
totalRounds += mainRing.getRoundCount();
}
public void runTerminatingLCR() {
for (RingNetwork ring : rings) {
ring.runTerminatingLCR();
}
}
}
Повторение: выходные данные терминала показывают, что несколько процессоров подтверждают окончательный идентификатор лидера несколько раз. Это может указывать на то, что процессоры либо получают сообщение о выборе лидера несколько раз, либо алгоритм не завершает работу должным образом после подтверждения лидера.
Согласованность идентификатора лидера: в выходных данных терминала все процессоры подтверждают тот же идентификатор окончательного лидера, который кажется последовательным. Однако правильность этого идентификатора лидера (т. е. действительно ли это максимальный идентификатор для всех процессоров) необходимо проверить на соответствие требованиям алгоритма.
Состояние завершения: в выходных данных CSV все кольца помечаются статусом завершения «ЛОЖЬ», а раунды записываются как «0», что предполагает, что алгоритм не выполняет раунды должным образом или раунды и статус завершения не отслеживаются и не обновляются правильно.< /p>
Количество сообщений: общее количество сообщений в выходных файлах CSV равно «6» для колец разных размеров, что кажется маловероятным, особенно если предполагается, что алгоритм масштабируется в зависимости от размера сети. Это может указывать на проблему с подсчетом сообщений или на отсутствие вариативности в тестовых примерах.
Производительность алгоритма: единообразие подсчета сообщений и нулевые раунды во всех тестовых примерах в выходных данных CSV. может указывать на проблему с реализацией алгоритма, особенно с тем, как он проходит раунды и завершает процесс выборов.
В целом, результаты указывают на потенциальные проблемы с обработкой сообщений, ходом раунда и обнаружением завершения. , а возможно и правильность самого процесса выборов лидера. Для устранения этих несоответствий и обеспечения соответствия указанным требованиям необходимы дальнейшее исследование и отладка реализации алгоритма.
Подробнее здесь: https://stackoverflow.com/questions/781 ... s-of-rings