diff --git a/src/main/java/com/google/devtools/build/lib/remote/ByteStreamBuildEventArtifactUploader.java b/src/main/java/com/google/devtools/build/lib/remote/ByteStreamBuildEventArtifactUploader.java
index 0ca33b6..92177fc 100644
--- a/src/main/java/com/google/devtools/build/lib/remote/ByteStreamBuildEventArtifactUploader.java
+++ b/src/main/java/com/google/devtools/build/lib/remote/ByteStreamBuildEventArtifactUploader.java
@@ -30,13 +30,10 @@
 import com.google.devtools.build.lib.buildeventstream.PathConverter;
 import com.google.devtools.build.lib.collect.ImmutableIterable;
 import com.google.devtools.build.lib.remote.common.MissingDigestsFinder;
-import com.google.devtools.build.lib.remote.common.NetworkTime;
 import com.google.devtools.build.lib.remote.common.RemoteActionExecutionContext;
-import com.google.devtools.build.lib.remote.common.RemoteActionExecutionContextImpl;
 import com.google.devtools.build.lib.remote.util.DigestUtil;
 import com.google.devtools.build.lib.remote.util.TracingMetadataUtils;
 import com.google.devtools.build.lib.vfs.Path;
-import io.grpc.Context;
 import io.netty.util.AbstractReferenceCounted;
 import io.netty.util.ReferenceCounted;
 import java.io.IOException;
@@ -161,7 +158,9 @@
    */
   private ListenableFuture<ImmutableIterable<PathMetadata>> queryRemoteCache(
       ImmutableList<ListenableFuture<PathMetadata>> allPaths) throws Exception {
-    Context ctx = TracingMetadataUtils.contextWithMetadata(buildRequestId, commandId, "bes-upload");
+    RequestMetadata metadata =
+        TracingMetadataUtils.buildMetadata(buildRequestId, commandId, "bes-upload");
+    RemoteActionExecutionContext context = RemoteActionExecutionContext.create(metadata);
 
     List<PathMetadata> knownRemotePaths = new ArrayList<>(allPaths.size());
     List<PathMetadata> filesToQuery = new ArrayList<>();
@@ -181,7 +180,7 @@
       return Futures.immediateFuture(ImmutableIterable.from(knownRemotePaths));
     }
     return Futures.transform(
-        ctx.call(() -> missingDigestsFinder.findMissingDigests(digestsToQuery)),
+        missingDigestsFinder.findMissingDigests(context, digestsToQuery),
         (missingDigests) -> {
           List<PathMetadata> filesToQueryUpdated = processQueryResult(missingDigests, filesToQuery);
           return ImmutableIterable.from(Iterables.concat(knownRemotePaths, filesToQueryUpdated));
@@ -197,8 +196,7 @@
       ImmutableIterable<PathMetadata> allPaths) {
     RequestMetadata metadata =
         TracingMetadataUtils.buildMetadata(buildRequestId, commandId, "bes-upload");
-    RemoteActionExecutionContext context =
-        new RemoteActionExecutionContextImpl(metadata, new NetworkTime());
+    RemoteActionExecutionContext context = RemoteActionExecutionContext.create(metadata);
 
     ImmutableList.Builder<ListenableFuture<PathMetadata>> allPathsUploaded =
         ImmutableList.builder();
diff --git a/src/main/java/com/google/devtools/build/lib/remote/ByteStreamUploader.java b/src/main/java/com/google/devtools/build/lib/remote/ByteStreamUploader.java
index bba8593..0301037 100644
--- a/src/main/java/com/google/devtools/build/lib/remote/ByteStreamUploader.java
+++ b/src/main/java/com/google/devtools/build/lib/remote/ByteStreamUploader.java
@@ -208,7 +208,6 @@
    *     boolean)} instead.
    */
   @Deprecated
-  @VisibleForTesting
   public ListenableFuture<Void> uploadBlobAsync(
       RemoteActionExecutionContext context, HashCode hash, Chunker chunker, boolean forceUpload) {
     Digest digest =
diff --git a/src/main/java/com/google/devtools/build/lib/remote/ExperimentalGrpcRemoteExecutor.java b/src/main/java/com/google/devtools/build/lib/remote/ExperimentalGrpcRemoteExecutor.java
index ea99931..41f5306 100644
--- a/src/main/java/com/google/devtools/build/lib/remote/ExperimentalGrpcRemoteExecutor.java
+++ b/src/main/java/com/google/devtools/build/lib/remote/ExperimentalGrpcRemoteExecutor.java
@@ -19,6 +19,7 @@
 import build.bazel.remote.execution.v2.ExecuteResponse;
 import build.bazel.remote.execution.v2.ExecutionGrpc;
 import build.bazel.remote.execution.v2.ExecutionGrpc.ExecutionBlockingStub;
+import build.bazel.remote.execution.v2.RequestMetadata;
 import build.bazel.remote.execution.v2.WaitExecutionRequest;
 import com.google.common.base.Preconditions;
 import com.google.devtools.build.lib.authandtls.CallCredentialsProvider;
@@ -26,6 +27,7 @@
 import com.google.devtools.build.lib.remote.RemoteRetrier.ProgressiveBackoff;
 import com.google.devtools.build.lib.remote.Retrier.Backoff;
 import com.google.devtools.build.lib.remote.common.OperationObserver;
+import com.google.devtools.build.lib.remote.common.RemoteActionExecutionContext;
 import com.google.devtools.build.lib.remote.common.RemoteExecutionClient;
 import com.google.devtools.build.lib.remote.options.RemoteOptions;
 import com.google.devtools.build.lib.remote.util.TracingMetadataUtils;
@@ -71,9 +73,9 @@
     this.retrier = retrier;
   }
 
-  private ExecutionBlockingStub executionBlockingStub() {
+  private ExecutionBlockingStub executionBlockingStub(RequestMetadata metadata) {
     return ExecutionGrpc.newBlockingStub(channel)
-        .withInterceptors(TracingMetadataUtils.attachMetadataFromContextInterceptor())
+        .withInterceptors(TracingMetadataUtils.attachMetadataInterceptor(metadata))
         .withCallCredentials(callCredentialsProvider.getCallCredentials())
         .withDeadlineAfter(remoteOptions.remoteTimeout.getSeconds(), SECONDS);
   }
@@ -310,11 +312,16 @@
   }
 
   @Override
-  public ExecuteResponse executeRemotely(ExecuteRequest request, OperationObserver observer)
+  public ExecuteResponse executeRemotely(
+      RemoteActionExecutionContext context, ExecuteRequest request, OperationObserver observer)
       throws IOException, InterruptedException {
     Execution execution =
         new Execution(
-            request, observer, retrier, callCredentialsProvider, this::executionBlockingStub);
+            request,
+            observer,
+            retrier,
+            callCredentialsProvider,
+            () -> this.executionBlockingStub(context.getRequestMetadata()));
     return execution.start();
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/remote/GrpcCacheClient.java b/src/main/java/com/google/devtools/build/lib/remote/GrpcCacheClient.java
index b2aeb4a..29ee7ac 100644
--- a/src/main/java/com/google/devtools/build/lib/remote/GrpcCacheClient.java
+++ b/src/main/java/com/google/devtools/build/lib/remote/GrpcCacheClient.java
@@ -56,7 +56,6 @@
 import com.google.devtools.build.lib.remote.util.Utils;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.protobuf.ByteString;
-import io.grpc.Context;
 import io.grpc.Status;
 import io.grpc.Status.Code;
 import io.grpc.StatusRuntimeException;
@@ -122,9 +121,11 @@
     return (options.maxOutboundMessageSize - overhead) / digestSize;
   }
 
