I found out my master's thesis topic has already been done (exactly), and my advisor didn't mention this when suggesting it to me - how to proceed?

Note that there is no way anyone knows about your precise situation, except you and your advisor, so I am making some wild guesses on what actually happened.

Perhaps your advisor is hoping to have an efficient implementation of the ideas / algorithms already expressed on the past paper, with the notion that he (or you and him) may later build on your implementation to create something new. In order to create anything new, you have to compare with existing approaches and therefore you still have to implement previous methods. He has given you two options a) Try to expand the ideas of the past paper b) If you cannot do that, just creating a NEW implementation of the original paper is enough for him. This is a MSc thesis and not all MSc theses lead to publishable results. But it still seems like an important project and as such, it seems it could still turn out to be a good MSc thesis and you will have a lot to learn from it.

So, your main problem is that you think that you cannot expand the original paper to new directions. But if you want to do research this is exactly what you are going to have to do. You should find a topic that interests you ("my supervisor gave a research plan exactly about what i want to do"), study previous literature (which you should have done before choosing the topic) and then expand on previous ideas. Note that since you have worked in industry, you may as well be a better programmer than those 2 PHD students and therefore your implementation might be much more efficient than theirs. This is still a significant contribution which may eventually be published.

My advice:

• Talk to your advisor and state your doubts and clarify the situation.
• Implement the paper's ideas as fast and efficient as possible
• Compare your implementation with the paper's results. You should at least aim for a more efficient implementation
• Check related literature that cites this paper. Is this paper, still state-of-the-art? Is this paper cited by anyone? This will show if this project has been picked up by anyone. If it is not, it is reasonable that your advisor wants to build upon the previous paper to further expand it. If someone has extended it or applied it to other use-cases, your assumption that it cannot be improved is wrong and you should think what you can do to further expand it. Either way, you will have an answer about how to proceed.
• Think of any other possible improvements, what else could be done better, in a more efficient way or how this idea could be used in other use-cases.

Also, you have learnt a valuable lesson. What you want to do in research should correlate with what is already been done. You should study previous research very carefully and exhaustively. If you believe that previous works have already done everything to perfection (which BTW is rarely the case) then you should choose a new topic. Otherwise you are the one that should think what can be improved. I think you pretty much expected that your advisor had a new research idea waiting just for you and all you needed to do was just to implement it. But this was really an unrealistic expectation on your part.

For a master's thesis it is nice but not completely essential to do something original. I'm sorry that it feels like you're rediscovering what is already known.

Now that you're in that situation, though, the best option is likely to write your results as a test of the published results or a comparison between the published results and something else. For example, you can use different data, compare some aspect that wasn't covered before (resource usage?), write more of a review or try to get different other partial/possible solutions running to compare against. Is the other code open source? If not, open-source yours (assuming your advisor is okay with it). Are there missing steps that are important? Describe them well.

Also, although it feels like a waste of time to repeat the same stuff (and often it is), there is a benefit to thoroughly testing out and verifying what is supposedly known. Just because something's published it isn't necessarily true or useful or accurate. In this case from what you've said it sounds like it is--but if you believe this was useful work for someone to have done, it is also useful for it to be independently verified, which you have done. I wish this were done more in academia, honestly. Too much poorly-verified and over-hyped stuff gets through. But it's hard to publish a paper saying, "I checked important result X and yep!...it was right on target."

It's harder to know what precisely to do about the academic honesty issue. You may wish to discreetly contact whoever is in charge of administrative ethics at your school (preferably some sort of grad student ethics advisor, so they can advise you on whether this sounds like a big problem). But if it's a problem it's a problem for your professor; I wouldn't let it derail your thesis unless absolutely necessary.

In mathematics it's often OK to have a master's thesis be expository, of course as long as it is clearly indicated that it is expository, and it is (of course) written in one's own words, well-referenced, etc. Usually in this case it's better if the expository work provides either a new proof of a known result, or a new perspective on the old result.

I'm sorry if this doesn't answer the academic honesty concerns, but is there any way you can take this spin?