diff --git a/go/test_platform/steps/execution.pb.go b/go/test_platform/steps/execution.pb.go
index e3027a3..b6bb39f 100644
--- a/go/test_platform/steps/execution.pb.go
+++ b/go/test_platform/steps/execution.pb.go
@@ -318,7 +318,16 @@
 	// Any rejected task dimensions from the task execution request,
 	// stored as key-value pairs. This field is only populated if the
 	// task was rejected by Swarming due to a lack of matching bot.
+	// DEPRECATED: use rejected_dimensions instead, as it allows multiple
+	// values for the same key. This will be deleted soon.
+	// TODO(https://crbug.com/11798680)
+	//
+	// Deprecated: Do not use.
 	RejectedTaskDimensions map[string]string `protobuf:"bytes,11,rep,name=rejected_task_dimensions,json=rejectedTaskDimensions,proto3" json:"rejected_task_dimensions,omitempty" protobuf_key:"bytes,1,opt,name=key,proto3" protobuf_val:"bytes,2,opt,name=value,proto3"`
+	// Any rejected task dimensions from the task execution request,
+	// stored as key-value pairs. This field is only populated if the
+	// task was rejected by Swarming due to a lack of matching bot.
+	RejectedDimensions []*ExecuteResponse_TaskResult_RejectedTaskDimension `protobuf:"bytes,12,rep,name=rejected_dimensions,json=rejectedDimensions,proto3" json:"rejected_dimensions,omitempty"`
 }
 
 func (x *ExecuteResponse_TaskResult) Reset() {
@@ -409,6 +418,7 @@
 	return nil
 }
 
