diff --git a/.travis.yml b/.travis.yml
index de02d78..edd12d4 100644
--- a/.travis.yml
+++ b/.travis.yml
@@ -11,23 +11,34 @@
 # limitations under the License.
 
 sudo: false
+
 language: python
+
 python:
   - "2.7"
+
 env:
-- TOX_ENV=pylint_code
-- TOX_ENV=pylint_tests
-- TOX_ENV=py27
-- TOX_ENV=py26
-- TOX_ENV=py27e2e
-- TOX_ENV=py26e2e
-- TOX_ENV=py27ssh
-- TOX_ENV=py26ssh
+  - TOX_ENV=pylint_code
+  - TOX_ENV=pylint_tests
+  - TOX_ENV=py27
+  - TOX_ENV=py26
+  - TOX_ENV=py27e2e
+  - TOX_ENV=py26e2e
+  - TOX_ENV=py27ssh
+  - TOX_ENV=py26ssh
+  - TOX_ENV=docs
+
 install:
   - pip install --upgrade pip
   - pip install --upgrade setuptools
   - pip install tox
+
 script:
   - pip --version
   - tox --version
-  - tox -e $TOX_ENV
+  - PYTEST_PROCESSES=1 tox -e $TOX_ENV
+
+# The PYTEST_PROCESSES environment var is used in tox.ini to override the --numprocesses argument
+# for PyTest's xdist plugin. The reason this is necessary is that conventional Travis environments
+# may report a large amount of available CPUs, but they they are greatly restricted. Through trial
+# and error we found that more than 1 process may result in failures.
diff --git a/tests/requirements.txt b/tests/requirements.txt
index cf57821..d86750b 100644
--- a/tests/requirements.txt
+++ b/tests/requirements.txt
@@ -10,12 +10,13 @@
 # See the License for the specific language governing permissions and
 # limitations under the License.
 
-testtools
-fasteners==0.13.0
-sh==1.12.13
+testtools==2.3.0
+fasteners==0.14.1
+sh==1.12.14
 psutil==5.2.2
-mock==1.0.1
-pylint==1.6.4
-pytest==3.0.2
-pytest-cov==2.3.1
-pytest-mock==1.2
+mock==2.0.0
+pylint==1.6.5
+pytest==3.1.3
+pytest-cov==2.5.1
+pytest-mock==1.6.0
+pytest-xdist==1.18.1
diff --git a/tox.ini b/tox.ini
index 9849b5e..129c557 100644
--- a/tox.ini
+++ b/tox.ini
@@ -12,17 +12,21 @@
 
 [tox]
 envlist=py27,py26,py27e2e,py26e2e,pywin,py27ssh,pylint_code,pylint_tests,docs
+processes={env:PYTEST_PROCESSES:auto}
 
 [testenv]
-whitelist_externals=rm
+whitelist_externals=
+  rm
 passenv=
   TRAVIS
   PYTHON
   PYTHON_VERSION
   PYTHON_ARCH
 deps=
-  -rrequirements.txt
-  -rtests/requirements.txt
+  --requirement
+    requirements.txt
+  --requirement
+    tests/requirements.txt
 basepython=
   py26: python2.6
   py27: python2.7
@@ -36,36 +40,76 @@
   docs: python2.7
 
 [testenv:py27]
-commands=pytest tests --ignore=tests/end2end --ignore=tests/orchestrator/execution_plugin/test_ssh.py --cov-report term-missing --cov aria
+commands=
+  pytest tests \
+    --numprocesses={[tox]processes} \
+    --ignore=tests/end2end \
+    --ignore=tests/orchestrator/execution_plugin/test_ssh.py \
+    --cov-report term-missing \
+    --cov aria
 
 [testenv:py26]
-commands=pytest tests --ignore=tests/end2end --ignore=tests/orchestrator/execution_plugin/test_ssh.py --cov-report term-missing --cov aria
+commands=
+  pytest tests \
+    --numprocesses={[tox]processes} \
+    --ignore=tests/end2end \
+    --ignore=tests/orchestrator/execution_plugin/test_ssh.py \
+    --cov-report term-missing \
+    --cov aria
 
 [testenv:py27e2e]
-commands=pytest tests/end2end --cov-report term-missing --cov aria
+commands=
+  pytest tests/end2end \
+    --numprocesses={[tox]processes} \
+    --cov-report term-missing \
+    --cov aria
 
 [testenv:py26e2e]
-commands=pytest tests/end2end --cov-report term-missing --cov aria
+commands=
+  pytest tests/end2end \
+    --numprocesses={[tox]processes} \
+    --cov-report term-missing \
+    --cov aria
 
 [testenv:pywin]
-commands=pytest tests --ignore=tests/end2end --ignore=tests/orchestrator/execution_plugin/test_ssh.py --cov-report term-missing --cov aria
+commands=
+  pytest tests \
+    --numprocesses={[tox]processes} \
+    --ignore=tests/end2end \
+    --ignore=tests/orchestrator/execution_plugin/test_ssh.py \
+    --cov-report term-missing \
+    --cov aria
 
 [testenv:py27ssh]
-install_command=pip install {opts} {packages} .[ssh]
-commands=pytest tests/orchestrator/execution_plugin/test_ssh.py
+install_command=
+  pip install {opts} {packages} .[ssh]
+commands=
+  pytest tests/orchestrator/execution_plugin/test_ssh.py \
+    --numprocesses={[tox]processes}
 
 [testenv:py26ssh]
-install_command=pip install {opts} {packages} .[ssh]
-commands=pytest tests/orchestrator/execution_plugin/test_ssh.py
+install_command=
+  pip install {opts} {packages} .[ssh]
+commands=
+  pytest tests/orchestrator/execution_plugin/test_ssh.py \
+  --numprocesses={[tox]processes}
 
 [testenv:pylint_code]
-commands=pylint --rcfile=aria/.pylintrc --disable=fixme,missing-docstring aria extensions/aria_extension_tosca/
+commands=
+  pylint aria extensions/aria_extension_tosca/ \
+  --rcfile=aria/.pylintrc \
+  --disable=fixme,missing-docstring
 
 [testenv:pylint_tests]
-commands=pylint --rcfile=tests/.pylintrc --disable=fixme,missing-docstring tests
+commands=
+  pylint tests \
+  --rcfile=tests/.pylintrc \
+  --disable=fixme,missing-docstring
 
 [testenv:docs]
+install_command=
+  pip install {opts} {packages} \
+    --requirement docs/requirements.txt
 commands=
-  pip install --requirement docs/requirements.txt
   rm --recursive --force docs/html
   sphinx-build -W -T -b html docs docs/html