データコレクションの登録を受信するステップであって、前記データコレクションが第1のプログラムによって作成され、前記登録が前記第1のプログラムを実行する機械上のオブジェクトランタイムコンポーネントから受信される、ステップと、前記第1のプログラムとは異なる第2のプログラムから前記データコレクションへの加入を受信するステップであって、前記データコレクションへの加入者のセットがあり、加入者の前記セットが前記第1のプログラムおよび前記第2のプログラムを備える、ステップと、前記加入者のうちの第1の加入者が前記データコレクションの状態に変更を行う第1の操作を前記データコレクションに実行したという第1の通知を受信するステップと、前記状態の前記変更を加入者の前記セットに伝搬するステップとを備える、データコレクションの共有を容易にする方法。前記加入者のうちの第2の加入者が前記データコレクションに第2の操作を実行したという第2の通知を受信するステップであって、前記第2の操作が前記第1の操作とは異なる、ステップと、前記第2の操作を前記第1の操作に対して変換することによって前記第1の操作と前記第2の操作との間の衝突を解決するステップとをさらに備える、請求項1に記載の方法。前記第2の通知が、前記データコレクションのアイテムの順序位置を使用して前記第2の操作を記述し、前記順序位置が、前記第1の操作が前記第2の操作の前に実行されるか、または前記第2の操作の後に実行されるかによって異なるアイテムを参照する、請求項2に記載の方法。前記データコレクションの真の状態で前記データコレクションのコピーを維持するステップをさらに備え、前記伝搬するステップが、前記真の状態を前記加入者に通信するステップを備える、請求項1に記載の方法。前記伝搬するステップが、前記第1の操作を実行することによって得られる、前記データコレクションの状態の前記加入者のバージョンに関連する変更の記述を、前記加入者に通信するステップを備える、請求項1に記載の方法。前記データコレクション内のアイテムのコンテンツの構造に関係なく実行される、請求項1に記載の方法。前記第1の通知が、前記データコレクションに実行される操作のタイプ、操作されているアイテムの前記データコレクション内の位置、および前記データコレクションの状態を備える、請求項1に記載の方法。請求項1乃至7のいずれか一項に記載の方法を実行するためのコンピューター実行可能指示を備える、コンピューター可読媒体。プロセッサーと、メモリーと、前記メモリーに格納されて前記プロセッサー上で実行するコレクション共有コンポーネントとを備え、前記コレクション共有コンポーネントが第1の機械上に前記データコレクションを作成する第1のプログラムから登録要求を受信し、第2の機械上で実行する第2のプログラムから前記データコレクションへの加入要求を受信し、前記第1のプログラムが前記第2のプログラムとは異なり、前記第1の機械が前記第2の機械とは異なり、前記コレクション共有コンポーネントが、加入者のセットの第1のメンバーから、前記データコレクションの状態を変更する第1の操作が前記第1のメンバーによって実行されたという第1の通知を受信し、前記状態が変更されたという第2の通知を加入者の前記セットに伝搬し、加入者の前記セットが前記第1のプログラムおよび前記第2のプログラムを備える、データコレクションの共有を容易にするためのシステム。前記コレクション共有コンポーネントが、加入者の前記セットの第2のメンバーから、前記第2のメンバーが前記データコレクションに第2の操作を実行したという第3の通知を受信し、前記第2の操作を前記第1の操作に対して変換することによって前記第1の操作と前記第2の操作との間の衝突を解決し、前記第1の操作が前記第2の操作とは異なり、前記第1のメンバーが前記第2のメンバーとは異なる、請求項9に記載のシステム。前記第2の通知が、前記データコレクションのアイテムの順序位置を使用して前記第2の操作を記述し、前記順序位置が、前記第1の操作が前記第2の操作の前に実行されるか、または前記第2の操作の後に実行されるかによって異なるアイテムを参照する、請求項10に記載のシステム。前記コレクション共有コンポーネントが、前記データコレクションの真の状態で前記データコレクションのコピーを維持し、前記第2の通知が前記真の状態を備える、請求項9に記載のシステム。前記第2の通知が、前記第1の操作を実行することによって得られる、前記データコレクションの状態の前記加入者のバージョンに関連する変更の記述を備える、請求項9に記載のシステム。前記コレクション共有コンポーネントが、前記データコレクション内のアイテムのコンテンツの構造に関係なく前記第2の通知を伝搬する、請求項9に記載のシステム。前記第1の通知が、前記データコレクションに実行される操作のタイプ、操作されているアイテムの前記データコレクション内の位置、および前記データコレクションの状態を備える、請求項9に記載のシステム。本発明は共有データコレクションを提供するものである。0004共有コレクションの概念は、共有メカニズムをプログラマーにとって透過的にする方法で実装されうる。さらに、そのコレクションがいくつかの異なるエンティティによって操作されている場合、共有コレクションを実装するメカニズムは、コレクションのためにデータ収束を提供できる。0005一例では、共有オブジェクトサーバーは、所与のどの時間にもコレクションの真の状態を維持することによって、コレクションの共有を管理する。コレクションにアクセスできるプログラムは、そのプログラムを実行している機械上の共有オブジェクトランタイムに接続しうる。共有コレクションにアクセスするプログラムは、そのコレクションを共有コレクションとして登録して、この登録はランタイムによって共有オブジェクトサーバーに通信されうる。コレクションにアクセスしたい他のプログラムも、そのコレクションを共有コレクションとして登録する。同様に、その登録がランタイムによって共有オブジェクトサーバーに通信される。さらに、プログラムはコレクションの変更通知に加入でき、加入要求はランタイムによって処理される。それぞれのプログラムは、コレクションのローカルコピーを維持する。コレクションの状態が何らかの方法で変更されると、変更が生じた機械上のランタイムが、その変更を共有オブジェクトサーバーに通信する。共有オブジェクトサーバーは、コレクションの真の状態をアップデートして、加入プログラムを実行している機械上の共有オブジェクトランタイムを通じてそのコレクションを登録した全てのプログラムに変更を通信する。次いで、これらのそれぞれのプログラムが、サーバーによって通信された状態変更に従ってコレクションのローカルコピーをアップデートする。コレクションに同時変更が生じた場合、共有オブジェクトサーバーは変更間のあらゆる衝突を解決して、コレクションの真の状態に決定論的に到達する。0006他の例では、共有オブジェクトは、クライアント/サーバー方式ではなくピアツーピア方式で管理される。ピアツーピア実装形態では、共有コレクションへのそれぞれの加入者が、他の加入者に変更を通信できる。次いで、加入者が実行する機械上のランタイムは、あらゆる衝突を決定論的に解決しながら、彼らのローカルコピーを変更できる。0007コレクションは、ほぼあらゆるプログラミング言語たとえば、C、C、Java登録商標、VisualBasic等で実装されうる。共有コレクションの概念は広範なプログラミングモデルで実装されうるので、異なる言語で書かれたプログラムが同じ共有コレクションを操作できる。さらに、プログラマーは、プログラムが完全にローカルなコレクションを操作するのと同じ方法で、共有コレクションを操作するプログラムを書くことができる。したがって、プログラムは、新しいコレクションを登録するための、または既存のコレクションへの変更に加入するための指示を出す以外の任意の方法で、コレクションの共有性質を認識せずに共有コレクションを操作できる。このように、効果的なコレクションの共有は、プログラムおよびプログラマーにとって透過的に行われる。さらに、共有メカニズムはコレクション内のデータのタイプにとらわれる必要はなく、したがってあらゆるタイプのデータのコレクションを共有できる。0008この概要は、以下の詳細な説明においてさらに説明する概念の選択を、簡単な形式で紹介するために提供するものである。この概要は、特許請求の範囲に記載された対象の主な特徴または基本的な特徴を識別することを意図するものではなく、特許請求の範囲に記載された対象の範囲を限定するために使用されることを意図するものでもない。0015現代のコンピューティングでは、同じ基本データへのアクセスを共有することによって、プログラムはしばしば互いに同時使用する。プログラムがデータを共有する場合、プログラムは、データが共有されているという事実を認識する方法でしばしば実装される。すなわち、一般的にプログラムは、他のプログラム、または同じプログラムの他のインスタンスとデータを共有するメカニズムの実装形態を含む必要がある。共有するためのメカニズムは、しばしば共有されているデータの性質、およびプログラマーの設計選択に特有である。したがって、2つのプログラムがデータを共有したい場合、それぞれのプログラマーは通常特定の共有メカニズムに同意して、実装する必要がある。限定された形式のデータ共有を可能にする特定の一般化されたメカニズムがあるが、特定の状況にはあまり適さない。0016あらゆる種類のデータの共有が様々な実装形態の問題を提示しているが、共有されるデータがコレクションである場合はさらなる問題が提示される。コレクションは、同時に操作されうるデータアイテムの集まりである。コレクションのいくつかの例には、リスト、アレー、セット、バッグ、および他の様々なデータの集まりがある。いくつかのタイプのコレクションは順序付けされる。すなわち、順序コレクションの現在の状態は、単にコレクションのコンテンツによってだけではなく、それらのコンテンツが出現する順序によって定義される。たとえば、{1、2、3、4、5}は、1から5までの全ての整数を含むデータのコレクションである。コレクションが順序付けられると、{1、2、3、4、5}と{2、3、1、5、4}とは、両方とも同じアイテムを含んではいるものの順序が異なるので、これらの2つの状態は異なる状態である。0017同時に実行しているプログラム間で任意のタイプのデータが共有されると、データの2つの修正が衝突する可能性がある。たとえば、あるプログラムがデータを修正しようとし、他のプログラムが同時にそのデータを削除しようとする場合がある。しかし、このような衝突が生じて、共有されているデータがコレクションの一部である場合、さらなる困難な事態が生じる。あるプログラムは、コレクション内の2番目のアイテムの後に、あるアイテムの挿入を要求する場合がある。他のプログラムは、2番目のアイテムを削除して、それによって、挿入されたアイテムを2番目のアイテムにするよう要求する場合がある。これらの変更を処理して、コレクションの真の状態に到達するために、元のコレクション内のどのアイテムが現在2番目であるかを決定しなければならない。それぞれのプログラムは、他のプログラムが同じコレクションを操作していることに気付かない場合があるので、両方のプログラムはコレクション内の2番目のアイテムを参照しながら、コレクション内のどのアイテムが実際に2番目の順序であるかについて異なる理解を有している場合がある。0018操作変換の分野は、コンピューティングにおいてデータの決定論的な順序付けを可能にするメカニズムに関係がある。これらのメカニズムのいくつかは、同時に操作されているファイル間の衝突を解決するために、たとえば、2人のユーザによって同時に編集されているテキストファイルに何の編集が生じたかを決定するために使用されうる。しかし、これらのタイプの技法は、一般に本明細書に記載されたコレクションの一般化された共有のタイプには適用されない。0019本明細書に記載された対象は、データコレクションを共有するためのメカニズムを提供する。本明細書に記載された技法は、いくつかのプログラムおよび/または同じプログラムのいくつかのインスタンスがコレクションへのアクセスを共有できるようにする、一般化されたコレクション共有メカニズムを提供するために使用されうる。これらの技法により、異なるプログラミング言語でプログラムを実装できるようになる。この技法により、コレクションが、そのコレクションを使用している全てのプログラムに伝搬されうる特定の状態に決定論的に到達できるような方法で、順序付けされたデータのコレクションを複数のプログラムおよび/またはプログラムインスタンスによって同時に操作できるようになる。さらに、本明細書に記載された技法により、プログラマーは、プログラムが完全にローカルなコレクションを操作するのとほぼ同じ方法で、共有コレクションを操作するプログラムを書けるようになる。さらに、共有メカニズムは、コレクション内の基本的なデータのタイプにとらわれないように作成でき、したがって、あらゆる適切な種類のデータについて、同じ一般化された共有メカニズムを使用できるようになる。言い換えれば、本明細書に記載された様々な動作を、コレクション内のデータアイテムのコンテンツに関係なく、またそれらのアイテムのコンテンツの構造に関係なく実行できるようになる。0020データを共有するプログラムは、単一の機械上で実行してもよく、ネットワークを通じて接続された、いくつかの機械上で実行してもよい。データの共有を容易にするために、プログラムを実行しているそれぞれの機械は共有オブジェクトランタイムを有することができる。共有オブジェクトランタイムは、共有コレクションを含む共有データオブジェクトの共有および同期の管理に役立つ場合がある。一例では、共有オブジェクトサーバーが共有コレクションの真の状態を維持する。機械上の共有コレクションに変更が行われると、その機械上のランタイムは共有オブジェクトサーバーにその変更を通知する。サーバーは、ローカル変更に応答して、コレクションの真の状態を変更できる。2つのプログラムが同時にコレクションに変更を行うと、共有オブジェクトサーバーは、真の状態に到達するために変更を解決でき、可能な限り、両方のプログラムが達成しようとしたコレクションの状態を反映できる。したがって、2つの異なるプログラムが、他の変更を知らずに同じコレクションをそれぞれ変更すると、サーバーはこれらの変更のうちの1つを実行してコレクションの新しい状態を作成でき、次いで、変更を行ったときにコレクションの新しい状態を知っていれば、もう1つのプログラムが行いたかった変更を反映するために可能な限りもう1つの変更を変換できる。サーバーは、様々な機械上のランタイムに変更または、該当する場合は変換された変更を通知して、そのコレクションに加入しているプログラムが、サーバーによって伝搬された変更に従ってそのローカルコピーをアップデートする。他の例では、コレクション共有はピアツーピアアーキテクチャに実装され、そのアーキテクチャでは、共有コレクションに加入するそれぞれのプログラムが、プログラムが行った変更を他のプログラムに通知して、他の加入者または、それらの加入者が実行している機械上のランタイムコンポーネントがサーバーの援助なしにそれらのローカルコピーを変更に同期させる。0021プログラムがコレクションを作成すると、プログラムはコレクションを共有コレクションとして登録するための指示を出すことができる。この指示は、プログラムを実行している機械上のランタイムによって受信でき、ランタイムは共有オブジェクトサーバーに登録を報告できる。次いで、共有オブジェクトサーバーは、コレクションの最初の状態を表すコレクションのコピーを受信する。この時点から、コレクションを作成したプログラムは、ランタイムが共有オブジェクトサーバーへのまたは、ピアツーピア実装形態では他の加入者への変更の報告、および共有オブジェクトサーバーから受信した状態変更の同期を管理するので、コレクションが完全にローカルであった場合とほぼ同じ方法で、コレクションを操作できる。0022あるプログラムが、他のプログラムによって作成された共有コレクションを使用したい場合、そのプログラムはそのコレクションを登録するための指示を出す。その指示は、ランタイムによって受信されて、共有オブジェクトサーバーに送信されうる。次いで、共有オブジェクトサーバーは、加入プログラムを実行している機械上のランタイムに、コレクションの状態へのあらゆる変更を通知することを知っている。プログラムがコレクションに加入すると、コレクションの現在の真の状態のコピーを受信でき、次いでローカルコレクションとして格納できる。次いで、加入プログラムは、コレクションがローカルであった場合とほぼ同じ方法で、共有コレクションを操作できる。このようにして、効果的なコレクションの共有は、そのコレクションを作成および登録するプログラムと、そのコレクションに加入するプログラムとの両方にとって、透過的に行われる。上述のように、システムは、コレクション内のデータの性質にとらわれる必要がないので、共有メカニズムはあらゆる種類の基本的なデータを含むコレクションと協働できる。0023図1は、共有コレクション102の例を示している。共有コレクション102は、何らかの方法で相互に関連する、ならびにプログラム104、106、および108などの複数のプログラムによってアクセスたとえば、読出しおよび書込みされうる、データアイテムのセットを備えうる。プログラム104~108は、同じプログラムの異なる実行インスタンスたとえば、いくつかの別個の処理で実行している同じアプリケーションでもよく、異なるプログラムでもよい。さらに、プログラム104~108は全て同じ機械上で実行してもよく、異なる機械上で実行してもよい。どちらの場合でも、プログラム104~108は、異なるプログラムでもよく、同じプログラムの別々の実行インスタンスでもよいという意味で、別個のものとして記述できる。コレクション共有メカニズム110は、プログラム104~108の間で共有コレクション102を共有することを容易にすることができる。コレクション共有メカニズム110の例示的実装形態は、以下で図2~7に関連して説明する。0024共有コレクション102は、共通の名前空間を共有するプログラムによって共有コレクション102が識別されうるようにする、名前112を有することができる。名前112の代用としてまたは、名前112に加えて、共有コレクション102は、共有コレクション102と他の共有コレクションとを区別する識別子114を有することもできる。識別子114は、たとえば、まだ名前が割り当てられていないコレクションに適用されうるので、これらのコレクションは、フレンドリーな名前がコレクションに割り当てられる前にシステムによって識別されうる。0025共有コレクション102は、複数のデータアイテムを有することができる。図1の例では、4つのデータアイテム116、118、120、および122が示されているが、コレクションはいくつのデータアイテムを有してもよい。それぞれのデータアイテムは、あらゆるタイプのデータを含みうる。共有コレクションに格納されうるデータのいくつかの例は、以下で図4および5に関連してより詳細に説明する。しかし、一般的な例として、コレクションに格納されうるいくつかのタイプのデータは、数または単語などの基本的なデータタイプ、またはやることリスト上のタスクを表す構造などのより複雑なプログラマー定義のデータタイプ、あるいはユーザインターフェースの要素である。本明細書に記載されたメカニズムは、データのタイプにとらわれる必要がないので、コレクション内の個々のデータアイテムは、基本的なデータタイプから、入り組んだスキーマを備える複雑なユーザ定義のデータタイプまでのいずれでもよい。0026図1の例では、共有コレクション102は順序付けされたコレクションである、上述のように、順序付けされたコレクションは、コレクションの状態が、コレクション内のデータアイテムによってだけでなく、それらのデータアイテムの順序によって定義されるコレクションである。データアイテムの挿入または除去は順序付けされたコレクションの状態を変更するが、2つの既存のデータアイテム間の位置も変更する。したがって、共有コレクション102内のそれぞれのデータアイテムは順序位置を有する。順序位置124、126、128、および130は、それぞれデータアイテム116、118、120、および122に対応する。したがって、データアイテム116は1番目の位置にあり、データアイテム118は2番目の位置にあり、以下同様である。アイテムの順序数のうちのいずれかを変更する場合、この変更は、たとえアイテム自体には変更がなくても、共有コレクション102の状態における変更という結果になる。0027共有コレクション102に実行されうる例示的操作には、交換操作132および削除操作134がある。交換操作132はコレクション内の2つまたはより多くのアイテムの順序位置を交換し、削除操作134はコレクション内のアイテムのうちの1つを除去する。また、挿入操作136を実行して新しいデータアイテム138をコレクションに追加することによってコレクションを修正できる。これらの操作については、後に以下の議論で言及する。0028図2は、プログラムが共有コレクション102へのアクセスを共有できる例示的シナリオを示している。機械202は、プログラムを実行する機械である。機械202は、デスクトップまたはラップトップなどのパーソナルコンピューター、サーバーコンピューター、ハンドヘルドコンピューター、スマートフォン、セットトップボックスなどの、何らかの種類のコンピューティング機能を有するどのようなタイプの機械でもよい。図示された例では、機械202上で2つのプログラム204および206を実行しているが、機械上でいくつのプログラムを実行してもよい。0029機械202はデータを格納でき、機械202に格納されるあるタイプのデータは共有コレクション102のローカルコピーである。図2の例では、共有コレクション102はプログラム204によって作成される。コレクションが作成された時点では、コレクションはプログラム204にとってローカルかつプライベートでよい。しかし、プログラム204は、他のプログラムが可能であれば、他の機械上で実行するプログラムを含むコレクション102へのアクセスを共有できるようにするために、共有するためのコレクションを登録したい場合がある。したがって、プログラム204は登録指示208を出す。登録指示208は、プログラム204が書かれた何らかのプログラミング言語を通じて出されてもよく、共有オブジェクトランタイム210によって受信されうる。たとえば、共有オブジェクトランタイム210は、プログラム204が共有オブジェクトランタイム210に登録指示ならびに加入要求、および他のタイプの指示を出せるようにする、アプリケーションプログラミングインターフェースAPIを提供できる。0030登録指示208を受信すると、共有オブジェクトランタイム210は、共有コレクション102を共有オブジェクトサーバー212に登録できる。共有オブジェクトサーバー212は、共有コレクション102などの共有データオブジェクトの真の状態を維持して、また共有オブジェクトへの変更についての情報センターとして働くサーバーである。すなわち、共有オブジェクトサーバー212は、機械上で共有データが変更すると、およびその共有データの状態への変更を他の機械に伝搬すると、通知を受信する。共有コレクション102が共有オブジェクトサーバー212に登録されると、共有オブジェクトランタイム210は、共有コレクション102のコピーを提供できる。共有するために一旦コレクション102が登録されると、図2で共有オブジェクトサーバー212を表すボックス内部の真の状態で印をつけられたボックス内で示されるように、共有オブジェクトサーバー212はコレクション102の真の状態を維持する。本明細書の記述を通じて、プログラムまたは加入者送信を、サーバーまたは他の加入者への送信登録または加入要求と呼ぶ場合がある点に留意されたい。これらのタイプの要求を送信するプログラムの動作は、プログラムが要求をランタイムに通信し、ランタイムがその要求をサーバー、あるいは他の加入者またはランタイムに通信する場合を含む。同様に、後述するように、加入者は状態変更をサーバーまたは他の加入者に通信できる。加入者が状態変更を通信する動作は、加入者の機械上のランタイムが通信を実行する場合を含む。0031共有するために共有コレクション102が登録されると、コレクションに加入することによってプログラム204以外のプログラムがそのコレクションにアクセスできる。コレクションに加入するために、プログラムは加入要求214を提出できる。いくつかのコレクションは、それらの作成者によって指定されたアクセス制御制限に従う場合がある。このようなアクセス制御制限は、共有コレクションにアクセスできるプログラムのセットおよび/またはユーザ、および/または機械を限定しうる。しかし、共有コレクション102にアクセス制限がないまたは、アクセス制限があるが、共有コレクション102へのアクセスを求めている人は、そのコレクションにアクセスする許可を得ると仮定すると、共有コレクション102の加入によって、加入者はそのコレクションを読み出す、および/または修正することができるようになる。0032加入要求は、任意の機械の任意のプログラムから来る場合がある。たとえば、プログラム206は共有オブジェクトランタイム210を通じて加入要求を提出することによって、共有コレクション102に加入できる。プログラム206は、共有コレクション102の作成者すなわち、プログラム204と同じ機械202上にある点に留意されたい。しかし、加入プログラムは異なる機械上にある場合がある。たとえば、機械218上のプログラム216も、加入要求214を提出することによって共有コレクション102に加入する。プログラム216からの加入要求は、機械218用のランタイムである共有オブジェクトランタイム220を通じて提出される。それぞれの機械は、それ自身の共有オブジェクトランタイムのインスタンスを有することができる。さらに、共有コレクション102への加入要求は、機械222上、または他の任意の機械上で実行しているプログラムから来る場合もある。0033プログラムが共有コレクション102に加入すると、そのプログラムは、共有コレクション102の現在の真の状態のコピーを受信できる。たとえば、機械218上のプログラム216は、共有コレクション102のコピーを受信して、そのコピーを、機械218を表す図1のボックス内の、機械218に格納できるローカルコピーとラベル付けされた共有コレクション102のインスタンスによって示されるように。次いで、加入プログラムは、まるで完全にローカルなコレクションであるかのようにローカルコピーの読出しおよび書込みができる。プログラムを実行している機械上の共有オブジェクトランタイムのインスタンスたとえば、プログラム216の場合は共有オブジェクトランタイム220は、共有コレクション102のローカルコピーを監視して、プログラムが共有オブジェクトサーバー212に報告するべき変更を共有コレクションに行ったかどうかを決定できる。0034共有コレクション102への任意の加入者が、共有コレクション102のローカルコピーへの変更を行う操作を実行すると、その加入者の機械上の共有オブジェクトランタイムが、その操作を共有オブジェクトサーバー212に報告する。次いで、共有オブジェクトサーバー212は、共有コレクション102の現在の真の状態をアップデートして、オブジェクトへの加入者オブジェクトの作成者を含むに状態変更を通知する。0035共有オブジェクトサーバー212は、共有コレクション102の加入者間での状態情報の収集および伝搬を容易にする同期コンポーネント226を含むことができる。同期コンポーネント226が操作する方法は、実装形態に依存する場合がある。一例では、同期コンポーネントは、共有コレクション102のマスターコピーを真の状態で維持して、そのコレクションの状態が変化する時はいつでも共有コレクション102の新しいコピーを単に伝搬する。他の例では、同期コンポーネント226は、現在のバージョンに関連する共有コレクション102への変更のリストを維持して、それらの変更を様々なクライアントに伝搬する。次いで、それぞれのクライアントのランタイムは、共有コレクション102の真の状態を、そのローカル状態、および共有オブジェクトサーバー212から受信した変更に基づいて計算できる。共有オブジェクトサーバー212が全ての状態変更に応答して共有コレクション102の完全なコピーを伝搬しなくても、共有オブジェクトサーバー212は、共有コレクション102への同時変更を解決する方法を決定できるので、クライアント側のランタイムが変更の通知を受信すると、共有コレクション102の新しい状態を古い状態から計算できる。後述するように、同期コンポーネント226は必要に応じて変更を変換できるので、第1の加入者が第2の加入者の同時変更を知らずに行った変更を第1の加入者に送信でき、道理にかなう方法で適用でき、その結果、全ての加入者が共有コレクション102の同じ状態に収束する。0036同期コンポーネント226によって実行されるある機能は、どちらのクライアントも他の変更を知らない2つのクライアントによってコレクションに行われた変更を適用する方法を決定するためのものである。この状況は、2つのクライアントが、コレクション内の同じアイテムに関係する変更をほぼ同時に行う場合に発生する場合があるので、それぞれのクライアントは他の変更の通知を受信する前に変更を行う。たとえば、コレクション内の最初の2つのアイテムがアルファおよびベータであると仮定する。AおよびBと呼ばれる2つのクライアントの両方が、ほぼ同時にコレクションに変更を行う。Aは新しいアイテム、ガンマをアルファの後の位置に追加したいが、Bはベータを削除したい。したがって、Aは順序位置2で新しいアイテムを追加する操作を実行し、Bは順序位置2でアイテムを削除する操作を実行する。Aの操作が最初に実行されると、両方の操作後の最終的な状態は、アルファおよびベータが位置1および2をそれぞれ占めることになる。Bの操作が最初に実行されると、両方の操作後の最終的な状態は、アルファおよびガンマが順序位置1および2をそれぞれ占めることになる。同期コンポーネント226は、この明らかな矛盾を以下の方法で解決できる。0037この例のために、サーバーS、ならびにクライアントAおよびBを呼び出す。S、A、およびBは全て状態0から開始する。Aは操作Xを実行し、Bは操作Yを実行する。AもBも他の操作が実行されたことを知らないので、AおよびBはそれぞれ状態0で操作をSに報告する。すなわち、AおよびBはそれぞれ、コレクションが状態0で存在する時に、そのコレクションに操作を実行したことを報告する。ある操作を実行したので、次にAおよびBはそれぞれ状態を1にインクリメントする。しかしこれらの操作のうちの1つが最初にSに到達する。この例では、最初にXが到達したと仮定する。操作Xが、Sの現在の状態と一致する状態0で実行されたので、その操作がSに実行されて、変換されずにBに送信される。さらに、肯定応答がAに送信される。Sは現在状態1である。この時点で、BはSから操作Xを受信する。操作YはまだSによって確認されていないので、操作XがYに対して変換されて、コレクションに適用される。現在、Bは状態2である。操作YがSに到達すると、その操作は状態0で実行されたことを示す。0はもはやSの現在の状態ではないので、Sは、Yを実行した時にBは操作Xに気付かなかったと決定する。したがって、操作Yが操作Xに対して変換されて、Aに送信される。肯定応答がBに送信される。Sは現在状態2である。この時点で、Aは操作Yの変換されたバージョンを受信する。Aには未処理の操作はないので、変換されたYをさらに変換することなしに適用する。すなわち、変換されたYは状態1に対して実行されていることを示す。Aはすでに状態1なので、Yをこれ以上変換する根拠はない。Aは現在状態2である。さらに、AおよびBの両方でのコレクションのコピーは、現在同じデータを同じ順序で示す。0038図2は、サーバーがコレクションの共有を管理する、例示的クライアント/サーバータイプ実装形態を示している。しかし、ピアツーピア実装形態も使用されうる。図3は、コレクション共有のピアツーピア実装形態の例を示している。0039図3の例では、機械202、218、および222がコレクション102の共有に参加する図2で参加するように。たとえば、それぞれの機械は、共有コレクション102の加入者である1つまたは複数のプログラムを有することができる共有コレクションの作成者は、加入者の概念に含まれる。それぞれの機械は、共有オブジェクトランタイムのインスタンスを有する。すなわち、共有オブジェクトランタイム210、220、および302は、それぞれ機械202、218、および222上で動作する。ピアツーピア実装形態では、共有オブジェクトランタイムは、サーバーと通信するのではなく、直接相互に通信できる。さらに、共有オブジェクトランタイムは、入ってくる変更をサーバーによって実行させるのではなく、それらの変更の変換を担当してよい。したがって、異なるランタイムがコレクションへの衝突する変更を解決するための同じアルゴリズムを実装する限り、コレクションの現在の状態を決定論的に知ることができる。0040たとえば機械202上で共有コレクション102が変更されると、機械202上の共有オブジェクトランタイム210が状態変更304の通知を、機械218上の共有オブジェクトランタイム220、および機械222上の共有オブジェクトランタイム302に送出する。それぞれの共有オブジェクトランタイムは、コレクション102の新しい状態に到達するために、共有コレクション102の現在の状態に状態変更304を適用する。2つの異なる機械から2つの異なる状態変更が同時に来る場合、共有オブジェクトランタイムは、どの状態変更が適用されるべきかを決定するために、衝突解決アルゴリズムたとえば、同期コンポーネント226に関連して上述したアルゴリズムを適用できる。上述のように、アルゴリズムは決定論的に作成されうるので、衝突する変更の同じセットを受信する任意の2つのランタイムは、同じ方法で衝突を解決して、それによってコレクションを様々な異なる機械上で同じ状態に変更することができる。0041図4および5は、共有コレクションが使用されうる方法のいくつかの例を示している。図4および5における例は例示的なものであり、本明細書に記載された対象を限定するものではない。図4および5における例は、共有コレクションが使用されうる方法のいくつかの特定の例を与えるために提供されるに過ぎないが、共有コレクションが使用されうる他の数多くのコンテキストがあることが理解されよう。0042図4は、共有コレクションとして実装されうる例示的タスクリストを示している。タスクリスト内のそれぞれのアイテムは、実行されるべきタスクでよい。図示されたタスクリストは4つの例示的アイテム402、404、406、および408を含み、それらは会社のために新しい商品を開発しているワーキンググループによって実行されるタスクでよい。タスクリストはコレクションとして実装でき、実装されるべきそれぞれのタスクはコレクション内のアイテムであり、これらのアイテムが実行されるべき順序を表すこれらのアイテム間で順序が定められる。ワーキンググループのメンバーは皆、タスクリストの制御を有することができる。たとえば、タスクリストは、グループのそれぞれのメンバーがインスタンスを実行している電子メールおよびカレンダープログラムを通じてアクセスされうる。したがって、グループの異なるメンバーが、リスト上でアイテムを追加または削除してもよく、既存のアイテムを再構成してもよい。したがって、プログラムのそれぞれのインスタンスは、タスクリストを表すコレクションへの加入者でよい。グループの任意のメンバーがプログラムのインスタンスを使用してタスクリストに変更を行うと、その変更は、上述の方法でプログラムの他のインスタンスに伝搬されうる。したがって、ある人はプログラムの第1のインスタンスを使用して、1番目および2番目のタスクの順序を交換することができ数字410で示されるように、他の人はプログラムの第2のインスタンスを使用して、3番目のタスクを削除できる数字412で示されるように。これらの変更を処理して、コレクションの新しい状態に到達できる。0043図5は、コレクションとして実装されうる例示的ユーザインターフェースを示している。ユーザインターフェースは、たとえばデスクトップサイドバーでよく、そこでは図5に示される様々なデータアイテムすなわち、データアイテム502504、506、508、および510は、コレクション内にアイテムが出現する順序に対応する何らかの垂直順序でサイドバー内に示されるべきウィジェットである。ウィジェットのリストはコレクションとして実装でき、異なるプログラムがコレクションへのアクセスを共有できる。たとえば、ユーザはニュースフィードの上に時計を置きたいと決定して、コレクション内の最初の2つの要素の順序を交換することができる数字512で示されるように。次いで、ユーザはサイドバー内のバグを情報技術管理者に報告できる。次いで、管理者は管理プログラムを使用して、サイドバーに接続できる。管理者は、たとえばフォトビューアにバグがあることを認識でき、そのウィジェットをサイドバーから削除できる数字514で示されるように。このようにして、2人が2つの異なるアプリケーションを使用して、コレクションとして実装されたユーザインターフェースを修正する。0044図4および5の例では、図示されたコレクションは複雑なデータタイプを含みうる点に留意されたい。たとえば、図4のデータアイテムは、要約、長い記述、納期、リマインド日等のためのフィールドを含みうるタスクである。また、図5内のデータアイテムは、アプリケーション名、ディスク上の位置、ランタイムパラメータ等のフィールドを含みうるアプリケーションハンドルでよい。言い換えれば、これらの例は、共有コレクションにおいてあらゆるタイプのデータが使用されうること、および、コレクション共有メカニズムは、データの性質または構造に関係なく様々なタイプのデータを同じ方法で処理できることを示している。0045図6は、コレクションが共有されうる例示的処理を示している。図6の説明に入る前に、図6の流れ図は、例として、図1~5に示したコンポーネントを参照して説明されるが、図6の処理は任意のシステムにおいて実行でき、図1~5に示したシナリオに限定されない点に留意されたい。さらに、図6の流れ図は、ブロックをつなぐ線によって示されるように特定の順序で処理の段階が実行される例を示しているが、この図に示される様々な段階は任意の順序で、あるいは任意の結合またはサブ結合で実行されうる。0046602で、コレクションが作成される。たとえば、プログラムは、通常はローカルコレクションを作成するために使用されるメカニズムを使用することによって、コレクションを作成できる。コレクションは、リスト、アレーなどの任意のタイプのコレクションでよい。604で、コレクションは、共有するために登録されうる。たとえば、コレクションを作成するプログラムは指示を出すことができ、その指示はプログラムを実行している機械上の共有オブジェクトランタイムによって受信されうる。一例では、ランタイムは、プログラムが登録指示を出せるようにするAPIを公開するが、登録指示は他の方法でも出されうる。0047共有するためにコレクションが登録された後、コレクションへの加入要求が受信されうる606で。たとえば、コレクションを作成したプログラムと同じ名前空間を共有する他のプログラムが、そのコレクションへの加入要求を出すことができる。これらの加入要求は、加入プログラムを実行している機械上の共有オブジェクトランタイムに出すことができる。一例では、加入要求はランタイムが公開したAPIを通じて出すことができる。本明細書に記載された対象のために、作成者は加入者のうちの1人と見なされる。たとえ作成者が加入要求ではなく登録要求を出しても、共有オブジェクトの作成者は、加入者はコレクションにアクセスできるプログラムであるという意味で加入者である。加入者は、コレクションの現在の状態を受信でき608で、コレクションのローカルコピーを格納できる。0048いくつかの時点で、加入者がコレクションに変更を行う610で。例示的な変更には、挿入652、削除654、および移動656がある。挿入652は、コレクションの順序内の特定の場所で、新しいアイテムをコレクションに追加する。削除654は、コレクションから既存のアイテムを除去する。移動656は、コレクション内の2つ以上のアイテム間で順序を変更する。0049加入者の機械上の共有オブジェクトランタイムによって変更が検出されると、共有オブジェクトランタイムが適用可能なエンティティに変更を通知して612で、これらの変更が、それらのエンティティによって受信される614で。どのエンティティが適用可能なエンティティかは、実装形態に依存する場合がある。上述のように、たとえば、本明細書に記載された対象のクライアント/サーバー実装形態と、ピアツーピア実装形態との両方がある。クライアント/サーバー実装形態では、変更を検出するランタイムが、コレクションの真の状態を管理する共有オブジェクトサーバーに通知できる。ピアツーピア実装形態では、それぞれのランタイムが他のランタイムに直接通知する。0050コレクションへの変更が受信されると、衝突する変更たとえば、2つのクライアントがコレクションの同じ状態に操作を実行したことを示す変更が決定論的な方法で解決されうる616で。たとえば、2つの加入者が、コレクション内の2番目のアイテムに影響を及ぼす変更を行ったたとえば、あるエンティティが1番目および2番目のエンティティの位置を交換して、他のエンティティが同時に2番目のエンティティを削除する場合、コレクションの真の状態に到達するために、たとえば同期コンポーネント226図2に示されるに関連して上述したアルゴリズムを使用して、これらの衝突する変更は解決されうる。衝突が解決される方法は、変更を行った加入者の目的を達成してもよく、達成しなくてもよいが、結果として得られる状態は明確に確定されうる。0051クライアント/サーバー実装形態では、解決された変更が加入者に送信されうる618で。ピアツーピア実装形態では、加入者および/または加入者の機械上のランタイムが、他の加入者および/またはランタイムから変更情報を受信して、サーバーの援助なしに自身で衝突を解決する。決定論的な衝突解決処理によって、それぞれのクライアントが同じ方法で変更を解決できるようになるので、様々な加入者がコレクションの真の状態についての同じ結果に収束できる。この場合もやはり、結果として得られる状態は明確に解決されうるが、結果として得られる状態は、変更を行った加入者の目的を達成してもよく、達成しなくてもよい。0052変更するための任意の既存の衝突が解決されるとおよび、クライアント/サーバー実装形態の場合は、その衝突解決の結果がサーバーから加入者に通信されると、コレクションのローカルコピーを真の状態に沿って維持するために、それらのローカルコピーへの変更が行われうる620で。次いで、加入者はコレクションの読出しおよび書込みを続けることができる。0053図7は、本明細書に記載された対象の態様が配置されうる例示的環境を示している。0054コンピューター700は、1つまたは複数のプロセッサー702、および1つまたは複数のデータ記憶コンポーネント704を含む。プロセッサー702は、一般的に、パーソナルデスクトップまたはラップトップコンピューター、サーバー、ハンドヘルドコンピューター、あるいは他の種類のコンピューティングデバイスで見られるマイクロプロセッサーである。データ記憶コンポーネント704は、データを長期間または短期間格納できるコンポーネントである。データ記憶コンポーネント704の例には、ハードディスク、リムーバブルディスク光ディスクおよび磁気ディスクを含む、揮発性および不揮発性ランダムアクセスメモリーRAM、読出し専用メモリーROM、フラッシュメモリー、磁気テープ等がある。データ記憶コンポーネントは、コンピューター可読記憶媒体の例である。コンピューター700は、ブラウン管CRTモニタ、液晶ディスプレイLCDモニタ、または他の任意のタイプのモニタでよいディスプレイ712を備えうるか、それに関連付けられうる。0055ソフトウェアは、データ記憶コンポーネント704に格納されて、1つまたは複数のプロセッサー702上で実行しうる。このようなソフトウェアの例には、図1~6に関連して上述した機能のうちのいくつかまたは全てを実装できるコレクション共有ソフトウェア706があるが、任意のタイプのソフトウェアも使用されうる。ソフトウェア706は、たとえば、分散システム、別のファイル、別の機能、別のオブジェクト、コードの別の行等におけるコンポーネントでよい、1つまたは複数のコンポーネントを通じて実装されうる。プログラムが、ハードディスクに格納されて、RAMにロードされて、コンピューターのプロセッサーで実行されるコンピューターたとえば、パーソナルコンピューター、サーバーコンピューター、ハンドヘルドコンピューター等は図7に示されるシナリオの典型であるが、本明細書に記載された対象はこの例に限定されない。0056本明細書に記載された対象は、データ記憶コンポーネント704のうちの1つまたは複数に格納されて、プロセッサー702のうちの1つまたは複数で実行するソフトウェアとして実装されうる。他の例としては、対象は、1つまたは複数のコンピューター可読記憶媒体に格納される指示として実装されうる。光ディスクまたは磁気ディスクなどの有形媒体は、記憶媒体の例である。指示は持続性媒体上に存在しうる。このような指示は、コンピューターまたは他の機械によって実行されると、方法の1つまたは複数の動作をコンピューターまたは他の機械に実行させることができる。動作を実行するための指示はある媒体に格納されてもよく、複数の媒体にわたって分散されてもよいので、全ての指示が同じ媒体上にあるかどうかに関わらず、1つまたは複数のコンピューター可読記憶媒体上に指示が集合的に出現しうる。0057さらに、本明細書に記載された任意の動作図示されているかどうかに関わらずは、方法の一部として、プロセッサーたとえば、1つまたは複数のプロセッサー702によって実行されうる。したがって、本明細書に動作A、B、およびCが記載されている場合、A、B、およびCの動作を備える方法が実行されうる。さらに、本明細書に動作A、B、およびCが記載されている場合、プロセッサーを使用してA、B、およびCの動作を実行するステップを備える方法が実行されうる。0058ある例示的環境では、コンピューター700は、ネットワーク708を通じて1つまたは複数の他のデバイスと通信可能なように接続されうる。構造の点でコンピューター700と類似してよいコンピューター710は、コンピューター700に接続されうるデバイスの例であるが、他のタイプのデバイスもそのように接続されうる。0059対象を、構造的特徴および/または方法論的行為に特有の文言で説明してきたが、添付の特許請求の範囲に定められる対象は、上述の特定の特徴または行為に必ずしも限定されないことが理解されるべきである。むしろ、上述の特定の特徴および行為は、特許請求の範囲を実装する例示的形式として開示したに過ぎない。