In this paper, we consider stochastic linear systems under the max-plus algebra. For such a system, the states are governed by the recursive equation X(n) = A(n) x X(n-1) + U-n with the initial condition X(0) = x(0). By transforming the linear system under the max-plus algebra into a sublinear system under the usual algebra, we establish various exponential upper bounds for the tail distributions of the states X(n) under the independently identically distributed (i.i.d.) assumption on {(A(n), U-n), n greater than or equal to 1} and a couple of regularity conditions on (A(1); U-1) and the initial condition x(0). These upper bounds are related to the spectral radius (or the Perron-Frobenius eigenvalue) of the nonnegative matrix in which each element is the moment generating function of the corresponding element in the state-feedback matrix A(1). In particular, we have Kingman’s upper hound for GI/GI/1 queue when the system is one-dimensional. We also show that some of these upper bounds can be achieved if A(1) is lower triangular, These bounds are applied to some commonly used systems to derive new results or strengthen known results.