-  private ContentAddressableStorageFutureStub casFutureStub() {
+  private ContentAddressableStorageFutureStub casFutureStub(RemoteActionExecutionContext context) {
     return ContentAddressableStorageGrpc.newFutureStub(channel)
-        .withInterceptors(TracingMetadataUtils.attachMetadataFromContextInterceptor())
+        .withInterceptors(
+            TracingMetadataUtils.attachMetadataInterceptor(context.getRequestMetadata()),
+            new NetworkTimeInterceptor(context::getNetworkTime))
         .withCallCredentials(callCredentialsProvider.getCallCredentials())
         .withDeadlineAfter(options.remoteTimeout.getSeconds(), TimeUnit.SECONDS);
   }
@@ -176,7 +177,8 @@
   }
 
   @Override
-  public ListenableFuture<ImmutableSet<Digest>> findMissingDigests(Iterable<Digest> digests) {
+  public ListenableFuture<ImmutableSet<Digest>> findMissingDigests(
+      RemoteActionExecutionContext context, Iterable<Digest> digests) {
     if (Iterables.isEmpty(digests)) {
       return Futures.immediateFuture(ImmutableSet.of());
     }
@@ -187,13 +189,13 @@
     for (Digest digest : digests) {
       requestBuilder.addBlobDigests(digest);
       if (requestBuilder.getBlobDigestsCount() == maxMissingBlobsDigestsPerMessage) {
-        getMissingDigestCalls.add(getMissingDigests(requestBuilder.build()));
+        getMissingDigestCalls.add(getMissingDigests(context, requestBuilder.build()));
         requestBuilder.clearBlobDigests();
       }
     }
 
     if (requestBuilder.getBlobDigestsCount() > 0) {
-      getMissingDigestCalls.add(getMissingDigests(requestBuilder.build()));
+      getMissingDigestCalls.add(getMissingDigests(context, requestBuilder.build()));
     }
 
     ListenableFuture<ImmutableSet<Digest>> success =
@@ -209,7 +211,7 @@
                 },
                 MoreExecutors.directExecutor());
 
-    RequestMetadata requestMetadata = TracingMetadataUtils.fromCurrentContext();
+    RequestMetadata requestMetadata = context.getRequestMetadata();
     return Futures.catchingAsync(
         success,
         RuntimeException.class,
@@ -226,10 +228,9 @@
   }
 
   private ListenableFuture<FindMissingBlobsResponse> getMissingDigests(
-      FindMissingBlobsRequest request) {
-    Context ctx = Context.current();
+      RemoteActionExecutionContext context, FindMissingBlobsRequest request) {
     return Utils.refreshIfUnauthenticatedAsync(
-        () -> retrier.executeAsync(() -> ctx.call(() -> casFutureStub().findMissingBlobs(request))),
+        () -> retrier.executeAsync(() -> casFutureStub(context).findMissingBlobs(request)),
         callCredentialsProvider);
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/remote/GrpcRemoteExecutor.java b/src/main/java/com/google/devtools/build/lib/remote/GrpcRemoteExecutor.java
index 22b068b..0b8c3fa 100644
--- a/src/main/java/com/google/devtools/build/lib/remote/GrpcRemoteExecutor.java
+++ b/src/main/java/com/google/devtools/build/lib/remote/GrpcRemoteExecutor.java
@@ -18,11 +18,13 @@
 import build.bazel.remote.execution.v2.ExecuteResponse;
 import build.bazel.remote.execution.v2.ExecutionGrpc;
 import build.bazel.remote.execution.v2.ExecutionGrpc.ExecutionBlockingStub;
+import build.bazel.remote.execution.v2.RequestMetadata;
 import build.bazel.remote.execution.v2.WaitExecutionRequest;
 import com.google.common.base.Preconditions;
 import com.google.devtools.build.lib.authandtls.CallCredentialsProvider;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadSafe;
 import com.google.devtools.build.lib.remote.common.OperationObserver;
+import com.google.devtools.build.lib.remote.common.RemoteActionExecutionContext;
 import com.google.devtools.build.lib.remote.common.RemoteExecutionClient;
 import com.google.devtools.build.lib.remote.util.TracingMetadataUtils;
 import com.google.devtools.build.lib.remote.util.Utils;
@@ -55,9 +57,9 @@
     this.retrier = retrier;
   }
 
