Member Avatar for ankit_nasa

Run the algorithim for n>6. to introduce non-
determinism, number each process 0..n-1; In each
iteration, generate a random number r<=n.choose r
processes randomly and allow only the chosen ones to
execute the protocol. token sending/ recieving can be
emulated by updating appropriate recieved[] bits.
ignoring the diffusion part, see how many processes
decide in at least three different trees. if numbers
are the same , it is a coincident?

  • 3 Contributors
  • 4 Replies
  • 115 Views
  • 8 Hours Discussion Span
  • Latest Post Latest Post by orko

Dani AI

Generated

A practical way to make progress is to treat this as a small, testable simulator rather than trying to reason only on paper. Break the task into pieces: a simple Process model that holds per-tree message and decision state, a round-based scheduler that activates a random subset each step, an in-memory message-emulation layer (no sockets or threads required), and a trial loop that records how many processes decide for three or more distinct trees. Make the simulator deterministic for debugging by seeding the RNG.

Implement and verify incrementally. First, run a single trial with a small n and verbose logging so you can see tokens/messages and decisions. Next, switch to batch mode and run thousands of independent trials to collect a distribution of the counts you care about. To judge whether equal counts across trees are “coincidences,” use the empirical frequency from the Monte Carlo runs (proportion of trials that show equality). If you need a formal test, compare observed frequencies with expected ones using a chi-square or exact test.

A compact Java skeleton to get started:

class Process {
  final int id;
  boolean[] decided;   // per-tree decisions
  boolean[] inbox;     // per-tree received flags

  Process(int id, int t) {
    this.id = id;
    decided = new boolean[t];
    inbox = new boolean[t];
  }

  void act(Process[] all, Random rnd) {
    // example: if inbox[tree] and not decided, mark decided[tree]=true
    // optionally forward a token: all[rnd.nextInt(all.length)].inbox[tree]=true;
  }
}

for (int trial=0; trial<trials; trial++) {
  // init processes
  for (int round=0; round<maxRounds; round++) {
    List<Integer> order = IntStream.range(0,n).boxed().collect(Collectors.toList());
    Collections.shuffle(order, rnd);
    int k = 1 + rnd.nextInt(n); // size of active subset
    for (int i=0;i<k;i++) processes[order.get(i)].act(processes, rnd);
  }
  // count processes with decidedCount >= 3 and store result
}

As suggested, post your code when you have an attempt and include one failing trace. : start with the tiny simulator above and add logging. ’s point about fundamentals rings true—implement the pieces one at a time so you can test and debug each part.

Recommended Answers

All 4 Replies

Member Avatar for Ezzaral

No, read the announcement at the top of the forum - we do not do homework for you.

Post code that you are having difficulty with and specific questions about it. The forum is to help those who are making an honest attempt at solving their issue. It's not for those who just want the work done for them.

Member Avatar for ankit_nasa

sorry i don't know that. hey can u help me in understanding thid question. i am not geting any thing wat's the output. plssssssssss

Member Avatar for Ezzaral

sorry i don't know that. hey can u help me in understanding thid question. i am not geting any thing wat's the output. plssssssssss

As I already stated - no, you need to make the effort on your homework yourself, post your code with your questions. If you have been paying attention at all in class then you should have some understanding of the question. You didn't even post the algorithm that was supposed to be run - this is only a fragment of a question.

Member Avatar for orko

are you going to class without completing your prerequisites? i will suggest you to drop off the course and finish your pre-req course first in that case... :)

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.