Let's say we have two routers running a BGP that is fully converged and both routers are advertising routes to each other. The link between them fails (physically so to speak). Now, after the hold down timer and both routers deemed the other as down. What happens when the link comes back to life? Do we have to re-configure the BGP session all over again? If not, what happens to the networks that are advertised from each router to the other? Is it instantly advertised again once the link comes back up, or there is some kind of update timer so that each router deems the other as an up neighbor?
It's treated as a fresh session up when the peers restart. TCP handshake, capability re-negotiation, address family advertisement, and then NLRI exchange. If the hold down timer expires, the peer is marked as dead, the session goes into the IDLE state, and follows its own rules for transitioning from IDLE to Active (actively attempting to establish a TCP connection). Note that a peer in the IDLE state can still accept an inbound TCP handshake from the other router.
Exact time needed for a specific route to be available again is dependent on the total # of NLRIs to be exchanged between the two routers. If you're exchanging full tables (500K+ NLRI), depending on processor size on both routers, it could take upwards of 5 minutes. If you only have 20 routes to announce, they'll process the NLRI real quick like.
BGP sends KEEPALIVE packets in specified interval (60 seconds by default). If BGP not received 3 keepalive packets from neighbour, HOLD DOWN timer expires and the neighbour is considered as dead. Assuming the neighbor is down, shutting down the BGP session, and withdrawing all routes from it's announcements.
HOLD DOWN timer, it's three times KEEPALIVE (180 seconds by default).
When link between BGP peers came back to life (physically) and neighbours received KEEPALIVE packets the session is automatically UP. Peers starts advertise their routes in announcements, according to specified criteria. You don't have to reconfigure BGP session again. It would not make sense, because in real environments, BGP session fails quite a often.