/assignment_collatz-conjecture

Assignment to learn Message Passing with YARP

Primary LanguageC++GNU General Public License v3.0GPL-3.0

Message Passing with YARP

Gitpod

Prerequisites

You should know what the following classes are up to:

Preamble

There exists a beautiful and yet undemonstrated conjecture in Mathematics that deals with the so-called trajectories of natural numbers. It is called the Collatz conjecture.

Learn on Wikipedia what trajectories are all about and how you can compute them for each given natural N, supposedly ending up always in 1.

Assignment

We ask you to design a distributed client/server computing architecture (see the figure below) whose plumbing is based on YARP to progressively verify the Collatz conjecture. The clients will thus perform concurrent verification running on a cluster of computers.

architecture

Client Side

The Client is required to:

  • Talk to the Server according to this protocol.
  • The Client requests the Server to obtain a natural N and a threshold T to then give back the test outcome.
  • Verify the pair (N,T). The test terminates successfully if, at any step, the trajectory of N becomes lower than or equal to T. Conversely, the test will not terminate; therefore, the Server is responsible for constantly monitoring the current state of pending requests.

Server Side

The Server is required to:

  • Communicate with the Clients according to this protocol.
  • Handle a FIFO of pending requests received from the Clients according to the following policy:
    1. At start-up, the counter CNT is initialized equal to 1.
    2. At each request received from Client Ci, CNT is increased and pushed back into FIFO, while the pair (CNT,HEAD-1) is provided to Ci, being HEAD the element stored at the top of FIFO.
    3. If the Client request contains the outcome of a test, then the Server removes the corresponding element from FIFO.
  • Monitor periodically the content of FIFO in search of those elements which have not been removed since long. These elements might be possible counterexamples to the conjecture. It is sufficient to report the content of FIFO at a given rate.

Protocol

Client ➡️ Server request

A Bottle whose format is:

Header Payload
vocab_req N
  • vocab_req is a proper identifier.
  • N corresponds to the natural whose previous test was successful, or is 0 at start-up.

Server ➡️ Client response

A Bottle whose format is:

Header Payload
vocab_item N, T
  • vocab_item is a proper identifier.
  • N is the natural for which a test is required against the threshold T.

How to complete the assignment