RTFM

http://dev.mysql.com/doc/refman/5.0/en/create-procedure.html

A procedure or function is considered “deterministic” if it always produces the same result for the same input parameters, and “not deterministic” otherwise. If neither DETERMINISTIC nor NOT DETERMINISTIC is given, the default is NOT DETERMINISTIC.

For replication purposes, use of the NOW() function (or its synonyms) or RAND() does not necessarily make a routine non-deterministic. For NOW(), the binary log includes the timestamp and replicates correctly. RAND() also replicates correctly as long as it is invoked only once within a routine. (You can consider the routine execution timestamp and random number seed as implicit inputs that are identical on the master and slave.)

Currently, the DETERMINISTIC characteristic is accepted, but not yet used by the optimizer. However, if binary logging is enabled, this characteristic affects whether MySQL accepts routine definitions. See Section 17.4, “Binary Logging of Stored Routines and Triggers”.