-  private ExecutionBlockingStub execBlockingStub() {
+  private ExecutionBlockingStub execBlockingStub(RequestMetadata metadata) {
     return ExecutionGrpc.newBlockingStub(channel)
-        .withInterceptors(TracingMetadataUtils.attachMetadataFromContextInterceptor())
+        .withInterceptors(TracingMetadataUtils.attachMetadataInterceptor(metadata))
         .withCallCredentials(callCredentialsProvider.getCallCredentials());
   }
 
@@ -105,7 +107,8 @@
    *   trigger a retry of the Execute call, resulting in a new Operation.
    * */
   @Override
-  public ExecuteResponse executeRemotely(ExecuteRequest request, OperationObserver observer)
+  public ExecuteResponse executeRemotely(
+      RemoteActionExecutionContext context, ExecuteRequest request, OperationObserver observer)
       throws IOException, InterruptedException {
     // Execute has two components: the Execute call and (optionally) the WaitExecution call.
     // This is the simple flow without any errors:
@@ -149,9 +152,9 @@
                             WaitExecutionRequest.newBuilder()
                                 .setName(operation.get().getName())
                                 .build();
-                        replies = execBlockingStub().waitExecution(wr);
+                        replies = execBlockingStub(context.getRequestMetadata()).waitExecution(wr);
                       } else {
-                        replies = execBlockingStub().execute(request);
+                        replies = execBlockingStub(context.getRequestMetadata()).execute(request);
                       }
                       try {
                         while (replies.hasNext()) {
diff --git a/src/main/java/com/google/devtools/build/lib/remote/NetworkTimeInterceptor.java b/src/main/java/com/google/devtools/build/lib/remote/NetworkTimeInterceptor.java
index ac953aa..571456c 100644
--- a/src/main/java/com/google/devtools/build/lib/remote/NetworkTimeInterceptor.java
+++ b/src/main/java/com/google/devtools/build/lib/remote/NetworkTimeInterceptor.java
@@ -19,7 +19,6 @@
 import io.grpc.Channel;
 import io.grpc.ClientCall;
 import io.grpc.ClientInterceptor;
-import io.grpc.Context;
 import io.grpc.ForwardingClientCall;
 import io.grpc.ForwardingClientCallListener;
 import io.grpc.Metadata;
@@ -30,7 +29,6 @@
 /** The ClientInterceptor used to track network time. */
 public class NetworkTimeInterceptor implements ClientInterceptor {
 
-  public static final Context.Key<NetworkTime> CONTEXT_KEY = Context.key("remote-network-time");
   private final Supplier<NetworkTime> networkTimeSupplier;
 
   public NetworkTimeInterceptor(Supplier<NetworkTime> networkTimeSupplier) {
diff --git a/src/main/java/com/google/devtools/build/lib/remote/RemoteActionInputFetcher.java b/src/main/java/com/google/devtools/build/lib/remote/RemoteActionInputFetcher.java
index e78c168..a9e7246 100644
--- a/src/main/java/com/google/devtools/build/lib/remote/RemoteActionInputFetcher.java
+++ b/src/main/java/com/google/devtools/build/lib/remote/RemoteActionInputFetcher.java
@@ -33,15 +33,12 @@
 import com.google.devtools.build.lib.profiler.ProfilerTask;
 import com.google.devtools.build.lib.profiler.SilentCloseable;
 import com.google.devtools.build.lib.remote.common.CacheNotFoundException;
-import com.google.devtools.build.lib.remote.common.NetworkTime;
 import com.google.devtools.build.lib.remote.common.RemoteActionExecutionContext;
-import com.google.devtools.build.lib.remote.common.RemoteActionExecutionContextImpl;
 import com.google.devtools.build.lib.remote.util.DigestUtil;
 import com.google.devtools.build.lib.remote.util.TracingMetadataUtils;
 import com.google.devtools.build.lib.remote.util.Utils;
 import com.google.devtools.build.lib.sandbox.SandboxHelpers;
 import com.google.devtools.build.lib.vfs.Path;
-import io.grpc.Context;
 import java.io.IOException;
 import java.util.HashMap;
 import java.util.HashSet;
@@ -167,48 +164,42 @@
       if (download == null) {
         RequestMetadata requestMetadata =
             TracingMetadataUtils.buildMetadata(buildRequestId, commandId, metadata.getActionId());
-        RemoteActionExecutionContext remoteActionExecutionContext =
-            new RemoteActionExecutionContextImpl(requestMetadata, new NetworkTime());
-        Context ctx = TracingMetadataUtils.contextWithMetadata(requestMetadata);
-        Context prevCtx = ctx.attach();
-        try {
-          Digest digest = DigestUtil.buildDigest(metadata.getDigest(), metadata.getSize());
-          download = remoteCache.downloadFile(remoteActionExecutionContext, path, digest);
-          downloadsInProgress.put(path, download);
-          Futures.addCallback(
-              download,
-              new FutureCallback<Void>() {
-                @Override
-                public void onSuccess(Void v) {
-                  synchronized (lock) {
-                    downloadsInProgress.remove(path);
-                    downloadedPaths.add(path);
-                  }
+        RemoteActionExecutionContext context = RemoteActionExecutionContext.create(requestMetadata);
 
-                  try {
-                    path.chmod(0755);
-                  } catch (IOException e) {
-                    logger.atWarning().withCause(e).log("Failed to chmod 755 on %s", path);
-                  }
+        Digest digest = DigestUtil.buildDigest(metadata.getDigest(), metadata.getSize());
+        download = remoteCache.downloadFile(context, path, digest);
+        downloadsInProgress.put(path, download);
+        Futures.addCallback(
+            download,
+            new FutureCallback<Void>() {
+              @Override
+              public void onSuccess(Void v) {
+                synchronized (lock) {
+                  downloadsInProgress.remove(path);
+                  downloadedPaths.add(path);
                 }
 
-                @Override
-                public void onFailure(Throwable t) {
-                  synchronized (lock) {
-                    downloadsInProgress.remove(path);
-                  }
-                  try {
-                    path.delete();
-                  } catch (IOException e) {
-                    logger.atWarning().withCause(e).log(
-                        "Failed to delete output file after incomplete download: %s", path);
-                  }
+                try {
+                  path.chmod(0755);
+                } catch (IOException e) {
+                  logger.atWarning().withCause(e).log("Failed to chmod 755 on %s", path);
                 }
-              },
-              MoreExecutors.directExecutor());
-        } finally {
-          ctx.detach(prevCtx);
-        }
+              }
+
+              @Override
+              public void onFailure(Throwable t) {
+                synchronized (lock) {
+                  downloadsInProgress.remove(path);
+                }
+                try {
+                  path.delete();
+                } catch (IOException e) {
+                  logger.atWarning().withCause(e).log(
+                      "Failed to delete output file after incomplete download: %s", path);
+                }
+              }
+            },
+            MoreExecutors.directExecutor());
       }
       return download;
     }
diff --git a/src/main/java/com/google/devtools/build/lib/remote/RemoteCache.java b/src/main/java/com/google/devtools/build/lib/remote/RemoteCache.java
index 3496243..6bfc730 100644
--- a/src/main/java/com/google/devtools/build/lib/remote/RemoteCache.java
+++ b/src/main/java/com/google/devtools/build/lib/remote/RemoteCache.java
@@ -188,7 +188,8 @@
     digests.addAll(digestToFile.keySet());
     digests.addAll(digestToBlobs.keySet());
 
-    ImmutableSet<Digest> digestsToUpload = getFromFuture(cacheProtocol.findMissingDigests(digests));
+    ImmutableSet<Digest> digestsToUpload =
+        getFromFuture(cacheProtocol.findMissingDigests(context, digests));
     ImmutableList.Builder<ListenableFuture<Void>> uploads = ImmutableList.builder();
     for (Digest digest : digestsToUpload) {
       Path file = digestToFile.get(digest);
diff --git a/src/main/java/com/google/devtools/build/lib/remote/RemoteExecutionCache.java b/src/main/java/com/google/devtools/build/lib/remote/RemoteExecutionCache.java
index 4398404..c0db565 100644
--- a/src/main/java/com/google/devtools/build/lib/remote/RemoteExecutionCache.java
+++ b/src/main/java/com/google/devtools/build/lib/remote/RemoteExecutionCache.java
@@ -62,7 +62,7 @@
     Iterable<Digest> allDigests =
         Iterables.concat(merkleTree.getAllDigests(), additionalInputs.keySet());
     ImmutableSet<Digest> missingDigests =
-        getFromFuture(cacheProtocol.findMissingDigests(allDigests));
+        getFromFuture(cacheProtocol.findMissingDigests(context, allDigests));
 
     List<ListenableFuture<Void>> uploadFutures = new ArrayList<>();
     for (Digest missingDigest : missingDigests) {
diff --git a/src/main/java/com/google/devtools/build/lib/remote/RemoteRepositoryRemoteExecutor.java b/src/main/java/com/google/devtools/build/lib/remote/RemoteRepositoryRemoteExecutor.java
index f4a05dc..a74c42f 100644
--- a/src/main/java/com/google/devtools/build/lib/remote/RemoteRepositoryRemoteExecutor.java
+++ b/src/main/java/com/google/devtools/build/lib/remote/RemoteRepositoryRemoteExecutor.java
@@ -29,10 +29,8 @@
 import com.google.devtools.build.lib.profiler.Profiler;
 import com.google.devtools.build.lib.profiler.ProfilerTask;
 import com.google.devtools.build.lib.profiler.SilentCloseable;
-import com.google.devtools.build.lib.remote.common.NetworkTime;
 import com.google.devtools.build.lib.remote.common.OperationObserver;
 import com.google.devtools.build.lib.remote.common.RemoteActionExecutionContext;
-import com.google.devtools.build.lib.remote.common.RemoteActionExecutionContextImpl;
 import com.google.devtools.build.lib.remote.common.RemoteCacheClient.ActionKey;
 import com.google.devtools.build.lib.remote.common.RemoteExecutionClient;
 import com.google.devtools.build.lib.remote.merkletree.MerkleTree;
@@ -43,7 +41,6 @@
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
 import com.google.protobuf.Message;
-import io.grpc.Context;
 import java.io.IOException;
 import java.time.Duration;
 import java.util.Map;
@@ -110,61 +107,48 @@
       throws IOException, InterruptedException {
     RequestMetadata metadata =
         TracingMetadataUtils.buildMetadata(buildRequestId, commandId, "repository_rule");
-    Context requestCtx = TracingMetadataUtils.contextWithMetadata(metadata);
-    Context prev = requestCtx.attach();
-    try {
-      Platform platform = PlatformUtils.buildPlatformProto(executionProperties);
-      Command command =
-          RemoteSpawnRunner.buildCommand(
-              /* outputs= */ ImmutableList.of(),
-              arguments,
-              environment,
-              platform,
-              workingDirectory);
-      Digest commandHash = digestUtil.compute(command);
-      MerkleTree merkleTree = MerkleTree.build(inputFiles, digestUtil);
-      Action action =
-          RemoteSpawnRunner.buildAction(
-              commandHash, merkleTree.getRootDigest(), timeout, acceptCached);
-      Digest actionDigest = digestUtil.compute(action);
-      ActionKey actionKey = new ActionKey(actionDigest);
-      RemoteActionExecutionContext remoteActionExecutionContext =
-          new RemoteActionExecutionContextImpl(metadata, new NetworkTime());
-      ActionResult actionResult;
-      try (SilentCloseable c =
-          Profiler.instance().profile(ProfilerTask.REMOTE_CACHE_CHECK, "check cache hit")) {
-        actionResult =
-            remoteCache.downloadActionResult(
-                remoteActionExecutionContext, actionKey, /* inlineOutErr= */ true);
-      }
-      if (actionResult == null || actionResult.getExitCode() != 0) {
-        try (SilentCloseable c =
-            Profiler.instance().profile(ProfilerTask.UPLOAD_TIME, "upload missing inputs")) {
-          Map<Digest, Message> additionalInputs = Maps.newHashMapWithExpectedSize(2);
-          additionalInputs.put(actionDigest, action);
-          additionalInputs.put(commandHash, command);
+    RemoteActionExecutionContext context = RemoteActionExecutionContext.create(metadata);
 
-          remoteCache.ensureInputsPresent(
-              remoteActionExecutionContext, merkleTree, additionalInputs);
-        }
-
-        try (SilentCloseable c =
-            Profiler.instance().profile(ProfilerTask.REMOTE_EXECUTION, "execute remotely")) {
-          ExecuteRequest executeRequest =
-              ExecuteRequest.newBuilder()
-                  .setActionDigest(actionDigest)
-                  .setInstanceName(remoteInstanceName)
-                  .setSkipCacheLookup(!acceptCached)
-                  .build();
-
-          ExecuteResponse response =
-              remoteExecutor.executeRemotely(executeRequest, OperationObserver.NO_OP);
-          actionResult = response.getResult();
-        }
-      }
-      return downloadOutErr(remoteActionExecutionContext, actionResult);
-    } finally {
-      requestCtx.detach(prev);
+    Platform platform = PlatformUtils.buildPlatformProto(executionProperties);
+    Command command =
+        RemoteSpawnRunner.buildCommand(
+            /* outputs= */ ImmutableList.of(), arguments, environment, platform, workingDirectory);
+    Digest commandHash = digestUtil.compute(command);
+    MerkleTree merkleTree = MerkleTree.build(inputFiles, digestUtil);
+    Action action =
+        RemoteSpawnRunner.buildAction(
+            commandHash, merkleTree.getRootDigest(), timeout, acceptCached);
+    Digest actionDigest = digestUtil.compute(action);
+    ActionKey actionKey = new ActionKey(actionDigest);
+    ActionResult actionResult;
+    try (SilentCloseable c =
+        Profiler.instance().profile(ProfilerTask.REMOTE_CACHE_CHECK, "check cache hit")) {
+      actionResult = remoteCache.downloadActionResult(context, actionKey, /* inlineOutErr= */ true);
     }
+    if (actionResult == null || actionResult.getExitCode() != 0) {
+      try (SilentCloseable c =
+          Profiler.instance().profile(ProfilerTask.UPLOAD_TIME, "upload missing inputs")) {
+        Map<Digest, Message> additionalInputs = Maps.newHashMapWithExpectedSize(2);
+        additionalInputs.put(actionDigest, action);
+        additionalInputs.put(commandHash, command);
+
+        remoteCache.ensureInputsPresent(context, merkleTree, additionalInputs);
+      }
+
+      try (SilentCloseable c =
+          Profiler.instance().profile(ProfilerTask.REMOTE_EXECUTION, "execute remotely")) {
+        ExecuteRequest executeRequest =
+            ExecuteRequest.newBuilder()
+                .setActionDigest(actionDigest)
+                .setInstanceName(remoteInstanceName)
+                .setSkipCacheLookup(!acceptCached)
+                .build();
+
+        ExecuteResponse response =
+            remoteExecutor.executeRemotely(context, executeRequest, OperationObserver.NO_OP);
+        actionResult = response.getResult();
+      }
+    }
+    return downloadOutErr(context, actionResult);
   }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/remote/RemoteServerCapabilities.java b/src/main/java/com/google/devtools/build/lib/remote/RemoteServerCapabilities.java
index bd528c3..2cc9d81 100644
--- a/src/main/java/com/google/devtools/build/lib/remote/RemoteServerCapabilities.java
+++ b/src/main/java/com/google/devtools/build/lib/remote/RemoteServerCapabilities.java
@@ -22,13 +22,14 @@
 import build.bazel.remote.execution.v2.GetCapabilitiesRequest;
 import build.bazel.remote.execution.v2.PriorityCapabilities;
 import build.bazel.remote.execution.v2.PriorityCapabilities.PriorityRange;
+import build.bazel.remote.execution.v2.RequestMetadata;
 import build.bazel.remote.execution.v2.ServerCapabilities;
 import com.google.common.base.Strings;
 import com.google.common.collect.ImmutableList;
+import com.google.devtools.build.lib.remote.common.RemoteActionExecutionContext;
 import com.google.devtools.build.lib.remote.options.RemoteOptions;
 import com.google.devtools.build.lib.remote.util.TracingMetadataUtils;
 import io.grpc.CallCredentials;
-import io.grpc.Context;
 import io.grpc.StatusRuntimeException;
 import java.io.IOException;
 import java.util.List;
@@ -57,31 +58,30 @@
     this.retrier = retrier;
   }
 
-  private CapabilitiesBlockingStub capabilitiesBlockingStub() {
+  private CapabilitiesBlockingStub capabilitiesBlockingStub(RemoteActionExecutionContext context) {
     return CapabilitiesGrpc.newBlockingStub(channel)
-        .withInterceptors(TracingMetadataUtils.attachMetadataFromContextInterceptor())
+        .withInterceptors(
+            TracingMetadataUtils.attachMetadataInterceptor(context.getRequestMetadata()))
         .withCallCredentials(callCredentials)
         .withDeadlineAfter(callTimeoutSecs, TimeUnit.SECONDS);
   }
 
   public ServerCapabilities get(String buildRequestId, String commandId)
       throws IOException, InterruptedException {
-    Context withMetadata =
-        TracingMetadataUtils.contextWithMetadata(buildRequestId, commandId, "capabilities");
-    Context previous = withMetadata.attach();
+    RequestMetadata metadata =
+        TracingMetadataUtils.buildMetadata(buildRequestId, commandId, "capabilities");
+    RemoteActionExecutionContext context = RemoteActionExecutionContext.create(metadata);
     try {
       GetCapabilitiesRequest request =
           instanceName == null
               ? GetCapabilitiesRequest.getDefaultInstance()
               : GetCapabilitiesRequest.newBuilder().setInstanceName(instanceName).build();
-      return retrier.execute(() -> capabilitiesBlockingStub().getCapabilities(request));
+      return retrier.execute(() -> capabilitiesBlockingStub(context).getCapabilities(request));
     } catch (StatusRuntimeException e) {
       if (e.getCause() instanceof IOException) {
         throw (IOException) e.getCause();
       }
       throw new IOException(e);
-    } finally {
-      withMetadata.detach(previous);
     }
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/remote/RemoteSpawnCache.java b/src/main/java/com/google/devtools/build/lib/remote/RemoteSpawnCache.java
index d213bee..ba70436 100644
--- a/src/main/java/com/google/devtools/build/lib/remote/RemoteSpawnCache.java
+++ b/src/main/java/com/google/devtools/build/lib/remote/RemoteSpawnCache.java
@@ -24,6 +24,7 @@
 import build.bazel.remote.execution.v2.Command;
 import build.bazel.remote.execution.v2.Digest;
 import build.bazel.remote.execution.v2.Platform;
+import build.bazel.remote.execution.v2.RequestMetadata;
 import com.google.common.base.Preconditions;
 import com.google.common.base.Stopwatch;
 import com.google.common.base.Throwables;
@@ -48,9 +49,7 @@
 import com.google.devtools.build.lib.profiler.ProfilerTask;
 import com.google.devtools.build.lib.profiler.SilentCloseable;
 import com.google.devtools.build.lib.remote.common.CacheNotFoundException;
-import com.google.devtools.build.lib.remote.common.NetworkTime;
 import com.google.devtools.build.lib.remote.common.RemoteActionExecutionContext;
-import com.google.devtools.build.lib.remote.common.RemoteActionExecutionContextImpl;
 import com.google.devtools.build.lib.remote.common.RemoteCacheClient.ActionKey;
 import com.google.devtools.build.lib.remote.merkletree.MerkleTree;
 import com.google.devtools.build.lib.remote.options.RemoteOptions;
@@ -61,7 +60,6 @@
 import com.google.devtools.build.lib.remote.util.Utils.InMemoryOutput;
 import com.google.devtools.build.lib.vfs.Path;
 import com.google.devtools.build.lib.vfs.PathFragment;
-import io.grpc.Context;
 import java.io.IOException;
 import java.util.Collection;
 import java.util.HashSet;
@@ -125,7 +123,6 @@
       return SpawnCache.NO_RESULT_NO_STORE;
     }
 
-    NetworkTime networkTime = new NetworkTime();
     Stopwatch totalTime = Stopwatch.createStarted();
 
     SortedMap<PathFragment, ActionInput> inputMap = context.getInputMapping();
@@ -154,14 +151,11 @@
     // Look up action cache, and reuse the action output if it is found.
     ActionKey actionKey = digestUtil.computeActionKey(action);
 
+    RequestMetadata metadata =
+        TracingMetadataUtils.buildMetadata(
+            buildRequestId, commandId, actionKey.getDigest().getHash());
     RemoteActionExecutionContext remoteActionExecutionContext =
-        new RemoteActionExecutionContextImpl(
-            TracingMetadataUtils.buildMetadata(
-                buildRequestId, commandId, actionKey.getDigest().getHash()),
-            networkTime);
-    Context withMetadata =
-        TracingMetadataUtils.contextWithMetadata(buildRequestId, commandId, actionKey)
-            .withValue(NetworkTimeInterceptor.CONTEXT_KEY, networkTime);
+        RemoteActionExecutionContext.create(metadata);
 
     Profiler prof = Profiler.instance();
     if (options.remoteAcceptCached
@@ -169,7 +163,6 @@
       context.report(ProgressStatus.CHECKING_CACHE, "remote-cache");
       // Metadata will be available in context.current() until we detach.
       // This is done via a thread-local variable.
-      Context previous = withMetadata.attach();
       try {
         ActionResult result;
         try (SilentCloseable c = prof.profile(ProfilerTask.REMOTE_CACHE_CHECK, "check cache hit")) {
@@ -220,7 +213,7 @@
           spawnMetrics
               .setFetchTime(fetchTime.elapsed())
               .setTotalTime(totalTime.elapsed())
-              .setNetworkTime(networkTime.getDuration());
+              .setNetworkTime(remoteActionExecutionContext.getNetworkTime().getDuration());
           SpawnResult spawnResult =
               createSpawnResult(
                   result.getExitCode(),
@@ -250,8 +243,6 @@
           errorMessage = "Reading from Remote Cache:\n" + errorMessage;
           report(Event.warn(errorMessage));
         }
-      } finally {
-        withMetadata.detach(previous);
       }
     }
 
@@ -291,7 +282,6 @@
             }
           }
 
-          Context previous = withMetadata.attach();
           Collection<Path> files =
               RemoteSpawnRunner.resolveActionInputs(execRoot, spawn.getOutputFiles());
           try (SilentCloseable c = prof.profile(ProfilerTask.UPLOAD_TIME, "upload outputs")) {
@@ -316,8 +306,6 @@
             }
             errorMessage = "Writing to Remote Cache:\n" + errorMessage;
             report(Event.warn(errorMessage));
-          } finally {
-            withMetadata.detach(previous);
           }
         }
 
diff --git a/src/main/java/com/google/devtools/build/lib/remote/RemoteSpawnRunner.java b/src/main/java/com/google/devtools/build/lib/remote/RemoteSpawnRunner.java
index 3e9486c..4977703 100644
--- a/src/main/java/com/google/devtools/build/lib/remote/RemoteSpawnRunner.java
+++ b/src/main/java/com/google/devtools/build/lib/remote/RemoteSpawnRunner.java
@@ -35,6 +35,7 @@
 import build.bazel.remote.execution.v2.ExecutionStage.Value;
 import build.bazel.remote.execution.v2.LogFile;
 import build.bazel.remote.execution.v2.Platform;
+import build.bazel.remote.execution.v2.RequestMetadata;
 import com.google.common.annotations.VisibleForTesting;
 import com.google.common.base.Preconditions;
 import com.google.common.base.Stopwatch;
@@ -66,10 +67,8 @@
 import com.google.devtools.build.lib.profiler.Profiler;
 import com.google.devtools.build.lib.profiler.ProfilerTask;
 import com.google.devtools.build.lib.profiler.SilentCloseable;
-import com.google.devtools.build.lib.remote.common.NetworkTime;
 import com.google.devtools.build.lib.remote.common.OperationObserver;
 import com.google.devtools.build.lib.remote.common.RemoteActionExecutionContext;
-import com.google.devtools.build.lib.remote.common.RemoteActionExecutionContextImpl;
 import com.google.devtools.build.lib.remote.common.RemoteCacheClient.ActionKey;
 import com.google.devtools.build.lib.remote.common.RemoteExecutionClient;
 import com.google.devtools.build.lib.remote.merkletree.MerkleTree;
@@ -91,7 +90,6 @@
 import com.google.protobuf.Timestamp;
 import com.google.protobuf.util.Durations;
 import com.google.protobuf.util.Timestamps;
-import io.grpc.Context;
 import io.grpc.Status.Code;
 import java.io.IOException;
 import java.time.Duration;
@@ -243,169 +241,165 @@
 
     Preconditions.checkArgument(
         Spawns.mayBeExecutedRemotely(spawn), "Spawn can't be executed remotely. This is a bug.");
-    NetworkTime networkTime = new NetworkTime();
     // Look up action cache, and reuse the action output if it is found.
     ActionKey actionKey = digestUtil.computeActionKey(action);
 
+    RequestMetadata metadata =
+        TracingMetadataUtils.buildMetadata(
+            buildRequestId, commandId, actionKey.getDigest().getHash());
     RemoteActionExecutionContext remoteActionExecutionContext =
-        new RemoteActionExecutionContextImpl(
-            TracingMetadataUtils.buildMetadata(
-                buildRequestId, commandId, actionKey.getDigest().getHash()),
-            networkTime);
-    Context withMetadata =
-        TracingMetadataUtils.contextWithMetadata(buildRequestId, commandId, actionKey)
-            .withValue(NetworkTimeInterceptor.CONTEXT_KEY, networkTime);
-    Context previous = withMetadata.attach();
+        RemoteActionExecutionContext.create(metadata);
     Profiler prof = Profiler.instance();
     try {
-      try {
-        // Try to lookup the action in the action cache.
-        ActionResult cachedResult;
-        try (SilentCloseable c = prof.profile(ProfilerTask.REMOTE_CACHE_CHECK, "check cache hit")) {
-          cachedResult =
-              acceptCachedResult
-                  ? remoteCache.downloadActionResult(
-                      remoteActionExecutionContext, actionKey, /* inlineOutErr= */ false)
-                  : null;
-        }
-        if (cachedResult != null) {
-          if (cachedResult.getExitCode() != 0) {
-            // Failed actions are treated as a cache miss mostly in order to avoid caching flaky
-            // actions (tests).
-            // Set acceptCachedResult to false in order to force the action re-execution
+      // Try to lookup the action in the action cache.
+      ActionResult cachedResult;
+      try (SilentCloseable c = prof.profile(ProfilerTask.REMOTE_CACHE_CHECK, "check cache hit")) {
+        cachedResult =
+            acceptCachedResult
+                ? remoteCache.downloadActionResult(
+                    remoteActionExecutionContext, actionKey, /* inlineOutErr= */ false)
+                : null;
+      }
+      if (cachedResult != null) {
+        if (cachedResult.getExitCode() != 0) {
+          // Failed actions are treated as a cache miss mostly in order to avoid caching flaky
+          // actions (tests).
+          // Set acceptCachedResult to false in order to force the action re-execution
+          acceptCachedResult = false;
+        } else {
+          try {
+            return downloadAndFinalizeSpawnResult(
+                remoteActionExecutionContext,
+                actionKey.getDigest().getHash(),
+                cachedResult,
+                /* cacheHit= */ true,
+                spawn,
+                context,
+                remoteOutputsMode,
+                totalTime,
+                () -> remoteActionExecutionContext.getNetworkTime().getDuration(),
+                spawnMetrics);
+          } catch (BulkTransferException e) {
+            if (!e.onlyCausedByCacheNotFoundException()) {
+              throw e;
+            }
+            // No cache hit, so we fall through to local or remote execution.
+            // We set acceptCachedResult to false in order to force the action re-execution.
             acceptCachedResult = false;
-          } else {
+          }
+        }
+      }
+    } catch (IOException e) {
+      return execLocallyAndUploadOrFail(
+          remoteActionExecutionContext,
+          spawn,
+          context,
+          inputMap,
+          actionKey,
+          action,
+          command,
+          uploadLocalResults,
+          e);
+    }
+
+    ExecuteRequest.Builder requestBuilder =
+        ExecuteRequest.newBuilder()
+            .setInstanceName(remoteOptions.remoteInstanceName)
+            .setActionDigest(actionKey.getDigest())
+            .setSkipCacheLookup(!acceptCachedResult);
+    if (remoteOptions.remoteResultCachePriority != 0) {
+      requestBuilder
+          .getResultsCachePolicyBuilder()
+          .setPriority(remoteOptions.remoteResultCachePriority);
+    }
+    if (remoteOptions.remoteExecutionPriority != 0) {
+      requestBuilder.getExecutionPolicyBuilder().setPriority(remoteOptions.remoteExecutionPriority);
+    }
+    try {
+      return retrier.execute(
+          () -> {
+            ExecuteRequest request = requestBuilder.build();
+
+            // Upload the command and all the inputs into the remote cache.
+            try (SilentCloseable c = prof.profile(UPLOAD_TIME, "upload missing inputs")) {
+              Map<Digest, Message> additionalInputs = Maps.newHashMapWithExpectedSize(2);
+              additionalInputs.put(actionKey.getDigest(), action);
+              additionalInputs.put(commandHash, command);
+              Duration networkTimeStart =
+                  remoteActionExecutionContext.getNetworkTime().getDuration();
+              Stopwatch uploadTime = Stopwatch.createStarted();
+              remoteCache.ensureInputsPresent(
+                  remoteActionExecutionContext, merkleTree, additionalInputs);
+              // subtract network time consumed here to ensure wall clock during upload is not
+              // double
+              // counted, and metrics time computation does not exceed total time
+              spawnMetrics.setUploadTime(
+                  uploadTime
+                      .elapsed()
+                      .minus(
+                          remoteActionExecutionContext
+                              .getNetworkTime()
+                              .getDuration()
+                              .minus(networkTimeStart)));
+            }
+
+            ExecutingStatusReporter reporter = new ExecutingStatusReporter(context);
+            ExecuteResponse reply;
+            try (SilentCloseable c = prof.profile(REMOTE_EXECUTION, "execute remotely")) {
+              reply =
+                  remoteExecutor.executeRemotely(remoteActionExecutionContext, request, reporter);
+            }
+            // In case of replies from server contains metadata, but none of them has EXECUTING
+            // status.
+            // It's already late at this stage, but we should at least report once.
+            reporter.reportExecutingIfNot();
+
+            FileOutErr outErr = context.getFileOutErr();
+            String message = reply.getMessage();
+            ActionResult actionResult = reply.getResult();
+            if ((actionResult.getExitCode() != 0 || reply.getStatus().getCode() != Code.OK.value())
+                && !message.isEmpty()) {
+              outErr.printErr(message + "\n");
+            }
+
+            spawnMetricsAccounting(spawnMetrics, actionResult.getExecutionMetadata());
+
+            try (SilentCloseable c = prof.profile(REMOTE_DOWNLOAD, "download server logs")) {
+              maybeDownloadServerLogs(remoteActionExecutionContext, reply, actionKey);
+            }
+
             try {
               return downloadAndFinalizeSpawnResult(
                   remoteActionExecutionContext,
                   actionKey.getDigest().getHash(),
-                  cachedResult,
-                  /* cacheHit= */ true,
+                  actionResult,
+                  reply.getCachedResult(),
                   spawn,
                   context,
                   remoteOutputsMode,
                   totalTime,
-                  networkTime::getDuration,
+                  () -> remoteActionExecutionContext.getNetworkTime().getDuration(),
                   spawnMetrics);
             } catch (BulkTransferException e) {
-              if (!e.onlyCausedByCacheNotFoundException()) {
-                throw e;
+              if (e.onlyCausedByCacheNotFoundException()) {
+                // No cache hit, so if we retry this execution, we must no longer accept
+                // cached results, it must be reexecuted
+                requestBuilder.setSkipCacheLookup(true);
               }
-              // No cache hit, so we fall through to local or remote execution.
-              // We set acceptCachedResult to false in order to force the action re-execution.
-              acceptCachedResult = false;
+              throw e;
             }
-          }
-        }
-      } catch (IOException e) {
-        return execLocallyAndUploadOrFail(
-            remoteActionExecutionContext,
-            spawn,
-            context,
-            inputMap,
-            actionKey,
-            action,
-            command,
-            uploadLocalResults,
-            e);
-      }
-
-      ExecuteRequest.Builder requestBuilder =
-          ExecuteRequest.newBuilder()
-              .setInstanceName(remoteOptions.remoteInstanceName)
-              .setActionDigest(actionKey.getDigest())
-              .setSkipCacheLookup(!acceptCachedResult);
-      if (remoteOptions.remoteResultCachePriority != 0) {
-        requestBuilder
-            .getResultsCachePolicyBuilder()
-            .setPriority(remoteOptions.remoteResultCachePriority);
-      }
-      if (remoteOptions.remoteExecutionPriority != 0) {
-        requestBuilder
-            .getExecutionPolicyBuilder()
-            .setPriority(remoteOptions.remoteExecutionPriority);
-      }
-      try {
-        return retrier.execute(
-            () -> {
-              ExecuteRequest request = requestBuilder.build();
-
-              // Upload the command and all the inputs into the remote cache.
-              try (SilentCloseable c = prof.profile(UPLOAD_TIME, "upload missing inputs")) {
-                Map<Digest, Message> additionalInputs = Maps.newHashMapWithExpectedSize(2);
-                additionalInputs.put(actionKey.getDigest(), action);
-                additionalInputs.put(commandHash, command);
-                Duration networkTimeStart = networkTime.getDuration();
-                Stopwatch uploadTime = Stopwatch.createStarted();
-                remoteCache.ensureInputsPresent(
-                    remoteActionExecutionContext, merkleTree, additionalInputs);
-                // subtract network time consumed here to ensure wall clock during upload is not
-                // double
-                // counted, and metrics time computation does not exceed total time
-                spawnMetrics.setUploadTime(
-                    uploadTime.elapsed().minus(networkTime.getDuration().minus(networkTimeStart)));
-              }
-
-              ExecutingStatusReporter reporter = new ExecutingStatusReporter(context);
-              ExecuteResponse reply;
-              try (SilentCloseable c = prof.profile(REMOTE_EXECUTION, "execute remotely")) {
-                reply = remoteExecutor.executeRemotely(request, reporter);
-              }
-              // In case of replies from server contains metadata, but none of them has EXECUTING
-              // status.
-              // It's already late at this stage, but we should at least report once.
-              reporter.reportExecutingIfNot();
-
-              FileOutErr outErr = context.getFileOutErr();
-              String message = reply.getMessage();
-              ActionResult actionResult = reply.getResult();
-              if ((actionResult.getExitCode() != 0
-                      || reply.getStatus().getCode() != Code.OK.value())
-                  && !message.isEmpty()) {
-                outErr.printErr(message + "\n");
-              }
-
-              spawnMetricsAccounting(spawnMetrics, actionResult.getExecutionMetadata());
-
-              try (SilentCloseable c = prof.profile(REMOTE_DOWNLOAD, "download server logs")) {
-                maybeDownloadServerLogs(remoteActionExecutionContext, reply, actionKey);
-              }
-
-              try {
-                return downloadAndFinalizeSpawnResult(
-                    remoteActionExecutionContext,
-                    actionKey.getDigest().getHash(),
-                    actionResult,
-                    reply.getCachedResult(),
-                    spawn,
-                    context,
-                    remoteOutputsMode,
-                    totalTime,
-                    networkTime::getDuration,
-                    spawnMetrics);
-              } catch (BulkTransferException e) {
-                if (e.onlyCausedByCacheNotFoundException()) {
-                  // No cache hit, so if we retry this execution, we must no longer accept
-                  // cached results, it must be reexecuted
-                  requestBuilder.setSkipCacheLookup(true);
-                }
-                throw e;
-              }
-            });
-      } catch (IOException e) {
-        return execLocallyAndUploadOrFail(
-            remoteActionExecutionContext,
-            spawn,
-            context,
-            inputMap,
-            actionKey,
-            action,
-            command,
-            uploadLocalResults,
-            e);
-      }
-    } finally {
-      withMetadata.detach(previous);
+          });
+    } catch (IOException e) {
+      return execLocallyAndUploadOrFail(
+          remoteActionExecutionContext,
+          spawn,
+          context,
+          inputMap,
+          actionKey,
+          action,
+          command,
+          uploadLocalResults,
+          e);
     }
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/remote/common/MissingDigestsFinder.java b/src/main/java/com/google/devtools/build/lib/remote/common/MissingDigestsFinder.java
index c9c1d40..f682e93 100644
--- a/src/main/java/com/google/devtools/build/lib/remote/common/MissingDigestsFinder.java
+++ b/src/main/java/com/google/devtools/build/lib/remote/common/MissingDigestsFinder.java
@@ -26,5 +26,6 @@
    *
    * @param digests The list of digests to look for.
    */
-  ListenableFuture<ImmutableSet<Digest>> findMissingDigests(Iterable<Digest> digests);
+  ListenableFuture<ImmutableSet<Digest>> findMissingDigests(
+      RemoteActionExecutionContext context, Iterable<Digest> digests);
 }
diff --git a/src/main/java/com/google/devtools/build/lib/remote/common/RemoteActionExecutionContext.java b/src/main/java/com/google/devtools/build/lib/remote/common/RemoteActionExecutionContext.java
index 6d61cd0..bc3d766 100644
--- a/src/main/java/com/google/devtools/build/lib/remote/common/RemoteActionExecutionContext.java
+++ b/src/main/java/com/google/devtools/build/lib/remote/common/RemoteActionExecutionContext.java
@@ -26,4 +26,9 @@
    * execution.
    */
   NetworkTime getNetworkTime();
+
+  /** Creates a {@link SimpleRemoteActionExecutionContext} with given {@link RequestMetadata}. */
+  static RemoteActionExecutionContext create(RequestMetadata metadata) {
+    return new SimpleRemoteActionExecutionContext(metadata, new NetworkTime());
+  }
 }
diff --git a/src/main/java/com/google/devtools/build/lib/remote/common/RemoteExecutionClient.java b/src/main/java/com/google/devtools/build/lib/remote/common/RemoteExecutionClient.java
index 1db02ea..ac2c283 100644
--- a/src/main/java/com/google/devtools/build/lib/remote/common/RemoteExecutionClient.java
+++ b/src/main/java/com/google/devtools/build/lib/remote/common/RemoteExecutionClient.java
@@ -25,7 +25,8 @@
 public interface RemoteExecutionClient {
 
   /** Execute an action remotely using Remote Execution API. */
-  ExecuteResponse executeRemotely(ExecuteRequest request, OperationObserver observer)
+  ExecuteResponse executeRemotely(
+      RemoteActionExecutionContext context, ExecuteRequest request, OperationObserver observer)
       throws IOException, InterruptedException;
 
   /** Close resources associated with the remote execution client. */
diff --git a/src/main/java/com/google/devtools/build/lib/remote/common/RemoteActionExecutionContextImpl.java b/src/main/java/com/google/devtools/build/lib/remote/common/SimpleRemoteActionExecutionContext.java
similarity index 89%
rename from src/main/java/com/google/devtools/build/lib/remote/common/RemoteActionExecutionContextImpl.java
rename to src/main/java/com/google/devtools/build/lib/remote/common/SimpleRemoteActionExecutionContext.java
index f4894e3..a0d82c7 100644
--- a/src/main/java/com/google/devtools/build/lib/remote/common/RemoteActionExecutionContextImpl.java
+++ b/src/main/java/com/google/devtools/build/lib/remote/common/SimpleRemoteActionExecutionContext.java
@@ -16,12 +16,12 @@
 import build.bazel.remote.execution.v2.RequestMetadata;
 
 /** A {@link RemoteActionExecutionContext} implementation */
-public class RemoteActionExecutionContextImpl implements RemoteActionExecutionContext {
+public class SimpleRemoteActionExecutionContext implements RemoteActionExecutionContext {
 
   private final RequestMetadata requestMetadata;
   private final NetworkTime networkTime;
 
-  public RemoteActionExecutionContextImpl(
+  public SimpleRemoteActionExecutionContext(
       RequestMetadata requestMetadata, NetworkTime networkTime) {
     this.requestMetadata = requestMetadata;
     this.networkTime = networkTime;
diff --git a/src/main/java/com/google/devtools/build/lib/remote/disk/DiskAndRemoteCacheClient.java b/src/main/java/com/google/devtools/build/lib/remote/disk/DiskAndRemoteCacheClient.java
index 60c5016..b340985 100644
--- a/src/main/java/com/google/devtools/build/lib/remote/disk/DiskAndRemoteCacheClient.java
+++ b/src/main/java/com/google/devtools/build/lib/remote/disk/DiskAndRemoteCacheClient.java
@@ -97,9 +97,12 @@
   }
 
   @Override
-  public ListenableFuture<ImmutableSet<Digest>> findMissingDigests(Iterable<Digest> digests) {
-    ListenableFuture<ImmutableSet<Digest>> remoteQuery = remoteCache.findMissingDigests(digests);
-    ListenableFuture<ImmutableSet<Digest>> diskQuery = diskCache.findMissingDigests(digests);
+  public ListenableFuture<ImmutableSet<Digest>> findMissingDigests(
+      RemoteActionExecutionContext context, Iterable<Digest> digests) {
+    ListenableFuture<ImmutableSet<Digest>> remoteQuery =
+        remoteCache.findMissingDigests(context, digests);
+    ListenableFuture<ImmutableSet<Digest>> diskQuery =
+        diskCache.findMissingDigests(context, digests);
     return Futures.whenAllSucceed(remoteQuery, diskQuery)
         .call(
             () ->
diff --git a/src/main/java/com/google/devtools/build/lib/remote/disk/DiskCacheClient.java b/src/main/java/com/google/devtools/build/lib/remote/disk/DiskCacheClient.java
index 6778525..26ce20a 100644
--- a/src/main/java/com/google/devtools/build/lib/remote/disk/DiskCacheClient.java
+++ b/src/main/java/com/google/devtools/build/lib/remote/disk/DiskCacheClient.java
@@ -143,7 +143,8 @@
   }
 
   @Override
-  public ListenableFuture<ImmutableSet<Digest>> findMissingDigests(Iterable<Digest> digests) {
+  public ListenableFuture<ImmutableSet<Digest>> findMissingDigests(
+      RemoteActionExecutionContext context, Iterable<Digest> digests) {
     // Both upload and download check if the file exists before doing I/O. So we don't
     // have to do it here.
     return Futures.immediateFuture(ImmutableSet.copyOf(digests));
diff --git a/src/main/java/com/google/devtools/build/lib/remote/downloader/GrpcRemoteDownloader.java b/src/main/java/com/google/devtools/build/lib/remote/downloader/GrpcRemoteDownloader.java
index 672207b..71b22c7 100644
--- a/src/main/java/com/google/devtools/build/lib/remote/downloader/GrpcRemoteDownloader.java
+++ b/src/main/java/com/google/devtools/build/lib/remote/downloader/GrpcRemoteDownloader.java
@@ -29,9 +29,7 @@
 import com.google.devtools.build.lib.events.ExtendedEventHandler;
 import com.google.devtools.build.lib.remote.ReferenceCountedChannel;
 import com.google.devtools.build.lib.remote.RemoteRetrier;
-import com.google.devtools.build.lib.remote.common.NetworkTime;
 import com.google.devtools.build.lib.remote.common.RemoteActionExecutionContext;
-import com.google.devtools.build.lib.remote.common.RemoteActionExecutionContextImpl;
 import com.google.devtools.build.lib.remote.common.RemoteCacheClient;
 import com.google.devtools.build.lib.remote.options.RemoteOptions;
 import com.google.devtools.build.lib.remote.util.TracingMetadataUtils;
@@ -118,7 +116,7 @@
     RequestMetadata metadata =
         TracingMetadataUtils.buildMetadata(buildRequestId, commandId, "remote_downloader");
     RemoteActionExecutionContext remoteActionExecutionContext =
-        new RemoteActionExecutionContextImpl(metadata, new NetworkTime());
+        RemoteActionExecutionContext.create(metadata);
 
     final FetchBlobRequest request =
         newFetchBlobRequest(options.remoteInstanceName, urls, authHeaders, checksum, canonicalId);
diff --git a/src/main/java/com/google/devtools/build/lib/remote/http/HttpCacheClient.java b/src/main/java/com/google/devtools/build/lib/remote/http/HttpCacheClient.java
index 1d8a922..1efecd3 100644
--- a/src/main/java/com/google/devtools/build/lib/remote/http/HttpCacheClient.java
+++ b/src/main/java/com/google/devtools/build/lib/remote/http/HttpCacheClient.java
@@ -690,7 +690,8 @@
   }
 
   @Override
-  public ListenableFuture<ImmutableSet<Digest>> findMissingDigests(Iterable<Digest> digests) {
+  public ListenableFuture<ImmutableSet<Digest>> findMissingDigests(
+      RemoteActionExecutionContext context, Iterable<Digest> digests) {
     return Futures.immediateFuture(ImmutableSet.copyOf(digests));
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/remote/util/TracingMetadataUtils.java b/src/main/java/com/google/devtools/build/lib/remote/util/TracingMetadataUtils.java
index cb880ce..93cf8a3 100644
--- a/src/main/java/com/google/devtools/build/lib/remote/util/TracingMetadataUtils.java
+++ b/src/main/java/com/google/devtools/build/lib/remote/util/TracingMetadataUtils.java
@@ -18,7 +18,6 @@
 import com.google.common.annotations.VisibleForTesting;
 import com.google.common.base.Preconditions;
 import com.google.devtools.build.lib.analysis.BlazeVersionInfo;
-import com.google.devtools.build.lib.remote.common.RemoteCacheClient.ActionKey;
 import com.google.devtools.build.lib.remote.options.RemoteOptions;
 import io.grpc.ClientInterceptor;
 import io.grpc.Context;
@@ -46,18 +45,6 @@
   public static final Metadata.Key<RequestMetadata> METADATA_KEY =
       ProtoUtils.keyForProto(RequestMetadata.getDefaultInstance());
 
-  /**
-   * Returns a new gRPC context derived from the current context, with {@link RequestMetadata}
-   * accessible by the {@link fromCurrentContext()} method.
-   *
-   * <p>The {@link RequestMetadata} is constructed using the provided arguments and the current tool
-   * version.
-   */
-  public static Context contextWithMetadata(
-      String buildRequestId, String commandId, ActionKey actionKey) {
-    return contextWithMetadata(buildRequestId, commandId, actionKey.getDigest().getHash());
-  }
-
   public static RequestMetadata buildMetadata(
       String buildRequestId, String commandId, String actionId) {
     Preconditions.checkNotNull(buildRequestId);
@@ -75,26 +62,9 @@
   }
 
   /**
-   * Returns a new gRPC context derived from the current context, with {@link RequestMetadata}
-   * accessible by the {@link fromCurrentContext()} method.
-   *
-   * <p>The {@link RequestMetadata} is constructed using the provided arguments and the current tool
-   * version.
-   */
-  public static Context contextWithMetadata(
-      String buildRequestId, String commandId, String actionId) {
-    RequestMetadata metadata = buildMetadata(buildRequestId, commandId, actionId);
-    return contextWithMetadata(metadata);
-  }
-
-  public static Context contextWithMetadata(RequestMetadata metadata) {
-    return Context.current().withValue(CONTEXT_KEY, metadata);
-  }
-
-  /**
    * Fetches a {@link RequestMetadata} defined on the current context.
    *
-   * @throws {@link IllegalStateException} when the metadata is not defined in the current context.
+   * @throws IllegalStateException when the metadata is not defined in the current context.
    */
   public static RequestMetadata fromCurrentContext() {
     RequestMetadata metadata = CONTEXT_KEY.get();
@@ -104,16 +74,6 @@
     return metadata;
   }
 
-  /**
-   * Creates a {@link Metadata} containing the {@link RequestMetadata} defined on the current
-   * context.
-   *
-   * @throws {@link IllegalStateException} when the metadata is not defined in the current context.
-   */
-  public static Metadata headersFromCurrentContext() {
-    return headersFromRequestMetadata(fromCurrentContext());
-  }
-
   /** Creates a {@link Metadata} containing the {@link RequestMetadata}. */
   public static Metadata headersFromRequestMetadata(RequestMetadata requestMetadata) {
     Metadata headers = new Metadata();
@@ -129,10 +89,6 @@
     return headers.get(METADATA_KEY);
   }
 
-  public static ClientInterceptor attachMetadataFromContextInterceptor() {
-    return MetadataUtils.newAttachHeadersInterceptor(headersFromCurrentContext());
-  }
-
   public static ClientInterceptor attachMetadataInterceptor(RequestMetadata requestMetadata) {
     return MetadataUtils.newAttachHeadersInterceptor(headersFromRequestMetadata(requestMetadata));
   }