A method for a computing system, comprising: in response to receiving a command to remove at least a first and a second media item from a queue (800A-D) of media items, wherein the queue (800A-D) is a cloud queue: removing the at least first and second media items from the queue (800A-D) of media items; adding to the queue (800A-D) of media items at least first and second indications that the at least first and second given media items, respectively, have been removed from the queue (800A-D); after adding the indications to the queue (800A-D), receiving, from a playback device, while the playback device is playing back the first media item, a request for one or more media items to update a locally stored copy of the queue (800A-D), starting from the first media item that is currently being played back by the playback device, determining, based on the indication included in the queue, that the media item currently being played back has been removed from the queue, in response to determining that the media item currently being played back has been removed from the queue, sending to the playback device a list of media items beginning from the media item currently being played back and including the indication that the media item currently being played back has been removed from the queue, receiving, from the playback device a second request for one or more media items to update the locally stored copy of the queue (800A-D), starting from the second media item that is currently being played back by the playback device, in response to the second request from the playback device: determining that the second media item has been removed from the queue of media items based on the indication associated with the second media item; in response to determining that the second media item has been removed, sending the list of media items starting from the second media item and including the second indication that the second media item has been removed from the queue (800A-D); determining that the number of requests for the one or more media items received since adding the indications to the queue of media items is greater than a threshold number; and in response to determining that the number of requests is greater than the threshold number, removing the first and second indications from the queue (800A-D) of media items. removing the at least first and second media items from the queue (800A-D) of media items; adding to the queue (800A-D) of media items at least first and second indications that the at least first and second given media items, respectively, have been removed from the queue (800A-D); after adding the indications to the queue (800A-D), receiving, from a playback device, while the playback device is playing back the first media item, a request for one or more media items to update a locally stored copy of the queue (800A-D), starting from the first media item that is currently being played back by the playback device, determining, based on the indication included in the queue, that the media item currently being played back has been removed from the queue, in response to determining that the media item currently being played back has been removed from the queue, sending to the playback device a list of media items beginning from the media item currently being played back and including the indication that the media item currently being played back has been removed from the queue, receiving, from the playback device a second request for one or more media items to update the locally stored copy of the queue (800A-D), starting from the second media item that is currently being played back by the playback device, in response to the second request from the playback device: determining that the second media item has been removed from the queue of media items based on the indication associated with the second media item; in response to determining that the second media item has been removed, sending the list of media items starting from the second media item and including the second indication that the second media item has been removed from the queue (800A-D); determining that the number of requests for the one or more media items received since adding the indications to the queue of media items is greater than a threshold number; and in response to determining that the number of requests is greater than the threshold number, removing the first and second indications from the queue (800A-D) of media items.