According to Reuters, Apple “has completed work” on its rumored cloud-based music service that will allow users to store their music online, and access it anywhere using a computer or an iOS device connected to the Internet.

Apple Inc has completed work on an online music storage service and is set to launch it ahead of Google Inc, whose own music efforts have stalled, according to several people familiar with both companies’ plans. Apple’s plans will allow iTunes customers to store their songs on a remote server, and then access them from wherever they have an Internet connection, said two of these people who asked not to be named as the talks are still confidential.

Reuters also claims Apple hasn’t secured any deal with music labels yet, and industry sources said several labels are hoping to close these deals before the service’s launch. Similarly to Amazon’s recently launched Cloud Drive and Cloud Player, Apple could introduce a service that works on the web and mobile devices, and offers a way for users to “digitally lock” their own media in the cloud – quite possibly without even needing the blessing of music labels to do so. Amazon, for instance, was initially rumored to be in a lot of trouble with licensing deals after the Cloud Player launch, but as of today no major music label has sued the online retailer – which basically gives its users an online space to store their DRM-free songs. Amazon, however, is reportedly in talks with labels anyway to come up with a more “advanced” plan that meets the music industry’s expectations and requirements.

Apple, on the other hand, might launch a service that acts as a remote backup location for a user’s iTunes library, and it could be part of the rumored new MobileMe – a complete revamp of the suite of online sync tools that’s also expected to be free, and deeply integrated into future versions of iOS. A number of reports in the past months indicated Apple was building an online iTunes backup solution with built-in streaming capabilities, although others claimed the company was also focusing on a subscription-based model for streaming the entire iTunes Store catalogue – similarly to how music service Spotify requires a premium subscription to stream music you don’t own.

Last, Reuters reports:

Apple and Google are keen to offer services that give music fans more flexibility to access their media wherever they are rather than tying them to a particular computer or mobile device.

In late 2009, Apple bought Lala, a cloud-based music company, but closed it down in April 2010, leading to speculation that it would launch an Apple-branded cloud service.

Interestingly enough, a series of downtimes and errors in iTunes and the App Store during the past 2 days lead many to believe Apple moved its iTunes servers to the new data center in North Carolina, which was set to become fully operative in Spring 2011.

Update: Peter Kafka at MediaMemo corroborates Reuters’ report on Apple’s finalized cloud-based music service, but he says “sources” told him that Apple has already closed deals with two of the “big four labels” (Warner, Universal, Sony and EMI), and that Apple’s Eddy Cue will be in New York tomorrow to close the remaining deals.

From the music industry’s perspective, however, there’s a big difference: Amazon started its service without getting approval from the big music labels. But Apple is actively seeking licenses for its service, and will pay the labels for the privilege.

“They’ve been very aggressive and thoughtful about it,” says an industry executive. “It feels like they want to go pretty soon.

Kafka also claims Apple’s service will benefit from the labels’ deals to offer an overall better system with better sound quality:

Amazon’s service does the same thing, but label executives have argued that a license would allow Apple (or Google, if it moves forward on similar, but stalled, plans) to create a more “robust service”, with better user interfaces, sound quality, and other features.

Last, it appears that Apple will allow both uploading of songs from hard drives and direct streaming (without needing an upload) of songs previously purchased with an iTunes account:

there’s at least one practical benefit from Apple’s perspective: The deals it is signing will allow it to store a single master copy of a song on its servers, and share that with multiple users.