What was the deal between the Machine and John?

Question

In the last episode of Person of Interest, we see that Harold decides to go on top of a building to upload the Machine's copy on a satellite. He knows that whoever uploads the copy of the Machine will be dead as Samaritan is launching the missle. But finally when he reached the top, we see he is on the wrong building and is saved. Instead of him, John is on the actual building's roof and dies there. John reveals he had a deal with the Machine and the Machine also confirms the same.

(Finch on building with Machine/Root voice)
Finch: Wait, are you sure this is the right place? Yes.
Root: This is where you're supposed to be.
Finch: No, none of these dishes are capable of transmitting to a Molniya orbit. This is the wrong building.

(On other building, Reese is standing)
Reese: Right building, Finch. For you.
Finch: What are you doing?
Reese: Me and the Machine have had a long-standing arrangement. A deal. Told you. Pay you back all at once. That's the way I like it.
Finch: No, I told you. It's supposed to be me alone.
Root/Machine: Sorry, Harry. Deal's a deal. You know as well as I do that he wasn't gonna let you die.

What was that deal or arrangement? And when did John and the Machine decide it?

Answer 1

The deal was for the Machine to save Finch's life, no matter what, however I don't believe there is any one episode where John explicitly makes a deal with the machine to prioritise Finch's life over his - it's been implicit from very early on in the show that Reese 'owes' his life to Finch, and that this debt has always been outstanding.

According to Person of Interest executive producer, Jonathan Nolan:

When did Reese make that deal with the Machine to save Finch's life, no matter what, in your mind?

Nolan: I think relatively early on. Our guys have had a couple of run-ins with this situation before. There was the episode that Reese and Finch were set up with an explosive bomb threat. They've been left for dead. I think there was a fair amount of back and forth. For me, from the beginning, just the fact that Finch had basically saved Reese in the pilot. They've saved each other plenty since, but that initial act of friendship…when we meet Reese in the pilot—one of the scenes we couldn't shoot because the state of New York wouldn't let us—the initial pilot had Reese standing on the Manhattan bridge, about the toss himself into the drink. You still get that vibe in the pilot, that this is the guy who is in extremis.