Exploring the characteristic features of emergence and identifying how the macro phenomena could be affected by different classes of hypothetical micro-theories are the challenges we face in this new paradigm. Two central issues are nonlocality and stochasticity. Noise can seed emergent structures and determine macroscopic forms. Nonlocality appears when one tries to translate physics expressed in one set of collective variables suitable for one level of structure to another set. We begin with the notion of nonlocality commonly associated with EPR experiment. We present results in the evolution of entanglement between two oscillators analyzed in a field theoretical context. We then show how nonlocality is linked with stochasticity in nonequilibrium dynamics: Nonlocal dissipation and nonlocal fluctuations (colored noise) arise naturally in the open-system dynamics of Langevin and the effectively-open system dynamics of Boltzmann, and the dynamics of correlation (BBGKY) hierarchy. These features originate from the choice of coarse-graining measures and backreaction processes. We analyze these two key issues in the context of strongly correlated systems which we believe are generic properties in any theory for the microscopic structure of spacetime, viz, quantum gravity.