The leader-follower consensus problem for multi-agent systems over directed random graphs is investigated. Motivated by the fact that inter-agent communication can be subject to random failure when agents perform tasks in a complex environment, a directed random graph is used to model the random loss of communication between agents, where the connection of the directed edge in the graph is assumed to be probabilistic and evolves according to a two-state Markov Model. In the leader-follower network, the leaders maintain a constant desired state and the followers update their states by communicating with local neighbors over the random communication network. Based on convex properties and a stochastic version of LaSalle's Invariance Principle, almost sure convergence of the followers' states to the convex hull spanned by the leaders' states is established for the leader-follower random network. A numerical simulation is provided to demonstrate the developed result. (C) 2015 Elsevier Ltd. All rights reserved.