Isn't gravity non-local and non-causal? The way I think of this is that, I can ask physical questions about a space-time which are impossible to answer unless one knows the full space-time, and hence I am inclined to believe that gravity is non-local. 
For example, sitting at a point in a black-hole space-time I can ask if the given point is inside or outside the black-hole. As far as I can see, there is no local measurement/calculation that can be done around that point which will give the answer. 
One has to know the full space-time Penrose diagram to know what is the complement of the past of the future null-infinity to know if such a region (black-hole) exists and then ask if the given event is inside that region or not. 
The very definition of a black-hole itself looks non-local to me! 
I have to know the entire Penrose diagram to know if there is a black-hole or not! 


*

*What are the most precise ways known to justify that gravity is non-local? 
How does one reconcile this with the fact that Einstein's equations local? (any differential equation is local by definition!) 

*How does string theory and/or AdS/CFT see this non-locality? 

*Similarly isn't the existence of space-times with closed timelike curves an evidence that gravity is also non-causal? 

*What are the most precise definitions of "locality" and "causality"? 

It would be great if people can refer to best known papers on these issues and if they connect to any currently exciting research question.  
 A: There are several definitions of black holes and black hole horizons.  You are correct that the event horizon is definitely a non-local phenomenon, and would not be measurable by a local observer.  This fact doesn't affect the local dynamics of that observer, though, because she would still be inhabiting a locally freely falling frame, and her dynamics could be fully worked out by the geodesic deviation equation, which IS local.  Just because you have global structures like black hole horizons and asymptotic infinities doesn't overrule this fact.  It would be similar to saying that fluid dynamics isn't local because a surfer in san diego can't tell whether the wave he's on stretches to san fransisco.  The wave might have a global structure that big, but the only important thing (for locality) is whether you can send a signal along the wave at a speed faster than the allowed wave speed.
A: 
What are the most precise definitions of "locality" and "causality"?

Causality means that a physical process happening at space time event $x$ is the physical cause of another physical process happening at space-time event $y$
Relativist locality (in special relativity) says that physical quantities at space-time event $x$ cannot be the cause of other physical quantities at space-time event $y$, if the events $x$ and $y$ are separated by a space-like interval : $(\Delta s)^2(x,y)=(x-y)^2<0$ (in a metrics $g = Diag(1,-1,-1,-1)$
In Quantum Field Theory, this is expressed as : $[\Phi(x), \Phi'(y)]_{(x-y)^2<0} = 0$, where $\Phi, \Phi'$ are any physical measurable quantities (hermitian operators).

What are the most precise ways known to justify that gravity is
  non-local? How does one reconcile this with the fact that Einstein's
  equations local? (any differential equation is local by definition!)

The problem, is that, for any space-time point $x$, we may choose frames, which  are (locally) inertial frames. So, locally (at $x$) - and only locally -, the effects of gravity are being cancelled, just by a change of frame. This is the consequence of the invariance by diffeomorphism of the Einstein equations. So, inevitably, there is a pseudo "non-local" appearance character of gravity. But the expression "non-local" is not a good choice, because  that does not mean at all that you can send an instantaneous information, or locally violate special relativity. This just comes for the freedom to choose frames at some space-time point $x$. Note that one of the consequences is that you cannot find a total stress-energy tensor which is both covariant and conserved.
A: 
Similarly isn't the existence of space-times with closed timelike curves an evidence that gravity is also non-causal?

Well, it's evidence that GR admits solutions where causality is problematical, but all the time machines I know about require stress-energy tensors that are unphysical. My own view is that GR is a superset of the real world, and as long as we confine ourselves to realistic stress-energy tensors there is no violation of causality.
A: You're right that the definition of a black hole based on an event horizon is non-local - you need to examine the entire future evolution to check if a light ray makes it to $\mathcal{I}^+ $.  However, more local alternative definitions have been discussed, such as those involving apparent horizons: You basically define a closed two-surface to be trapped if, when you look at the pair of future-oriented null directions which are orthogonal to it, you find that they're converging as the surface evolves in time.  A point on a timeslice is trapped if it lies on a trapped surface in the timeslice.  The apparent horizon is then the boundary of the union of the trapped points.
This just makes use of local quantities - the test for convergence of the null directions is computed using derivatives only.  No need to wait for future null infinity!  More discussion and refinements here.