+// Deprecated: Do not use.
 func (x *ExecuteResponse_TaskResult) GetRejectedTaskDimensions() map[string]string {
 	if x != nil {
 		return x.RejectedTaskDimensions
@@ -416,6 +426,13 @@
 	return nil
 }
 
+func (x *ExecuteResponse_TaskResult) GetRejectedDimensions() []*ExecuteResponse_TaskResult_RejectedTaskDimension {
+	if x != nil {
+		return x.RejectedDimensions
+	}
+	return nil
+}
+
 type ExecuteResponse_ConsolidatedResult struct {
 	state         protoimpl.MessageState
 	sizeCache     protoimpl.SizeCache
@@ -538,6 +555,61 @@
 	return ""
 }
 
+type ExecuteResponse_TaskResult_RejectedTaskDimension struct {
+	state         protoimpl.MessageState
+	sizeCache     protoimpl.SizeCache
+	unknownFields protoimpl.UnknownFields
+
+	Key   string `protobuf:"bytes,1,opt,name=key,proto3" json:"key,omitempty"`
+	Value string `protobuf:"bytes,2,opt,name=value,proto3" json:"value,omitempty"`
+}
+
+func (x *ExecuteResponse_TaskResult_RejectedTaskDimension) Reset() {
+	*x = ExecuteResponse_TaskResult_RejectedTaskDimension{}
+	if protoimpl.UnsafeEnabled {
+		mi := &file_test_platform_steps_execution_proto_msgTypes[10]
+		ms := protoimpl.X.MessageStateOf(protoimpl.Pointer(x))
+		ms.StoreMessageInfo(mi)
+	}
+}
+
+func (x *ExecuteResponse_TaskResult_RejectedTaskDimension) String() string {
+	return protoimpl.X.MessageStringOf(x)
+}
+
+func (*ExecuteResponse_TaskResult_RejectedTaskDimension) ProtoMessage() {}
+
+func (x *ExecuteResponse_TaskResult_RejectedTaskDimension) ProtoReflect() protoreflect.Message {
+	mi := &file_test_platform_steps_execution_proto_msgTypes[10]
+	if protoimpl.UnsafeEnabled && x != nil {
+		ms := protoimpl.X.MessageStateOf(protoimpl.Pointer(x))
+		if ms.LoadMessageInfo() == nil {
+			ms.StoreMessageInfo(mi)
+		}
+		return ms
+	}
+	return mi.MessageOf(x)
+}
+
+// Deprecated: Use ExecuteResponse_TaskResult_RejectedTaskDimension.ProtoReflect.Descriptor instead.
+func (*ExecuteResponse_TaskResult_RejectedTaskDimension) Descriptor() ([]byte, []int) {
+	return file_test_platform_steps_execution_proto_rawDescGZIP(), []int{3, 0, 2}
+}
+
+func (x *ExecuteResponse_TaskResult_RejectedTaskDimension) GetKey() string {
+	if x != nil {
+		return x.Key
+	}
+	return ""
+}
+
+func (x *ExecuteResponse_TaskResult_RejectedTaskDimension) GetValue() string {
+	if x != nil {
+		return x.Value
+	}
+	return ""
+}
+
 var File_test_platform_steps_execution_proto protoreflect.FileDescriptor
 
 var file_test_platform_steps_execution_proto_rawDesc = []byte{
@@ -611,7 +683,7 @@
 	0x69, 0x6f, 0x6e, 0x12, 0x34, 0x0a, 0x06, 0x63, 0x6f, 0x6e, 0x66, 0x69, 0x67, 0x18, 0x03, 0x20,
 	0x01, 0x28, 0x0b, 0x32, 0x1c, 0x2e, 0x74, 0x65, 0x73, 0x74, 0x5f, 0x70, 0x6c, 0x61, 0x74, 0x66,
 	0x6f, 0x72, 0x6d, 0x2e, 0x63, 0x6f, 0x6e, 0x66, 0x69, 0x67, 0x2e, 0x43, 0x6f, 0x6e, 0x66, 0x69,
-	0x67, 0x52, 0x06, 0x63, 0x6f, 0x6e, 0x66, 0x69, 0x67, 0x22, 0x95, 0x09, 0x0a, 0x0f, 0x45, 0x78,
+	0x67, 0x52, 0x06, 0x63, 0x6f, 0x6e, 0x66, 0x69, 0x67, 0x22, 0xd2, 0x0a, 0x0a, 0x0f, 0x45, 0x78,
 	0x65, 0x63, 0x75, 0x74, 0x65, 0x52, 0x65, 0x73, 0x70, 0x6f, 0x6e, 0x73, 0x65, 0x12, 0x56, 0x0a,
 	0x0c, 0x74, 0x61, 0x73, 0x6b, 0x5f, 0x72, 0x65, 0x73, 0x75, 0x6c, 0x74, 0x73, 0x18, 0x01, 0x20,
 	0x03, 0x28, 0x0b, 0x32, 0x2f, 0x2e, 0x74, 0x65, 0x73, 0x74, 0x5f, 0x70, 0x6c, 0x61, 0x74, 0x66,
@@ -628,7 +700,7 @@
 	0x73, 0x12, 0x2e, 0x0a, 0x05, 0x73, 0x74, 0x61, 0x74, 0x65, 0x18, 0x02, 0x20, 0x01, 0x28, 0x0b,
 	0x32, 0x18, 0x2e, 0x74, 0x65, 0x73, 0x74, 0x5f, 0x70, 0x6c, 0x61, 0x74, 0x66, 0x6f, 0x72, 0x6d,
 	0x2e, 0x54, 0x61, 0x73, 0x6b, 0x53, 0x74, 0x61, 0x74, 0x65, 0x52, 0x05, 0x73, 0x74, 0x61, 0x74,
-	0x65, 0x1a, 0xaa, 0x06, 0x0a, 0x0a, 0x54, 0x61, 0x73, 0x6b, 0x52, 0x65, 0x73, 0x75, 0x6c, 0x74,
+	0x65, 0x1a, 0xe7, 0x07, 0x0a, 0x0a, 0x54, 0x61, 0x73, 0x6b, 0x52, 0x65, 0x73, 0x75, 0x6c, 0x74,
 	0x12, 0x19, 0x0a, 0x08, 0x74, 0x61, 0x73, 0x6b, 0x5f, 0x75, 0x72, 0x6c, 0x18, 0x02, 0x20, 0x01,
 	0x28, 0x09, 0x52, 0x07, 0x74, 0x61, 0x73, 0x6b, 0x55, 0x72, 0x6c, 0x12, 0x2e, 0x0a, 0x05, 0x73,
 	0x74, 0x61, 0x74, 0x65, 0x18, 0x03, 0x20, 0x01, 0x28, 0x0b, 0x32, 0x18, 0x2e, 0x74, 0x65, 0x73,
@@ -654,42 +726,54 @@
 	0x18, 0x09, 0x20, 0x01, 0x28, 0x0b, 0x32, 0x21, 0x2e, 0x74, 0x65, 0x73, 0x74, 0x5f, 0x70, 0x6c,
 	0x61, 0x74, 0x66, 0x6f, 0x72, 0x6d, 0x2e, 0x63, 0x6f, 0x6d, 0x6d, 0x6f, 0x6e, 0x2e, 0x54, 0x61,
 	0x73, 0x6b, 0x4c, 0x6f, 0x67, 0x44, 0x61, 0x74, 0x61, 0x52, 0x07, 0x6c, 0x6f, 0x67, 0x44, 0x61,
-	0x74, 0x61, 0x12, 0x85, 0x01, 0x0a, 0x18, 0x72, 0x65, 0x6a, 0x65, 0x63, 0x74, 0x65, 0x64, 0x5f,
+	0x74, 0x61, 0x12, 0x89, 0x01, 0x0a, 0x18, 0x72, 0x65, 0x6a, 0x65, 0x63, 0x74, 0x65, 0x64, 0x5f,
 	0x74, 0x61, 0x73, 0x6b, 0x5f, 0x64, 0x69, 0x6d, 0x65, 0x6e, 0x73, 0x69, 0x6f, 0x6e, 0x73, 0x18,
 	0x0b, 0x20, 0x03, 0x28, 0x0b, 0x32, 0x4b, 0x2e, 0x74, 0x65, 0x73, 0x74, 0x5f, 0x70, 0x6c, 0x61,
 	0x74, 0x66, 0x6f, 0x72, 0x6d, 0x2e, 0x73, 0x74, 0x65, 0x70, 0x73, 0x2e, 0x45, 0x78, 0x65, 0x63,
 	0x75, 0x74, 0x65, 0x52, 0x65, 0x73, 0x70, 0x6f, 0x6e, 0x73, 0x65, 0x2e, 0x54, 0x61, 0x73, 0x6b,
 	0x52, 0x65, 0x73, 0x75, 0x6c, 0x74, 0x2e, 0x52, 0x65, 0x6a, 0x65, 0x63, 0x74, 0x65, 0x64, 0x54,
 	0x61, 0x73, 0x6b, 0x44, 0x69, 0x6d, 0x65, 0x6e, 0x73, 0x69, 0x6f, 0x6e, 0x73, 0x45, 0x6e, 0x74,
-	0x72, 0x79, 0x52, 0x16, 0x72, 0x65, 0x6a, 0x65, 0x63, 0x74, 0x65, 0x64, 0x54, 0x61, 0x73, 0x6b,
-	0x44, 0x69, 0x6d, 0x65, 0x6e, 0x73, 0x69, 0x6f, 0x6e, 0x73, 0x1a, 0x96, 0x01, 0x0a, 0x0e, 0x54,
-	0x65, 0x73, 0x74, 0x43, 0x61, 0x73, 0x65, 0x52, 0x65, 0x73, 0x75, 0x6c, 0x74, 0x12, 0x12, 0x0a,
-	0x04, 0x6e, 0x61, 0x6d, 0x65, 0x18, 0x01, 0x20, 0x01, 0x28, 0x09, 0x52, 0x04, 0x6e, 0x61, 0x6d,
-	0x65, 0x12, 0x3a, 0x0a, 0x07, 0x76, 0x65, 0x72, 0x64, 0x69, 0x63, 0x74, 0x18, 0x02, 0x20, 0x01,
-	0x28, 0x0e, 0x32, 0x20, 0x2e, 0x74, 0x65, 0x73, 0x74, 0x5f, 0x70, 0x6c, 0x61, 0x74, 0x66, 0x6f,
-	0x72, 0x6d, 0x2e, 0x54, 0x61, 0x73, 0x6b, 0x53, 0x74, 0x61, 0x74, 0x65, 0x2e, 0x56, 0x65, 0x72,
-	0x64, 0x69, 0x63, 0x74, 0x52, 0x07, 0x76, 0x65, 0x72, 0x64, 0x69, 0x63, 0x74, 0x12, 0x34, 0x0a,
-	0x16, 0x68, 0x75, 0x6d, 0x61, 0x6e, 0x5f, 0x72, 0x65, 0x61, 0x64, 0x61, 0x62, 0x6c, 0x65, 0x5f,
-	0x73, 0x75, 0x6d, 0x6d, 0x61, 0x72, 0x79, 0x18, 0x03, 0x20, 0x01, 0x28, 0x09, 0x52, 0x14, 0x68,
-	0x75, 0x6d, 0x61, 0x6e, 0x52, 0x65, 0x61, 0x64, 0x61, 0x62, 0x6c, 0x65, 0x53, 0x75, 0x6d, 0x6d,
-	0x61, 0x72, 0x79, 0x1a, 0x49, 0x0a, 0x1b, 0x52, 0x65, 0x6a, 0x65, 0x63, 0x74, 0x65, 0x64, 0x54,
-	0x61, 0x73, 0x6b, 0x44, 0x69, 0x6d, 0x65, 0x6e, 0x73, 0x69, 0x6f, 0x6e, 0x73, 0x45, 0x6e, 0x74,
-	0x72, 0x79, 0x12, 0x10, 0x0a, 0x03, 0x6b, 0x65, 0x79, 0x18, 0x01, 0x20, 0x01, 0x28, 0x09, 0x52,
-	0x03, 0x6b, 0x65, 0x79, 0x12, 0x14, 0x0a, 0x05, 0x76, 0x61, 0x6c, 0x75, 0x65, 0x18, 0x02, 0x20,
-	0x01, 0x28, 0x09, 0x52, 0x05, 0x76, 0x61, 0x6c, 0x75, 0x65, 0x3a, 0x02, 0x38, 0x01, 0x4a, 0x04,
-	0x08, 0x0a, 0x10, 0x0b, 0x52, 0x18, 0x73, 0x79, 0x6e, 0x63, 0x68, 0x72, 0x6f, 0x6e, 0x6f, 0x75,
-	0x73, 0x5f, 0x6c, 0x6f, 0x67, 0x5f, 0x64, 0x61, 0x74, 0x61, 0x5f, 0x75, 0x72, 0x6c, 0x1a, 0x61,
-	0x0a, 0x12, 0x43, 0x6f, 0x6e, 0x73, 0x6f, 0x6c, 0x69, 0x64, 0x61, 0x74, 0x65, 0x64, 0x52, 0x65,
-	0x73, 0x75, 0x6c, 0x74, 0x12, 0x4b, 0x0a, 0x08, 0x61, 0x74, 0x74, 0x65, 0x6d, 0x70, 0x74, 0x73,
-	0x18, 0x01, 0x20, 0x03, 0x28, 0x0b, 0x32, 0x2f, 0x2e, 0x74, 0x65, 0x73, 0x74, 0x5f, 0x70, 0x6c,
-	0x61, 0x74, 0x66, 0x6f, 0x72, 0x6d, 0x2e, 0x73, 0x74, 0x65, 0x70, 0x73, 0x2e, 0x45, 0x78, 0x65,
-	0x63, 0x75, 0x74, 0x65, 0x52, 0x65, 0x73, 0x70, 0x6f, 0x6e, 0x73, 0x65, 0x2e, 0x54, 0x61, 0x73,
-	0x6b, 0x52, 0x65, 0x73, 0x75, 0x6c, 0x74, 0x52, 0x08, 0x61, 0x74, 0x74, 0x65, 0x6d, 0x70, 0x74,
-	0x73, 0x42, 0x3f, 0x5a, 0x3d, 0x67, 0x6f, 0x2e, 0x63, 0x68, 0x72, 0x6f, 0x6d, 0x69, 0x75, 0x6d,
-	0x2e, 0x6f, 0x72, 0x67, 0x2f, 0x63, 0x68, 0x72, 0x6f, 0x6d, 0x69, 0x75, 0x6d, 0x6f, 0x73, 0x2f,
-	0x69, 0x6e, 0x66, 0x72, 0x61, 0x2f, 0x70, 0x72, 0x6f, 0x74, 0x6f, 0x2f, 0x67, 0x6f, 0x2f, 0x74,
-	0x65, 0x73, 0x74, 0x5f, 0x70, 0x6c, 0x61, 0x74, 0x66, 0x6f, 0x72, 0x6d, 0x2f, 0x73, 0x74, 0x65,
-	0x70, 0x73, 0x62, 0x06, 0x70, 0x72, 0x6f, 0x74, 0x6f, 0x33,
+	0x72, 0x79, 0x42, 0x02, 0x18, 0x01, 0x52, 0x16, 0x72, 0x65, 0x6a, 0x65, 0x63, 0x74, 0x65, 0x64,
+	0x54, 0x61, 0x73, 0x6b, 0x44, 0x69, 0x6d, 0x65, 0x6e, 0x73, 0x69, 0x6f, 0x6e, 0x73, 0x12, 0x76,
+	0x0a, 0x13, 0x72, 0x65, 0x6a, 0x65, 0x63, 0x74, 0x65, 0x64, 0x5f, 0x64, 0x69, 0x6d, 0x65, 0x6e,
+	0x73, 0x69, 0x6f, 0x6e, 0x73, 0x18, 0x0c, 0x20, 0x03, 0x28, 0x0b, 0x32, 0x45, 0x2e, 0x74, 0x65,
+	0x73, 0x74, 0x5f, 0x70, 0x6c, 0x61, 0x74, 0x66, 0x6f, 0x72, 0x6d, 0x2e, 0x73, 0x74, 0x65, 0x70,
+	0x73, 0x2e, 0x45, 0x78, 0x65, 0x63, 0x75, 0x74, 0x65, 0x52, 0x65, 0x73, 0x70, 0x6f, 0x6e, 0x73,
+	0x65, 0x2e, 0x54, 0x61, 0x73, 0x6b, 0x52, 0x65, 0x73, 0x75, 0x6c, 0x74, 0x2e, 0x52, 0x65, 0x6a,
+	0x65, 0x63, 0x74, 0x65, 0x64, 0x54, 0x61, 0x73, 0x6b, 0x44, 0x69, 0x6d, 0x65, 0x6e, 0x73, 0x69,
+	0x6f, 0x6e, 0x52, 0x12, 0x72, 0x65, 0x6a, 0x65, 0x63, 0x74, 0x65, 0x64, 0x44, 0x69, 0x6d, 0x65,
+	0x6e, 0x73, 0x69, 0x6f, 0x6e, 0x73, 0x1a, 0x96, 0x01, 0x0a, 0x0e, 0x54, 0x65, 0x73, 0x74, 0x43,
+	0x61, 0x73, 0x65, 0x52, 0x65, 0x73, 0x75, 0x6c, 0x74, 0x12, 0x12, 0x0a, 0x04, 0x6e, 0x61, 0x6d,
+	0x65, 0x18, 0x01, 0x20, 0x01, 0x28, 0x09, 0x52, 0x04, 0x6e, 0x61, 0x6d, 0x65, 0x12, 0x3a, 0x0a,
+	0x07, 0x76, 0x65, 0x72, 0x64, 0x69, 0x63, 0x74, 0x18, 0x02, 0x20, 0x01, 0x28, 0x0e, 0x32, 0x20,
+	0x2e, 0x74, 0x65, 0x73, 0x74, 0x5f, 0x70, 0x6c, 0x61, 0x74, 0x66, 0x6f, 0x72, 0x6d, 0x2e, 0x54,
+	0x61, 0x73, 0x6b, 0x53, 0x74, 0x61, 0x74, 0x65, 0x2e, 0x56, 0x65, 0x72, 0x64, 0x69, 0x63, 0x74,
+	0x52, 0x07, 0x76, 0x65, 0x72, 0x64, 0x69, 0x63, 0x74, 0x12, 0x34, 0x0a, 0x16, 0x68, 0x75, 0x6d,
+	0x61, 0x6e, 0x5f, 0x72, 0x65, 0x61, 0x64, 0x61, 0x62, 0x6c, 0x65, 0x5f, 0x73, 0x75, 0x6d, 0x6d,
+	0x61, 0x72, 0x79, 0x18, 0x03, 0x20, 0x01, 0x28, 0x09, 0x52, 0x14, 0x68, 0x75, 0x6d, 0x61, 0x6e,
+	0x52, 0x65, 0x61, 0x64, 0x61, 0x62, 0x6c, 0x65, 0x53, 0x75, 0x6d, 0x6d, 0x61, 0x72, 0x79, 0x1a,
+	0x49, 0x0a, 0x1b, 0x52, 0x65, 0x6a, 0x65, 0x63, 0x74, 0x65, 0x64, 0x54, 0x61, 0x73, 0x6b, 0x44,
+	0x69, 0x6d, 0x65, 0x6e, 0x73, 0x69, 0x6f, 0x6e, 0x73, 0x45, 0x6e, 0x74, 0x72, 0x79, 0x12, 0x10,
+	0x0a, 0x03, 0x6b, 0x65, 0x79, 0x18, 0x01, 0x20, 0x01, 0x28, 0x09, 0x52, 0x03, 0x6b, 0x65, 0x79,
+	0x12, 0x14, 0x0a, 0x05, 0x76, 0x61, 0x6c, 0x75, 0x65, 0x18, 0x02, 0x20, 0x01, 0x28, 0x09, 0x52,
+	0x05, 0x76, 0x61, 0x6c, 0x75, 0x65, 0x3a, 0x02, 0x38, 0x01, 0x1a, 0x3f, 0x0a, 0x15, 0x52, 0x65,
+	0x6a, 0x65, 0x63, 0x74, 0x65, 0x64, 0x54, 0x61, 0x73, 0x6b, 0x44, 0x69, 0x6d, 0x65, 0x6e, 0x73,
+	0x69, 0x6f, 0x6e, 0x12, 0x10, 0x0a, 0x03, 0x6b, 0x65, 0x79, 0x18, 0x01, 0x20, 0x01, 0x28, 0x09,
+	0x52, 0x03, 0x6b, 0x65, 0x79, 0x12, 0x14, 0x0a, 0x05, 0x76, 0x61, 0x6c, 0x75, 0x65, 0x18, 0x02,
+	0x20, 0x01, 0x28, 0x09, 0x52, 0x05, 0x76, 0x61, 0x6c, 0x75, 0x65, 0x4a, 0x04, 0x08, 0x0a, 0x10,
+	0x0b, 0x52, 0x18, 0x73, 0x79, 0x6e, 0x63, 0x68, 0x72, 0x6f, 0x6e, 0x6f, 0x75, 0x73, 0x5f, 0x6c,
+	0x6f, 0x67, 0x5f, 0x64, 0x61, 0x74, 0x61, 0x5f, 0x75, 0x72, 0x6c, 0x1a, 0x61, 0x0a, 0x12, 0x43,
+	0x6f, 0x6e, 0x73, 0x6f, 0x6c, 0x69, 0x64, 0x61, 0x74, 0x65, 0x64, 0x52, 0x65, 0x73, 0x75, 0x6c,
+	0x74, 0x12, 0x4b, 0x0a, 0x08, 0x61, 0x74, 0x74, 0x65, 0x6d, 0x70, 0x74, 0x73, 0x18, 0x01, 0x20,
+	0x03, 0x28, 0x0b, 0x32, 0x2f, 0x2e, 0x74, 0x65, 0x73, 0x74, 0x5f, 0x70, 0x6c, 0x61, 0x74, 0x66,
+	0x6f, 0x72, 0x6d, 0x2e, 0x73, 0x74, 0x65, 0x70, 0x73, 0x2e, 0x45, 0x78, 0x65, 0x63, 0x75, 0x74,
+	0x65, 0x52, 0x65, 0x73, 0x70, 0x6f, 0x6e, 0x73, 0x65, 0x2e, 0x54, 0x61, 0x73, 0x6b, 0x52, 0x65,
+	0x73, 0x75, 0x6c, 0x74, 0x52, 0x08, 0x61, 0x74, 0x74, 0x65, 0x6d, 0x70, 0x74, 0x73, 0x42, 0x3f,
+	0x5a, 0x3d, 0x67, 0x6f, 0x2e, 0x63, 0x68, 0x72, 0x6f, 0x6d, 0x69, 0x75, 0x6d, 0x2e, 0x6f, 0x72,
+	0x67, 0x2f, 0x63, 0x68, 0x72, 0x6f, 0x6d, 0x69, 0x75, 0x6d, 0x6f, 0x73, 0x2f, 0x69, 0x6e, 0x66,
+	0x72, 0x61, 0x2f, 0x70, 0x72, 0x6f, 0x74, 0x6f, 0x2f, 0x67, 0x6f, 0x2f, 0x74, 0x65, 0x73, 0x74,
+	0x5f, 0x70, 0x6c, 0x61, 0x74, 0x66, 0x6f, 0x72, 0x6d, 0x2f, 0x73, 0x74, 0x65, 0x70, 0x73, 0x62,
+	0x06, 0x70, 0x72, 0x6f, 0x74, 0x6f, 0x33,
 }
 
 var (
@@ -704,7 +788,7 @@
 	return file_test_platform_steps_execution_proto_rawDescData
 }
 
-var file_test_platform_steps_execution_proto_msgTypes = make([]protoimpl.MessageInfo, 10)
+var file_test_platform_steps_execution_proto_msgTypes = make([]protoimpl.MessageInfo, 11)
 var file_test_platform_steps_execution_proto_goTypes = []interface{}{
 	(*ExecuteRequests)(nil),            // 0: test_platform.steps.ExecuteRequests
 	(*ExecuteResponses)(nil),           // 1: test_platform.steps.ExecuteResponses
@@ -715,41 +799,43 @@
 	(*ExecuteResponse_TaskResult)(nil), // 6: test_platform.steps.ExecuteResponse.TaskResult
 	(*ExecuteResponse_ConsolidatedResult)(nil),        // 7: test_platform.steps.ExecuteResponse.ConsolidatedResult
 	(*ExecuteResponse_TaskResult_TestCaseResult)(nil), // 8: test_platform.steps.ExecuteResponse.TaskResult.TestCaseResult
-	nil,                                  // 9: test_platform.steps.ExecuteResponse.TaskResult.RejectedTaskDimensionsEntry
-	(*execute.Build)(nil),                // 10: test_platform.steps.execute.Build
-	(*test_platform.Request_Params)(nil), // 11: test_platform.Request.Params
-	(*EnumerationResponse)(nil),          // 12: test_platform.steps.EnumerationResponse
-	(*config.Config)(nil),                // 13: test_platform.config.Config
-	(*test_platform.TaskState)(nil),      // 14: test_platform.TaskState
-	(*common.TaskLogData)(nil),           // 15: test_platform.common.TaskLogData
-	(test_platform.TaskState_Verdict)(0), // 16: test_platform.TaskState.Verdict
+	nil, // 9: test_platform.steps.ExecuteResponse.TaskResult.RejectedTaskDimensionsEntry
+	(*ExecuteResponse_TaskResult_RejectedTaskDimension)(nil), // 10: test_platform.steps.ExecuteResponse.TaskResult.RejectedTaskDimension
+	(*execute.Build)(nil),                // 11: test_platform.steps.execute.Build
+	(*test_platform.Request_Params)(nil), // 12: test_platform.Request.Params
+	(*EnumerationResponse)(nil),          // 13: test_platform.steps.EnumerationResponse
+	(*config.Config)(nil),                // 14: test_platform.config.Config
+	(*test_platform.TaskState)(nil),      // 15: test_platform.TaskState
+	(*common.TaskLogData)(nil),           // 16: test_platform.common.TaskLogData
+	(test_platform.TaskState_Verdict)(0), // 17: test_platform.TaskState.Verdict
 }
 var file_test_platform_steps_execution_proto_depIdxs = []int32{
 	2,  // 0: test_platform.steps.ExecuteRequests.requests:type_name -> test_platform.steps.ExecuteRequest
 	4,  // 1: test_platform.steps.ExecuteRequests.tagged_requests:type_name -> test_platform.steps.ExecuteRequests.TaggedRequestsEntry
-	10, // 2: test_platform.steps.ExecuteRequests.build:type_name -> test_platform.steps.execute.Build
+	11, // 2: test_platform.steps.ExecuteRequests.build:type_name -> test_platform.steps.execute.Build
 	3,  // 3: test_platform.steps.ExecuteResponses.responses:type_name -> test_platform.steps.ExecuteResponse
 	5,  // 4: test_platform.steps.ExecuteResponses.tagged_responses:type_name -> test_platform.steps.ExecuteResponses.TaggedResponsesEntry
-	11, // 5: test_platform.steps.ExecuteRequest.request_params:type_name -> test_platform.Request.Params
-	12, // 6: test_platform.steps.ExecuteRequest.enumeration:type_name -> test_platform.steps.EnumerationResponse
-	13, // 7: test_platform.steps.ExecuteRequest.config:type_name -> test_platform.config.Config
+	12, // 5: test_platform.steps.ExecuteRequest.request_params:type_name -> test_platform.Request.Params
+	13, // 6: test_platform.steps.ExecuteRequest.enumeration:type_name -> test_platform.steps.EnumerationResponse
+	14, // 7: test_platform.steps.ExecuteRequest.config:type_name -> test_platform.config.Config
 	6,  // 8: test_platform.steps.ExecuteResponse.task_results:type_name -> test_platform.steps.ExecuteResponse.TaskResult
 	7,  // 9: test_platform.steps.ExecuteResponse.consolidated_results:type_name -> test_platform.steps.ExecuteResponse.ConsolidatedResult
-	14, // 10: test_platform.steps.ExecuteResponse.state:type_name -> test_platform.TaskState
+	15, // 10: test_platform.steps.ExecuteResponse.state:type_name -> test_platform.TaskState
 	2,  // 11: test_platform.steps.ExecuteRequests.TaggedRequestsEntry.value:type_name -> test_platform.steps.ExecuteRequest
 	3,  // 12: test_platform.steps.ExecuteResponses.TaggedResponsesEntry.value:type_name -> test_platform.steps.ExecuteResponse
-	14, // 13: test_platform.steps.ExecuteResponse.TaskResult.state:type_name -> test_platform.TaskState
+	15, // 13: test_platform.steps.ExecuteResponse.TaskResult.state:type_name -> test_platform.TaskState
 	8,  // 14: test_platform.steps.ExecuteResponse.TaskResult.test_cases:type_name -> test_platform.steps.ExecuteResponse.TaskResult.TestCaseResult
 	8,  // 15: test_platform.steps.ExecuteResponse.TaskResult.prejob_steps:type_name -> test_platform.steps.ExecuteResponse.TaskResult.TestCaseResult
-	15, // 16: test_platform.steps.ExecuteResponse.TaskResult.log_data:type_name -> test_platform.common.TaskLogData
+	16, // 16: test_platform.steps.ExecuteResponse.TaskResult.log_data:type_name -> test_platform.common.TaskLogData
 	9,  // 17: test_platform.steps.ExecuteResponse.TaskResult.rejected_task_dimensions:type_name -> test_platform.steps.ExecuteResponse.TaskResult.RejectedTaskDimensionsEntry
-	6,  // 18: test_platform.steps.ExecuteResponse.ConsolidatedResult.attempts:type_name -> test_platform.steps.ExecuteResponse.TaskResult
-	16, // 19: test_platform.steps.ExecuteResponse.TaskResult.TestCaseResult.verdict:type_name -> test_platform.TaskState.Verdict
-	20, // [20:20] is the sub-list for method output_type
-	20, // [20:20] is the sub-list for method input_type
-	20, // [20:20] is the sub-list for extension type_name
-	20, // [20:20] is the sub-list for extension extendee
-	0,  // [0:20] is the sub-list for field type_name
+	10, // 18: test_platform.steps.ExecuteResponse.TaskResult.rejected_dimensions:type_name -> test_platform.steps.ExecuteResponse.TaskResult.RejectedTaskDimension
+	6,  // 19: test_platform.steps.ExecuteResponse.ConsolidatedResult.attempts:type_name -> test_platform.steps.ExecuteResponse.TaskResult
+	17, // 20: test_platform.steps.ExecuteResponse.TaskResult.TestCaseResult.verdict:type_name -> test_platform.TaskState.Verdict
+	21, // [21:21] is the sub-list for method output_type
+	21, // [21:21] is the sub-list for method input_type
+	21, // [21:21] is the sub-list for extension type_name
+	21, // [21:21] is the sub-list for extension extendee
+	0,  // [0:21] is the sub-list for field type_name
 }
 
 func init() { file_test_platform_steps_execution_proto_init() }
@@ -843,6 +929,18 @@
 				return nil
 			}
 		}
