Deep learning with a large number of parametersrequires distributed training, where model accuracy and runtimeare two important factors to be considered. However, there hasbeen no systematic study of the tradeoff between these two factorsduring the model training process. This paper presents Rudra, aparameter server based distributed computing framework tunedfor training large-scale deep neural networks. Using variants ofthe asynchronous stochastic gradient descent algorithm we studythe impact of synchronization protocol, stale gradient updates, minibatch size, learning rates, and number of learners on runtimeperformance and model accuracy. We introduce a new learningrate modulation strategy to counter the effect of stale gradientsand propose a new synchronization protocol that can effectivelybound the staleness in gradients, improve runtime performanceand achieve good model accuracy. Our empirical investigationreveals a principled approach for distributed training of neuralnetworks: The mini-batch size per learner should be reducedas more learners are added to the system to preserve the modelaccuracy. We validate this approach using commonly-used imageclassification benchmarks: CIFAR10 and ImageNet.