Distribution of identifiers in serverless networks

Claim 3

The method of claim 1 wherein in every ascending new round of execution the short sectors at the end of the previous round are considered to be long sectors at the beginning of the next round, the number of sectors increasing in each round by a factor of two.

Claim 4

The method of claim 1 wherein identifiers may be withdrawn arbitrarily in any round as well as assigned, and if an identifier withdrawn is an endpoint of an undivided long sector, an already-assigned identifier in that round having a value of a midpoint of a long sector is reassigned using the value of the withdrawn identifier, freeing the previous midpoint value to be reused.

Claim 5

The method of claim 3 wherein if in any instant round withdrawal of an identifier will reduce the number of sectors below the beginning number of sectors for the round, a new descending round is entered wherein the long sectors of the instant round are considered short sectors of the descending round.

Claim 6

The method of claim 4 wherein a bitmap is used in any round for identifying, at any point in time, which long sectors are divided into short sectors by assignment of identifiers, and which are not yet divided, the number of bits in the bitmap equal to the number of long sectors in the round.

Claim 7

The method of claim 5 wherein the bitmap is divided into equal-length fragments, each fragment representing a group of adjacent sectors of the circle.

Claim 8

The method of claim 6 wherein the fragment length is a power of two.

Claim 9

The method of claim 6 wherein a hierarchy of bitmap fragments is established over the main bitmap, one bit in each upper-level bitmap representing a bitmap fragment in the next lower-level bitmap, wherein a one in a bit of an upper-level bit indicates either presence of at least one undivided sector or at least one divided sector represented in the associated lower-level fragment.

Claim 10

The method of claim 8 wherein the hierarchy of bitmaps is used to select sectors to divide to provide values for assignment as identifiers or assigned values to be re-assigned.

Claim 11

The method of claim 5 wherein the bitmap is consulted in selecting sectors for assigning and reassigning identifiers.

Claim 12

A distributed, serverless system comprising: a plurality of computerized appliances as active and inactive nodes in the serverless system; a communication facility interconnecting individual ones of the plurality of computerized appliances; and an assignment system for assigning and re-assigning identifiers to nodes of the serverless system; wherein the assignment system establishes a circle as a locus of all identifiers, with the value of any point on the circle being the portion of one complete revolution in a first direction around the circle to the point, measured from a first zero point, and selects values to be assigned as identifiers as needed by successive rounds of assignment, wherein, in any round of assignment, beginning with n equal-length sectors, termed long sectors, only the value of midpoints of long sectors are selected as new identifiers to be assigned in the system, each new assignment creating two new short sectors, the round continuing until all long sectors are divided, making the number of sectors at the end of the round, and the beginning of the next round 2n, and wherein the beginning and end of any round of assignment has identifiers assigned with point values that divide the circle into equal-length sectors.

Claim 13

A distributed, serverless system comprising: a plurality of computerized appliances as active and inactive nodes in the serverless system; a communication facility interconnecting individual ones of the plurality of computerized appliances; and an assignment system for assigning and re-assigning identifiers to nodes of the serverless system; wherein the assignment system establishes a circle as a locus of all identifiers, with the value of any point on the circle being the portion of one complete revolution in a first direction around the circle to the point, measured from a first zero point, and selects values to be assigned as identifiers as needed by successive rounds of assignment, wherein, in any round of assignment, beginning with n equal-length sectors, termed long sectors, only the value of midpoints of long sectors are selected as new identifiers to be assigned in the system, each new assignment creating two new short sectors, the round continuing until all long sectors are divided, making the number of sectors at the end of the round, and the beginning of the next round 2n, and wherein the beginning and end of any round of assignment has identifiers assigned with point values that divide the circle into equal-length sectors.

Claim 14

The distributed system of claim 11 wherein in every ascending new round of execution the short sectors at the end of the previous round are considered to be long sectors at the beginning of the next round, the number of sectors increasing in each round by a factor of two.

Claim 15

The distributed system of claim 11 wherein identifiers may be withdrawn arbitrarily in any round as well as assigned, and if an identifier withdrawn is an endpoint of an undivided long sector, an already-assigned identifier in that round having a value of a midpoint of a long sector is reassigned using the value of the withdrawn identifier, freeing the previous midpoint value to be reused.

Claim 16

The distributed system of claim 13 wherein if in any instant round withdrawal of an identifier will reduce the number of sectors below the beginning number of sectors for the round, a new descending round is entered wherein the long sectors of the instant round are considered short sectors of the descending round.

Claim 17

The distributed system of claim 14 wherein a bitmap is used in any round for identifying, at any point in time, which long sectors are divided into short sectors by assignment of identifiers, and which are not, the number of bits in the bitmap equal to the number of long sectors in the round.

Claim 18

The distributed system of claim 15 wherein the bitmap is divided into equal-length fragments, each fragment representing a group of adjacent sectors of the circle.

Claim 19

The distributed system of claim 16 wherein the fragment length is a power of two.

Claim 20

The method of claim 16 wherein a hierarchy of bitmap fragments is established over the main bitmap, one bit in each upper-level bitmap representing a bitmap fragment in the next lower-level bitmap, wherein a one in a bit of an upper-level bit indicates either presence of at least one undivided sector or at least one divided sector represented in the associated lower-level fragment.

Claim 21

The method of claim 18 wherein the hierarchy of bitmaps is used to select sectors to divide to provide values for assignment as identifiers or assigned values to be re-assigned.

Claim 22

The distributed system of claim 15 wherein the bitmap is consulted in selecting sectors for assigning and reassigning identifiers.