+		file_test_platform_steps_execution_proto_msgTypes[10].Exporter = func(v interface{}, i int) interface{} {
+			switch v := v.(*ExecuteResponse_TaskResult_RejectedTaskDimension); i {
+			case 0:
+				return &v.state
+			case 1:
+				return &v.sizeCache
+			case 2:
+				return &v.unknownFields
+			default:
+				return nil
+			}
+		}
 	}
 	type x struct{}
 	out := protoimpl.TypeBuilder{
@@ -850,7 +948,7 @@
 			GoPackagePath: reflect.TypeOf(x{}).PkgPath(),
 			RawDescriptor: file_test_platform_steps_execution_proto_rawDesc,
 			NumEnums:      0,
-			NumMessages:   10,
+			NumMessages:   11,
 			NumExtensions: 0,
 			NumServices:   0,
 		},
diff --git a/src/test_platform/steps/execution.proto b/src/test_platform/steps/execution.proto
index d69ffff..ee40072 100644
--- a/src/test_platform/steps/execution.proto
+++ b/src/test_platform/steps/execution.proto
@@ -96,7 +96,21 @@
         // Any rejected task dimensions from the task execution request,
         // stored as key-value pairs. This field is only populated if the
         // task was rejected by Swarming due to a lack of matching bot.
-        map<string, string> rejected_task_dimensions = 11;
+        // DEPRECATED: use rejected_dimensions instead, as it allows multiple
+        // values for the same key. This will be deleted soon.
+        // TODO(https://crbug.com/11798680)
+        map<string, string> rejected_task_dimensions = 11
+            [deprecated = true];
+
+        message RejectedTaskDimension {
+          string key = 1;
+          string value = 2;
+        }
+
+        // Any rejected task dimensions from the task execution request,
+        // stored as key-value pairs. This field is only populated if the
+        // task was rejected by Swarming due to a lack of matching bot.
+        repeated RejectedTaskDimension rejected_dimensions = 12;
 
         reserved 10;
         reserved "synchronous_log_data_url";